0

我有一个边列表和一个顶点列表。每条边引用两个顶点，每个顶点维护一个边列表。

我想找到从此图生成的所有非重叠多边形。

一个例子是

0,0) (4,0) (4,2) (4,4) (2,4) (2,2) (4,2) (6,2) (6,6) (0,6) ( 0,0)

这条路径应该描述在某些顶点上具有碰撞的每个唯一边。在实际图中，顶点是不同的。我需要的两个多边形是 (0,0) (4,0) (4,2) (2,2) (2,4) (4,4) (4,2) (6,2) (6,6) (0,6) 和 (2,2) (2,4) (4,4) (4,2)

4

2 回答 2

3

您所描述的是在图中找到所有最小电路的问题。（我认为它恰好有一个几何模型是无关紧要的。）这里有一篇论文可以找到一个最小的电路。您可以通过删除最小电路的边缘并再次运行算法来构建它。

对于有向图的情况，此线程中也讨论了该问题。您可以通过制作每个边的副本并将顶点反转然后将其视为有向图，从而将您的图转换为有向图。唯一的问题是每个多边形会被找到两次，每个遍历方向一次。您可以通过后处理步骤或在算法运行时通过一些巧妙的簿记来清理它。

于 2011-08-29T22:23:19.723 回答
1

嗯，我在想...

唯一特别感兴趣的顶点是具有两条以上边的顶点。要找到所有具有两个以上边的顶点是 O(n)。然后找到最紧密的闭环与在给定顶点处找到给定边和另一边之间的最小 theta 相同（如果顶点是 ccw，这是从当前边顺时针方向的最小角度）。为了找到所有最紧密的闭环，我需要在边数大于 2 的顶点处检查所有边 ccw 边对。这是跟踪的初始化。从那时起，跟踪将始终顺时针选择具有最小 theta 的下一条边。返回路径后，我将移动到根顶点中的下一个边对，然后再次路径。检查完所有对后，我将移动到边数大于 2 的下一个顶点。现在，如果我只能确定我是否陷入已知循环而不是追踪。也许如果路径的前两个顶点在已知多边形中以相同的顺序出现......

听上去怎么样？我知道这不是 djikstra，但它会起作用，并且希望比找到所有循环蛮力更快。

于 2011-08-30T13:42:50.813 回答