Voronoi图的最简单的算法来实现？ [英] Easiest algorithm of Voronoi diagram to implement?

问题描述

什么是容易的算法来实现Voronoi图？

What are the easy algorithms to implement Voronoi diagram?

我找不到任何算法，特别是在虚拟的形式。请分享Voronoi图算法，教程等。

I couldn't find any algorithm specially in pseudo form. Please share some links of Voronoi diagram algorithm, tutorial etc.

在此先感谢。

推荐答案

这是简单的算法来计算一个点集的德劳内三角是的翻转边缘。由于Delaunay三角剖分是Voronoi图的双图，可以从线性时间的三角构造图。

An easy algorithm to compute the Delaunay triangulation of a point set is flipping edges. Since a Delaunay triangulation is the dual graph of a Voronoi diagram, you can construct the diagram from the triangulation in linear time.

不幸的是，在运行翻转方法的时间的最坏情况是O（n ^ 2）。更好的算法，如财富的行扫存在，这需要为O（n log n）的时间。这有点棘手的落实，虽然。如果你懒（像我），我会建议找一个德劳内三角的现有实现，使用它，然后计算出偶图。

Unfortunately, the worst case running time of the flipping approach is O(n^2). Better algorithms such as Fortune's line sweep exist, which take O(n log n) time. This is somewhat tricky to implement though. If you're lazy (as I am), I would suggest looking for an existing implementation of a Delaunay triangulation, use it, and then compute the dual graph.

在一般情况下，一本好书的话题是计算几何通过德伯格等人。

In general, a good book on the topic is Computational Geometry by de Berg et al.

这篇关于Voronoi图的最简单的算法来实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！