algorithm - 从 2D 网格创建多边形的高效算法？ (顶点+边)

Question

给定一个由顶点(二维坐标)和边(作为顶点对)列表组成的网格，如下所示:

所以边缘定义如下:

a: 2,3 
b: 3,4
c: 4,8
d: 5,8
e: 6,7
etc..

边是方向中性的，即定义边的任意两个顶点的顺序是随机的(边不是顺时针或逆时针)。

多边形可以是凸面或凹面，但它们从不重叠或自相交(边从不交叉)。

问题:如何生成所有多边形的列表？

更具体地说，在上面的示例中，我需要 4 个多边形，如下所示:

(a,b,c,d,i)
(d,g,h)
(f,i,j,k)
(e,h,k)

多边形也没有方向，顺时针或逆时针不适用，事实上定义多边形的边的顺序也可能是随机的。例如，5 边形的 (a,i,d,b,c) 也可以。

与其将多边形定义为边列表，还可以是连接顶点的列表，如下所示:

(2,3,4,8,5)
(6,5,8)
(2,5,7,1)
(7,6,5)

在这种情况下，顶点的顺序不能是随机的(顶点列表应该是循环序列)但方向(顺时针或逆时针)仍然无关紧要。所以 4 边形也可以是 (5,2,1,7) 或 (1,7,5,2) 等等。

什么是高效(快速)构造多边形列表的方法，定义在边或顶点中？

Answer 1

对于每条边 vw，生成两个半边 v->w 和 w->v。按头部划分这些(x->y 的头部是y)。在每个分区内，按角度排序(如果使用比较排序，则有一种避免触发的方法)。

对于您的示例图，结果是

7->1, 2->1
1->2, 5->2, 3->2
2->3, 4->3
8->4, 3->4
7->5, 6->5, 8->5, 2->5
8->6, 5->6, 7->6
6->7, 5->7, 1->7
5->8, 6->8, 4->8

.现在，定义一个排列，其中 v->w 映射到包含 w->v 的列表中 w->v 之后的半边(必要时环绕)。这种排列的循环是多边形。

例如，5->8 映射到 2->5(在 8->5 之后)映射到 3 ->2(在5->2之后)映射到4->3(在2->3之后)映射到8->4(在 3->4 之后)映射到 5->8(在 4->8 之后) >).