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

Question

我有一个顶点列表，并且我知道它们之间的连接。我试图找到顶点的所有多边形形状。这些多边形形状不应重叠。

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

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

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

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

P.S：如果我的方法不适合这个问题或者有更好/更简单的解决方案，我愿意采用与我的方法不同的方法

Answer 1

根据您的示例，您试图找到平面图的faces，由其顶点和边定义。

步骤 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

下一个弧线示例：

• (D -> C) 是 (A -> D) 的下一条弧
• (C -> G) 是 (D -> C) 的下一条弧
• (G -> E) 是 (C -> G) 的下一条弧
• 等等...

该算法将找到所有内部面加上一张外部面，以循环（A -> E, E -> B, B -> F, F -> G, G -> C, C -> D ，D -> A）。您可以忽略这个外部面，但在某些情况下它可能很有用 - 例如，当您是给定的一个点并且您需要找到它相对于整个图形的位置时。