algorithm - 2 つの凸多角形の交点

Question

私は2つの凸多角形を持っています。ポリゴンは、頂点の循環リストとして実装されます。この 2 つのポリゴンの交点を見つける方法は?

Answer 1

For each edge V1-V2 in the first polygon,
    Let H := Half-plane tangenting V1-V2, with the remaining
        vertices on the "inside".
    Let C := New empty polygon.
    For each edge V3-V4 in the second polygon,
        Let X := The intersection between V3-V4 and H.
        If V3 inside H, and V4 is outside H then,
            Add V3 to C.
            Add X to C.
        Else if both V3 and V4 lies outside H then,
            Skip.
        Else if V3 outside H, and V4 is inside H then,
            Add X to C.
        Else
            Add V3 to C.
    Replace the second polygon with C.

これは、単純な使用には十分です。10 ～ 20 個の頂点があり、フレームごとに再計算されません。— O( n ² )

---

ここにいくつかのリンクがあります：

• コンピュータ グラフィックス I – ポリゴンのクリッピングと塗りつぶし(pdf)
• rosettacode.org – Sutherland-Hodgman ポリゴン クリッピング

Answer 2

両方のポリゴンが凸面であるという事実を利用できます。そして、この知識があれば、次のスイープ ライン アルゴリズムを使用してO(n)時間を達成できます。

両方の多角形の最上点を見つけます。簡単にするために、水平方向のエッジがないと仮定します。ポリゴンの左境界と右境界に寄与するエッジのリストを作成します。

平面をスイープしながら、4 つのエッジを保存します。left_edge_C1, right_edge_C1, left_edge_C2, right_edge_C2. エッジは 4 つしかないため、エッジを格納するための複合体は必要ありません。すべての可能なオプションを繰り返すだけで、次のイベント ポイントを見つけることができます。

各イベント ポイントでは、交点の境界にいくつかのエッジが表示されます。基本的に、各イベント ポイントで 3 つのケースのいずれかを使用できます (写真を参照)。

Answer 3

@Yola の素敵な平面スイープの説明に加えて、 Computational Geometry in Cの第 7 章で説明されている線形時間アルゴリズムがあります。また、C & Java コードは (同じリンクで) 利用できます。いくつかのトリッキーな縮退のケースがあります。たとえば、2 つのポリゴンが 1 点で交差する場合や、交差がセグメントである場合です。