6

SFML c++ ライブラリで凸形状しか形成できないというルールを回避しようとしています。

これを行うために、指定された頂点をテストすることを計画しています。凹型の場合は、頂点をグループに分割し、各グループの凹型をテストし、組み合わせたときに元の形状のように見える完全な凹型形状が得られるまで繰り返します。

私が知りたいのは...

  • 形状の凹みをテストするための方程式は何ですか?それは何であり、どのように機能しますか?

  • 凹形状の頂点を分割して、最終的に形状ができるだけ少ない凸形状から形成されるようにするにはどうすればよいですか?

  • 私の目標を達成するためのベストプラクティスは何ですか?

ありがとう！

4

5 に答える 5

6

すべてのエッジを一周し、次のエッジが常に同じ方向 (左手/右手) に移動していることを確認することで、形状が凸包であるかどうかをテストできます。これは、高速で安価なアルゴリズムです。これの実装がここにあります: en.wikipedia.org/wiki/Graham_scan

凸包がない場合は、パッケージ ラッピング アルゴリズムを実行して、すべてのポイントを包含する凸包を取得します (これも非常に高速です)。en.wikipedia.org/wiki/Gift_wrapping_algorithm

次に、形状上にあるが凸包上にないポイントを探します。これらのポイントの実行ごとに、これらのポイントから新しい形状を作成します (さらに、凸包の両側の 2 つ)。

再帰はあなたの友達です: 今作ったサブシェイプのそれぞれに対して全く同じプロセスを実行してください.

この手法を使用して、ポイントが任意の形状の内部に含まれているかどうかをテストしました。つまり、ポイントは凸包の内部にある必要があります (テストは簡単です)。 -形....

于 2011-07-13T23:21:44.077 に答える
4

昨日公開されたBoost Geometry ライブラリには、 が実装されています。絵は千の言葉以上を語ります： Convex Hull algorithm

ここに画像の説明を入力

これは非凹型 (つまり凸型) の「新しい」形状を構築しますが、これはまさにあなたが望むものかもしれませんし、そうでないかもしれません。ただし、その過程で、アルゴリズムは形状を凹凸に分類できるはずなので、それでもライブラリに興味があるでしょう。

凸包アルゴリズムに関する一般情報:

Adrian Japon は多かれ少なかれ「ヒット テスト」(封じ込めテスト) が凸面/凹面のジオメトリを気にする通常の理由であると示唆したので、これ以上苦労することなく、それに対応する Boost Geometry アルゴリズムを強調しますwithin。

繰り返しますが、写真がとてもきれいだからです。図は多角形に対して点を照会することを示唆していますが、アルゴリズムは完全に汎用的であり、別のn次元の多角形の完全な封じ込めをテストするために使用できます。

ここに画像の説明を入力

于 2011-07-13T22:20:54.923 に答える
3

さて、すべての情報を一緒にマッシュするだけです：

画像1

  • 最後に、この PowerPointの情報を使用して、現在のモノトーン形状を三角測量します。

    1. u1 と u2 をスタックにプッシュします。
    2. j = 3 /* j は現在の頂点のインデックス */
    3. u = uj
    4. ケース (i): u は v1 に隣接しているが vi に隣接していない。対角線 uv2、uv3、…、uvi を追加します。スタックから vi、vi-1、…、v1 をポップします。vi、u をスタックにプッシュします。ケース (ii): u は vi に隣接していますが、v1 には隣接していません。while i > 1 および角度 uvivi-1 <  対角線 uvi-1 スタックから vi をポップ endwhile プッシュ u ケース (iii): v1 と vi の両方に隣接する u。対角線 uv2、uv3、…、uvi-1 を追加します。出口
    5. j = j + 1 ステップ 3 に進みます。 
**Note:**
By “adjacent” we mean connected by an edge in P.   
Recall that v1 is the bottom of the stack, vi is the top.    
By “Push” we mean push the item(s) to the back of the list

これが誰かの役に立てば幸いです...しかし、私はまだより良い/より速い解決策を探しています。

于 2011-07-15T02:21:57.623 に答える
1

考えるべきいくつかのこと：

  • 左利きと右利きの角（十字の印は簡単に区別できます）。凸型の角はすべて同じ手触りです。

  • エッジを拡張して新しい頂点を追加すると、既存の頂点間にエッジを追加するよりも良い結果が得られる場合があります。

于 2011-07-13T22:31:17.680 に答える
1

ポリゴンをポイントのリストとして持っていると仮定します。非常に簡単な方法は、ポリゴンを一周して、連続するポイントのトリプレット（A、B、C）のシーケンスを検討することです。

次に、ある時点で det(AB,BC) がその符号を変更することを確認します。

det(AB,AC) = (x_a-x_b)(yc-yb) - (x_c-x_b)(y_a-y_b)

于 2011-07-13T23:23:29.267 に答える