algorithm - 两个凸多边形的交集

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(n²)

---

这里有几个链接:

• Computer Graphics I – Polygon Clipping and Filling (pdf)
• rosettacode.org – Sutherland-Hodgman polygon clipping