兩個凸多邊形的交點

Question

我有兩個凸多邊形。多邊形實現爲其頂點的循環列表。如何找到這兩個多邊形的交集？

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（ñ ）

---

下面是幾個環節：

• 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。你不需要任何複雜的邊緣，因爲它們只有四個。您可以通過迭代所有可能的選項來找到下一個事件點。

在每個事件點，其交點邊界上會出現一些邊緣。基本上，在每個事件點你可以有一個免費的案例（見圖）。

Answer 3

除了@約拉的很好的平面掃描描述， 存在 Computational Geometry in C，第7章與C & Java代碼中描述的線性時間的算法是可用的（在相同的鏈接）。有幾個棘手的退化情況，例如，當兩個多邊形在某一點相交，或者交點是一個線段時。