两个凸多边形的交点

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

这是一些链接:

• 计算机图形学I - 多边形裁剪和填充(pdf)
• rosettacode.org - Sutherland-Hodgman多边形裁剪

Answer 2

您可以从两个多边形都是凸面的事实中受益.有了这些知识,您可以使用以下扫描线算法实现O(n)时间:

找到两个多边形中最顶部的点.为简单起见,假设您没有水平边.创建有助于多边形左右边界的边列表.

扫平飞机时,你可以存放4条边.left_edge_C1,right_edge_C1,left_edge_C2,right_edge_C2.你不需要任何复杂的方法来磨边,因为它们只有四个.您可以通过迭代所有可能的选项来找到下一个事件点.

在每个事件点处,一些边缘出现在它们的交叉点的边界上.基本上,在每个事件点,您可以拥有一个免费案例(参见图片).