两个凸多边形的交集

Question

我有两个凸多边形。这些多边形的实现是它们顶点的循环列表。如何找到这两个多边形的交集？

- Tikhon Belousko

Answer 1

由于两个多边形都是凸的，你可以从中受益。并且通过使用以下扫描线算法，你可以实现O(n) 的时间复杂度:

找到两个多边形中最高的点。为了简单起见，假设你没有水平边缘。创建贡献到多边形左侧和右侧边界的边缘列表。

在扫描平面时，你需要存储4个边缘：left_edge_C1, right_edge_C1, left_edge_C2, right_edge_C2。你不需要任何复杂的方法来存储这些边缘，因为它们只有四个。你可以通过迭代所有可能的选项来查找下一个事件点。

在每个事件点上，某些边缘出现在它们的交界处。基本上，在每个事件点上，你可以有三种情况之一（参见图像）。

- Yola

---

这个解释并不完全清楚。I) 这三种情况没有被彻底解释清楚。我不理解图像中第一个和最后一个例子之间的区别。可能部分原因是我不理解阴影区域的含义。left_edge 也没有被清楚地解释。将边缘分为绿色和红色使得看起来所有的边缘都被分为两类，但是其中一个绿色（左边）的边缘的端点在顶部的右侧，所以对于那个边缘没有明确的规则。因此，我无法理解整个算法。 - undefined

Answer 2

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多边形剪辑

- Markus Jarderot

---

你确定在第三种情况下要将V3添加到交集中吗？这似乎是不正确的。 - Tikhon Belousko

我重写了它，以更好地与Sutherland-Hodgman算法对齐。 - Markus Jarderot

Answer 3

除了@Yola的不错的平面扫描描述外，还有一种线性时间算法在计算几何中的C语言第7章中进行了描述。同时提供了C和Java代码（在同一链接中）。存在一些棘手的退化情况，例如，当两个多边形相交于一个点时，或者交点是一个线段时。

- Joseph O'Rourke