重複する凸多角形の検索

Question

私は、中程度の数の辺を持つ凸多角形のセットを持っています（例えば4から30）。ポリゴンの数十分の1、例えば100〜1000があります。それらの大部分は分離されていますが、いくつかは2〜10の小さなグループを形成し、それらの間に重なりがあります。

重複するポリゴンのグループを効率的に識別する必要があります。

古典的なアルゴリズムはありますか？ （私は掃引アプローチを考えていますが、おそらくそれが良いでしょうか？）検出前にポリゴンをボックスに囲むことは有益でしょうか？

以下、代表例です。二次元的にこの種の問題のために使われています

Answer 1

一つの伝統的なアプローチは、あなたが各バケット内のオブジェクトの数が少ないまで階層的に連続して小さいバケットにあなたの2次元空間を分割四分木を構築することです。

オブジェクトが交差したバケットまたはバケットのセットが見つかるまで、重複検出がクワッドツリーを歩き、小さなセットのオブジェクトに対して重複検出を実行します。

あり、建物への簡単な紹介だと、ここで衝突検出のためにそれらを使用して：Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space

簡素が、より計算コストのアプローチは1つのポリゴンが他を閉塞するかどうかを判断するためにビットZバッファを使用してのような何かをするだろう：

• あなたの多角形のそれぞれ固有の番号（それの深さ）
• にバッファにラスタライズ各ポリゴンを割り当て、それぞれをチェックすると、すでに設定されていますピクセルを閉塞したかどうか確認するために、バッファに書き込みます。そうであれば、奥行きは、あなたが遮ったポリゴンと、それを遮ったポリゴンを書いた新しい値を識別します。