使用找到的voronoi/delaunay图生成库在这个节目中 http://sourceforge.net/projects/mapmanager/,这是基于《财富》最初的实施他的算法 http://en.wikipedia.org/wiki/Fortune%27s_algorithm,使用一组随机点作为输入数据,我可以获得以下输出数据:
-
的边列表德劳内三角测量 http://en.wikipedia.org/wiki/Delaunay_triangulation,这意味着对于每个输入点,我可以看到哪些输入点是其邻居。它们似乎没有任何特定的顺序。
-
顶点对的列表沃罗诺伊图 http://en.wikipedia.org/wiki/Voronoi_diagram,我可以用它一次一行绘制 Voronoi 图。同样,显然没有特定的顺序。
-
未命名的点对列表,这似乎与 2 是相同的列表,但顺序不同。
-
维诺图中形成的顶点列表,显然也没有特定的顺序。
以下是使用此库测试运行我的程序的数据示例:
Input points:
0 (426.484, 175.16)
1 (282.004, 231.388)
2 (487.891, 353.996)
3 (50.8574, 5.02996)
4 (602.252, 288.418)
Vertex Pairs:
0 (387.425, 288.533) (277.142, 5.15565)
1 (387.425, 288.533) (503.484, 248.682)
2 (277.142, 5.15565) (0, 288.161)
3 (387.425, 288.533) (272.213, 482)
4 (503.484, 248.682) (637.275, 482)
5 (503.484, 248.682) (642, 33.7153)
6 (277.142, 5.15565) (279.477, 0)
Voronoi lines?:
0 (279.477, 0) (277.142, 5.15565)
1 (642, 33.7153) (503.484, 248.682)
2 (503.484, 248.682) (637.275, 482)
3 (387.425, 288.533) (272.213, 482)
4 (277.142, 5.15565) (0, 288.161)
5 (387.425, 288.533) (503.484, 248.682)
6 (277.142, 5.15565) (387.425, 288.533)
Delaunay Edges:
0 (282.004, 231.388) (487.891, 353.996)
1 (602.252, 288.418) (487.891, 353.996)
2 (426.484, 175.16) (487.891, 353.996)
3 (426.484, 175.16) (602.252, 288.418)
4 (50.8574, 5.02996) (282.004, 231.388)
5 (426.484, 175.16) (282.004, 231.388)
6 (50.8574, 5.02996) (426.484, 175.16)
Vertices:
0 (277.142, 5.15565)
1 (503.484, 248.682)
2 (387.425, 288.533)
3 (0, 288.161)
4 (272.213, 482)
5 (637.275, 482)
6 (642, 33.7153)
7 (279.477, 0)
虽然如果我只需要绘制 Voronoi 和 Delaunay 图,上述数据就足够了,但对于我尝试使用这些图进行的实际工作来说,这些信息还不够。我需要的是由 Voronoi 顶点形成的多边形字典,由每个多边形围绕形成的输入点进行索引。优选地,对于每个多边形,这些点将按顺时针顺序排序。
有了上述信息,我可以隐式地将数据分配给每个区域,如有必要,将数据分配给角点,告诉哪些区域共享边缘(使用 Delaunay 边缘),并进行相应的分析。
简而言之,如何使用可用的数据来组合一个字典,其中键是输入点之一,并且由该键索引的数据是形成周围多边形的 Voronoi 顶点的列表?或者,该信息是否隐含在我所获得的数据中?