我怎样才能得到这个Voronoi图数据的单元字典？ [英] How can I get a dictionary of cells from this Voronoi Diagram data?

问题描述

使用voronoi / delaunay图生成库在此程序中找到，该程序基于Fortune原始实现的他的算法，用一组随机点作为输入数据，我可以得到以下输出数据：

1. Delaunay Triangulation ，这意味着对于每个输入点，我可以看到哪些输入点是其邻居。他们似乎没有任何特定的顺序。


2. 来自 Voronoi图 ，我可以一次绘制Voronoi图。再次，显然没有特定的顺序。


3. 一对未点名的点，它似乎与2相同，但排列顺序不同。


4. Voronoi图中形成的顶点列表，显然也没有特定的顺序。

以下是使用此库的程序的测试运行数据示例：

 输入点数：
 0（426.484,175.16）
 1（282.004,231.388）
 2（487.891,353.996）
 3（50.8574,5.02996）
 4（ （387.425,288.533）（277.142,5.15565）
 1（387.425,288.533）（503.484,248.682）
 2（$）
 $ b顶点对：
 0 （237.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线？：
 0（279.477,0）（277.142,5.155565） 
 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.155565）（0,288.161）
 5（387.425,288.533）（503.484,248.682）
 6（277.142,5.155565）（387.425,288.533）
 
德劳内边缘：
 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）
 
顶点：$ b​​ $ b 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顶点的列表？或者，这些信息是否隐藏在我已经给出的数据中？

我的答案的出发点是你用来生成单元格的不是一个库，而是一个写得很整齐的类来包装原本由Fortune自己发布的代码，而不是一个成熟的库。所以，作者实际上并没有预料到你的需求，尽管你想要的信息已经被计算出来了，但它是无法访问的。

在内部，您的输入点作为Site结构的实例存储，并且算法继续创建半边缘，每个边缘都维护着一个引用顶点，它是指向它封入的网站的指针 。沿着半边沿着您自然环绕的封闭网站 - 正是您所需要的。

为了访问这些数据，我建议修改或扩展VoronoiDiagramGenerator类;我将通过创建一个带有Site指针的散列表作为键和一个HalfEdge指针作为值来完成。然后，修改generateVoroni方法，在调用voronoi之后立即插入新代码：

 对于ELHash中的每个HalfEdge 
为当前半边的网站获取表格条目
如果网站在表格中有空值HalfEdge引用
设置当前HalfEdge引用
结束如果
结束对于每个
  

...还有你的字典。单一的半边将允许你走围绕相关网站的多边形的周长，我认为这是你要求的。你的下一个问题是要有效地发现哪个包含了一些新的数据点 - 但这是另一个问题:-)。我希望你会考虑分享你完成的课程 - 它应该比基础课程更有用。

编辑：
这是一个很棒的演讲介绍上面所有的图片都是这样说的： http://ima.udg.es/~sellares/ ComGeo / Vor2D_1.ppt ：

• Voronoy图的定义


• （请参阅下面的图片）


• 图片中的Fortune算法

一个C＃实现，它可以帮助你检索字典，如上所述： http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C

Using the voronoi/delaunay diagram generation library found in this program, which is based on Fortune's original implementation of his algorithm, with a random set of points as input data, I am able to get the following output data:

1. A list of the edges from the Delaunay Triangulation, meaning that for each input point, I can see which input points are its neighbors. They don't appear to be in any particular order.
2. A list of the vertex pairs from the Voronoi Diagram, which I can use to draw the Voronoi diagram one line at a time. Again, apparently in no particular order.
3. An unnamed list of pairs of points, which seems to just be the same list as 2, but in a different order.
4. A list of the vertices formed in the Voronoi Diagram, also apparently in no particular order.

Here is an example of data from a test run of my program using this library:

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)

While the above data is adequate if all I need is to draw the Voronoi and Delaunay diagrams, it is not enough information for the actual work I am trying to do with these diagrams. What I need is a dictionary of polygons formed by the Voronoi vertices, indexed by the input point that each polygon was formed around. Preferably, for each polygon, these points would be sorted in clockwise order.

With the above information, I could implicitly assign data to each region, assign data to corners if necessary, tell which regions share edges (using the Delaunay edges), and do analysis accordingly.

So in short, how can I use the data available to me to put together a dictionary in which the key is one of the input points, and the data indexed by that key is a list of the Voronoi vertices that form the surrounding polygon? Or alternatively, is that information somewhere implicit in the data I've been given?

解决方案

Fortune's algorithm is O(n log n) - but your code will be O(n^2), if you try to reconstruct cells brute-force fashion as proposed by Alink.

The starting point for my answer is that what you are using to generate the cells is not a library, but rather is just a class written to neatly wrap up the code originally presented by Fortune himself, and not actually a mature library. So, the author in fact hasn't anticipated your needs, and although the information you want has been computed, it isn't accessible.

Internally, your input points are stored as instances of the "Site" struct, and the algorithm proceeds to create half-edges, each of which maintains a reference "vertex" which is a pointer to the Site it encloses. Stepping along half-edges you naturally circumnavigate the enclosed Site - exactly what you need.

To access this data, I suggested modifying or extending the VoronoiDiagramGenerator class; I would do it by creating a hash table with Site pointers as the key and a single HalfEdge pointer as the value. Then, modify the generateVoroni method, inserting your new code immediately following the call to voronoi:

For each HalfEdge in ELHash
         Get table entry for current half edge's Site
         If site in table has null HalfEdge reference
            set current HalfEdge reference
         End If
End For each

...and there is your dictionary. That single half-edge will allow you to "walk" the perimeter of the polygon enclosing the related site, which I think is what you asked for. Your next problem will be to efficiently discover which polygon encloses some new data point - but that is another question :-). I hope you'll consider sharing your completed class - it should be a significantly more useful than the base class.

Edit: Here is an excellent presentation descibing all said above in pictures: http://ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt:

• definition of Voronoy Diagram
• tree of of half-edges (see pics. below)
• Fortunes algorithm in pictures

And here is a C# implementation which could help you to retrieve the dictionary, as proposed above: http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C

这篇关于我怎样才能得到这个Voronoi图数据的单元字典？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！