5

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

当前版本的伪代码：

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）。红线显示哪些两条边未被交叉。结果应该始终是一系列平面图，尽管不确定是否有多个有效结果或只有一个。

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

例子

4

2 回答 2

1

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

在此处输入图像描述

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

于 2013-01-04T05:03:03.570 回答
0

您似乎希望最终得到一个嵌入的平面多边形，其顶点正是给定的点集合。点上所需的“顺序”是您通过绕过多边形的边界并按照它们出现的顺序枚举顶点而得到的。

对于给定的点集合，通常会有多个具有此属性的嵌入多边形；例如，考虑以下点列表：

(-1,-1), (0,0), (1,0), (1,1), (0,1)

此列表定义了一个符合您标准的多边形（如果我理解正确的话）。但是此列表的以下顺序也是如此：

(-1,-1), (1,0), (0,0), (1,1), (0,1)

这是一种可行的算法（我不知道快速）。

首先，按 x 坐标（例如使用快速排序）以升序对您的点进行排序（称为此列表 L）。

其次，找到凸包（例如用 quickhull）；凸包的边界将包含排序列表 L 中最左边和最右边的点（称为这些 L[1] 和 L[n]）；令 S 为 L[1] 和 L[n] 边界上的点的子集。

您想要的列表是 S，按照它在 L 中出现的顺序（这也是它在凸包边界中出现的顺序），然​​后是其他元素 LS，其顺序与它们在 L 中出现的顺序相反。

前两个操作通常需要时间 O(n log n)（最坏情况 O(n^2)）；最后一个需要时间 O(n)。您得到的多边形将是凸包的下边界（例如，从左到右），以及它们上方从右到左的“之字形”中的其余点。

于 2013-01-04T03:25:43.597 回答