3

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

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

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

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

当我从 A 开始然后到达 E 顶点时，我如何决定选择 G 路径？

PS：如果我的方法不适合这个问题或者有更好/更简单的解决方案，我愿意接受与我不同的方法

样品图

4

1 回答 1

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

下一个弧的示例：

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

于 2019-06-10T01:50:15.310 回答