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. 

これは単純な使い方で十分です。すべてのフレームを再計算しません。 — O（N ）ここで

---

はいくつかのリンクです：

• Computer Graphics I – Polygon Clipping and Filling（PDF）
• rosettacode.org – Sutherland-Hodgman polygon clipping

Answer 2

あなたがいるという事実から恩恵を受けることができます両方のポリゴンが凸です。この知識を使って、次の掃引線アルゴリズムを使用して、O（n）時間を達成することができます。

両方のポリゴンのトッパポイントを見つけます。簡単にするため、水平なエッジがないとします。ポリゴンの左と右の境界に寄与するエッジのリストを作成します。

飛行機を掃除している間に、4つのエッジが保存されます。 left_edge_C1、right_edge_C1、left_edge_C2、right_edge_C2。エッジを描画するのに複雑なものは必要ありません。そのうち4つしかないからです。すべての可能なオプションを反復するだけで、次のイベントポイントを見つけることができます。

各イベントポイントで、交差点の境界にエッジが表示されます。基本的に、各イベントポイントで無料のケースの1つを持つことができます（写真を参照）。

Yolaの素敵な平面スイープ記述@に加え

Answer 3

、 Computational Geometry in Cで説明した線形時間アルゴリズムが存在し、第7章とC & Javaコードは（同じリンクで）入手可能です。 2つのポリゴンがある点で交差する場合、または交差点がセグメントである場合など、いくつかのトリッキーな縮退の場合があります。