27

System.Windows.Shapes.Polygon一連のポイントによってレイアウトが完全に決定されるオブジェクトがあります。このポリゴンが自己交差しているかどうか、つまり、ポリゴンのいずれかの辺が頂点ではない点で他の辺と交差しているかどうかを判断する必要があります。

これを計算する簡単で高速な方法はありますか?

4

4 に答える 4

35

  • 簡単、低速、低メモリ フットプリント: 各セグメントを他のすべてのセグメントと比較し、交差をチェックします。複雑さO(n 2 ) .

  • わずかに高速で中程度のメモリ フットプリント(上記の修正バージョン): エッジを空間 "バケット" に格納し、バケットごとに上記のアルゴリズムを実行します。複雑度O(n 2 / m)バケットm個 (一様分布を仮定) 。

  • 高速で高いメモリ フットプリント: 空間ハッシュ関数を使用して、エッジをバケットに分割します。衝突をチェックします。複雑さO(n) .

  • 高速でメモリ使用量が少ない:ここ(またはここ) で説明されているようなスイープライン アルゴリズムを使用します。複雑さO(n log n)

後者は、速度とメモリのバランスが良く、特にBentley-Ottmann アルゴリズムが優れているため、私のお気に入りです。実装もそれほど複雑ではありません。

于 2011-02-02T15:25:22.543 に答える
3

隣接していない線分のペアが交差しているかどうかを確認します。

于 2011-02-02T15:15:42.507 に答える
2

完全を期すために、この議論に別のアルゴリズムを追加します。

読者が軸に沿ったバウンディング ボックスについて知っていると仮定すると (そうでない場合は Google で検索してください)、「スイープ アンド プルーン アルゴリズム」を使用して、AABB の衝突があるエッジのペアをすばやく見つけることは非常に効率的です。（グーグル）。次に、これらのペアに対して交差ルーチンが呼び出されます。

ここでの利点は、非直線エッジ (円とスプライン) と交差することさえあり、アプローチはほぼ同様に効率的ですが、より一般的であることです。

于 2013-07-25T19:06:05.873 に答える