两个凸多边形的交点(Intersection of two convex polygons)

我有两个凸多边形。 多边形被实现为它们的顶点的循环名单。 如何找到这两个多边形的交集？

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 ^2） 的

---

下面是几个环节：

• 计算机图形I -多边形裁剪和填充 （PDF）
• rosettacode.org -萨瑟兰-Hodgman多边形裁剪

Answer 2:

您可以受益于一个事实，即两个多边形凹凸有致。 而与此知识，你可以通过使用跟随着扫描线算法实现O（n）的时间：

查找这两个多边形的最上面的点。 为简单起见假设你有没有水平边缘。 建立促进多边形的左右边界边缘的名单。

虽然扫下了飞机你存储4个边缘。 left_edge_C1 ， right_edge_C1 ， left_edge_C2 ， right_edge_C2 。 你不需要任何复杂strore边缘，因为只有他们四人。 您只需通过遍历所有可能的选择找到下一个事件点。

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

Answer 3:

除了@约拉的很好的平面扫描介绍，还有中描述的线性时间的算法用C计算几何 （在同一链路），第7章。而C＆Java代码是可用的。 有几种棘手退化情况，例如，当两个多边形相交于一点，或交点是一个段。

文章来源: Intersection of two convex polygons