computational-geometry - 2 つの多角形の共通の内点を見つける

Question

ポリゴンが重なっているとします。どちらも必ずしも凸ではありません。どちらの境界上でもなく、両方の内側にあるポイントを見つける効率的なアルゴリズムは何ですか?

それらが重なり合い、ポリゴンが 3D の頂点のセットによって定義されていると仮定します。

Answer 1

Vatti ポリゴン クリッピング アルゴリズムの変形を使用できます。Vatti のアルゴリズムはスキャンライン アルゴリズムです。これは基本的に、両方のポリゴンの頂点を (たとえば) 左から右にスキャンすること、およびそれらの境界間の交点をスキャンすることを意味します。これらの「イベント」の連続する 2 つを通る垂直線の間で、ポリゴンによって作成された台形/三角形を調べます。両方の一部である台形を見つけたら、その重心を出力できます。