如何找到给定顶点的所有多边形形状？

Question

我有一组顶点，并且知道它们之间的连接。我正在尝试找到所有这些顶点形成的多边形，这些多边形不应重叠。

我进行了一些研究，认为如果我可以沿着顶点顺时针（或逆时针）遍历，就可以检测到多边形形状。因此，我寻找了沿着顶点顺时针遍历的解决方案。我发现了一个类似的话题并尝试了建议的解决方案。但问题是，在遍历顶点时，当有多个顺时针选项可供选择时，我无法确定选择哪条路径。

基本上，我想找到以下多边形形状：

* A, E, G, C, D, A
* E, F, G,  E 
* E, B, F, E

当我从A点出发，到达E点时，如何决定选择G路径？

附注：如果我的方法不适用于此问题或有更好/更简单的解决方案，我也可以尝试其他方法。

- onler

---

我该如何决定选择 G 路径？我猜你不应该这样做，你可以找到一个顶点最少的多边形，然后切割它（删除非共享的边缘，或以某种方式标记多边形为已删除）。然后找到下一个顶点最少的多边形，以此类推... - Renat

是的，寻找顶点最少的多边形是另一种方法。但是，需要回答两个问题：

1. 如何找到顶点最少的多边形？
2. 如何解决重叠问题？请参见示例图像。在这种情况下，ABC、ABD、ACD、BCD都具有最少的顶点数。我如何决定放弃ABC并保留其余部分？

- onler

好的，在谷歌搜索“最短循环”时，我认为我已经找到了你问题的答案：https://math.stackexchange.com/questions/8140/find-all-cycles-faces-in-a-graph - Renat

你需要更清晰的解释“所有顶点的多边形形状”。为什么不选择例如AECD？或者三角形ACD？为什么不使用像Delaunay三角剖分算法这样的东西来适应你的目的？ - Gene

@Renat 谢谢，这个问题有一个相关的问题（https://dev59.com/SFHTa4cB1Zd3GeqPRGm2），我认为它和我的问题是一样的。被接受的答案基本上与您建议的相同。提供了伪代码和代码的工作版本：https://gist.github.com/mastoj/750015 但是，它没有解决我在先前评论中提到的重叠问题。 - onler

@Gene 基本上，我开始有一个矩形形状（四个顶点和四条边）。新的顶点将被动态添加，这些新的顶点可能会分割矩形区域成小块。我的主要目的是跟踪这一点并计算每个单独区域的大小。我在搜索如何做到这一点时遇到了“Delaunay三角剖分算法”。我认为这可能是解决这个问题的方法，但我无法找到解决方法。 - onler

Answer 1

根据您的示例，您正在尝试查找由其顶点和边定义的平面图的面。

步骤1。 用连接两个方向的顶点的一对有向边（弧）替换每个未定向边。 对于每个弧（v1 -> v2），找到一个下一个弧（v2 -> v3），使得这两个弧的左侧都有相同的面-可以通过计算弧与轴（例如OX）之间的角度并按顺时针（或逆时针）顺序进行排序来完成此操作。 将所有弧标记为“未使用”。

步骤2。 拾取任何“未使用”的弧，并依次跟随下一个弧，直到达到初始弧的起点-您将获得一个界定面的循环。 您已找到所有弧/顶点的新面。 将此循环中的所有弧标记为“已使用”。 重复此操作，直到没有“未使用”的弧为止。

回到您的示例-您将拥有以下弧：

A -> E, E -> A
A -> D, D -> A
B -> E, E -> B
B -> F, F -> B
C -> D, D -> C
C -> G, G -> C
E -> F, F -> E
E -> G, G -> E
F -> G, G -> F

next 弧的例子：

• (A -> D) 的 next 弧是 (D -> C)
• (D -> C) 的 next 弧是 (C -> G)
• (C -> G) 的 next 弧是 (G -> E)
• 等等...

此算法将找到所有内部面以及一个由循环 (A -> E, E -> B, B -> F, F -> G, G -> C, C -> D, D -> A) 界定的外部面。您可以忽略这个外部面，但在某些情况下它可能会有用 - 例如，当您获得一个点并且需要找到它相对于整个图形的位置时。

- HEKTO

---

有没有想法如何检测和忽略外部面？ - Magnuti

@Ramriez - 考虑每个弧和其下一个弧之间的角度。外部环上这些角度的总和将为PI*(n+2)，任何内部环上的总和为PI*(n-2)。这里的n是环的长度。 - HEKTO