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

Question

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

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

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

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

从A点到E点，如何决定选择G路？

P.S：如果我的方法不适合这个问题或者有 better/easier 解决方案

，我愿意接受与我不同的方法

Answer 1

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

步骤 1. 用一对有向边（弧）替换每个 un-directed 边，连接两个方向的顶点。对于每个圆弧 (v1 -> v2) 找到一个 next 圆弧 (v2 -> v3)，使得这两个圆弧在 左侧有相同的面 - 这可以通过计算圆弧和轴（比如）OX 之间的角度并按顺时针（或 counter-clockwise）顺序排列它们来完成。将所有圆弧标记为"unused".

第 2 步。 拾起任何 "unused" 弧并沿着下一条弧一个接一个地走，直到到达初始弧的原点 - 您将得到一个循环, 包围着一张脸。您发现了一张新面孔 arcs/vertices。将此循环中的所有弧标记为"used"。重复直到没有 "unused" 个弧。

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

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）。您可以忽略这个外部面，但在某些情况下它可能很有用 - 例如，当您给定一个点并且您需要找到它相对于整个图形的位置时。

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

How to find all the polygonal shapes of given the vertices?

algorithm

math

geometry

polygon

planar-graph