polygons - 取消一组多边形中任何交叉边的快速算法

Question

我有许多多边形，每个多边形都表示为一个点列表。我正在寻找一种快速算法来遍历多边形列表并取消所有交叉边，直到没有交叉边为止。

当前版本的伪代码:

While True:
    For each pair of polygons:
         for edge1 in first_polygon:
             for edge2 in second_polygon:
                 if edges_cross(edge1,edge2): # Uses a line segment intersection test
                     uncross_edges(first_polygon,second_polygon,edge1,edge2)
    If no edges have been uncrossed:
        break

这可以通过用递归替换 while 循环来改善一点。但是，它在性能方面仍然很差。

以下是解开*的简单示例。实际上会有大量的多边形和每个多边形相当数量的点(大约 10-500)。红线显示哪两条边没有交叉。结果应该总是一系列平面图，尽管不确定是否有多个有效结果或只有一个。

编辑:这次我先添加线条，然后添加点，并使用更复杂的形状。假装点是固定的。

Answer 1

首先，让我们说明你想要什么(如果我没猜错的话)。假设您有两个多边形，其中一个有边 (a, b)与边相交 (s, r)另一个。这些多边形也有顺时针方向，所以你知道 b 之后的下一个顶点，以及 r 之后的下一个顶点.由于边缘交叉，您将它们都删除，然后添加四个新的。您添加的新内容是:(a, r) , (r, next(b)) ; (s, b) , (b, next(r)) .所以你又得到了两个多边形。这如下图所示。请注意，最初仅删除两条边(每个多边形一条边)，所有交叉都已解决。



加速 O(n^2) 的琐碎实现每次迭代并不容易，每个多边形 500 个点是一个非常小的数量需要担心。如果您决定这次需要改进，我最初的建议是使用 Bentley-Otmann algorithm以某种聪明的方式。聪明的方法是运行算法，然后当你找到一个交叉点时，你执行上面的过程来消除这个交叉点，然后你更新指导算法的事件。希望可以更新要处理的事件，而不会使算法在这种情况下无用，但我没有证据。