Voronoi图最容易实现的algorithm?

什么是简单的algorithm来实现Voronoi图?

我无法find任何伪格式的algorithm。 请分享一些Voronoi图algorithm,教程等的链接

计算点集的Delaunay三angular剖分的简单algorithm是翻转边缘 。 由于Delaunay三angular剖分是Voronoi图的对偶图,因此可以用线性时间从三angular剖分构build图。

不幸的是,翻转方法的最坏情况运行时间是O(n ^ 2)。 存在更好的algorithm,例如Fortune的行扫描,其花费O(n log n)时间。 虽然这实现起来有些棘手。 如果你懒惰(就像我一样),我会build议寻找现有的Delaunay三angular剖分实现,使用它,然后计算双图。

一般来说,关于这个话题的一本好书是由de Berg等人的Computational Geometry 。

Bowyer-Watsonalgorithm很容易理解。 这是一个实现: http : //paulbourke.net/papers/triangulate/ 。 这是一个点的一个delaunay三angular剖分,但你可以使用它来获得双列的delaunay,即一个voronoi图。 BTW。 最小生成树是delaunay三angular剖分的一个子集。

最简单的? 这是暴力方法:对于输出中的每个像素,遍历所有点,计算距离,使用最接近的点。 尽可能慢,但很简单。 如果performance不重要,那么这个工作就完成了。 我自己一直在做一个有趣的改进,但仍然在寻找是否有其他人有相同的(相当明显的)想法。

维基百科页面( http://en.wikipedia.org/wiki/Voronoi_diagram )有一个algorithm部分,链接到用于实现Voronoi图的algorithm。

在Stephan Fortune / Shane O'Sullivan的C和C ++中,有一个免费的voronoi实现:

VoronoiDiagramGenerator.cpp VoronoiDiagramGenerator.h 

你会在很多地方find它。 即在http://www.skynet.ie/~sos/masters/

构buildVoronoi图的最有效的algorithm是Fortunealgorithm 。 它运行在O(n log n)。

这里是他在C中的参考实现的链接。

就我个人而言,我真的很喜欢Bill Simons和Carson Farmer的python实现 ,因为我发现它更容易扩展。

这里是一个JavaScript实现,使用四叉树,并允许增量构造。

http://code.google.com/p/javascript-voronoi/

虽然最初的问题是关于如何实施Voronoi,但是当我search这个主题的信息时,我发现有一篇文章说了以下内容,这将节省我很多时间:

在互联网上有很多“近乎正确”的C ++代码来实现Voronoi图。 当种子点非常密集时,大多数很less触发失败。 我会build议testing你在网上find的任何代码,并在你浪费太多时间之前,用你希望在你的项目中使用的点数来广泛地testing它。

我在网上find的最好的实现是从这里链接的MapManager程序的一部分: http : //www.skynet.ie/~sos/mapviewer/voronoi.php它主要是工作,但我处理间歇性图腐败订单10 ^ 6点。 我一直没有弄清楚腐败正在如何蔓延。

昨晚我发现这个: http : //www.boost.org/doc/libs/1_53_0_beta1/libs/polygon/doc/voronoi_main.htm “Boost.Polygon Voronoi图书馆”。 它看起来很有希望。 这与基准testing来certificate它的准确性,并有很好的性能。 图书馆有一个适当的界面和文件。 我很惊讶,我之前没有find这个图书馆,所以我在这里写了一些。 (我在研究中早期阅读这篇文章。)

这是最快的 – 这是一个简单的voronoi,但它看起来不错。 它将空格划分为一个网格,在随机放置的每个网格单元中放置一个点,并沿网格移动,检查3×3个单元格,以查找它与相邻单元格的关系。

没有渐变,速度更快。

你可能会问最简单的三维voronoi会是什么。 这将是很有趣的知道。 可能是3x3x3单元格和检查渐变。

http://www.iquilezles.org/www/articles/smoothvoronoi/smoothvoronoi.htm

 float voronoi( in vec2 x ) { ivec2 p = floor( x ); vec2 f = fract( x ); float res = 8.0; for( int j=-1; j<=1; j++ ) for( int i=-1; i<=1; i++ ) { ivec2 b = ivec2( i, j ); vec2 r = vec2( b ) - f + random2f( p + b ); float d = dot( r, r ); res = min( res, d ); } return sqrt( res ); } 

和chebychev距离一样。 你可以从这里使用一个random2f二维浮点噪声:

https://www.shadertoy.com/view/Msl3DM

编辑:我已经把它转换成C代码

这是一段时间以来,为了那些谁的利益,我相信这是很酷的:

  function rndng ( n: float ): float {//random number -1, 1 var e = ( n *321.9)%1; return (e*e*111.0)%2-1; } function voronoi( vtx: Vector3 ) { var px = Mathf.Floor( vtx.x ); var pz = Mathf.Floor( vtx.z ); var fx = Mathf.Abs(vtx.x%1); var fz = Mathf.Abs(vtx.z%1); var res = 8.0; for( var j=-1; j<=1; j++ ) for( var i=-1; i<=1; i++ ) { var rx = i - fx + nz2d(px+i ,pz + j ) ; var rz = j - fz + nz2d(px+i ,pz + j ) ; var d = Vector2.Dot(Vector2(rx,rz),Vector2(rx,rz)); res = Mathf.Min( res, d ); } return Mathf.Sqrt( res ); } 

实际上在https://rosettacode.org/wiki/Voronoi_diagram上有25种不同语言的实现;

例如对于Java:

 import java.awt.Color; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.geom.Ellipse2D; import java.awt.image.BufferedImage; import java.io.File; import java.io.IOException; import java.util.Random; import javax.imageio.ImageIO; import javax.swing.JFrame; public class Voronoi extends JFrame { static double p = 3; static BufferedImage I; static int px[], py[], color[], cells = 100, size = 1000; public Voronoi() { super("Voronoi Diagram"); setBounds(0, 0, size, size); setDefaultCloseOperation(EXIT_ON_CLOSE); int n = 0; Random rand = new Random(); I = new BufferedImage(size, size, BufferedImage.TYPE_INT_RGB); px = new int[cells]; py = new int[cells]; color = new int[cells]; for (int i = 0; i < cells; i++) { px[i] = rand.nextInt(size); py[i] = rand.nextInt(size); color[i] = rand.nextInt(16777215); } for (int x = 0; x < size; x++) { for (int y = 0; y < size; y++) { n = 0; for (byte i = 0; i < cells; i++) { if (distance(px[i], x, py[i], y) < distance(px[n], x, py[n], y)) { n = i; } } I.setRGB(x, y, color[n]); } } Graphics2D g = I.createGraphics(); g.setColor(Color.BLACK); for (int i = 0; i < cells; i++) { g.fill(new Ellipse2D .Double(px[i] - 2.5, py[i] - 2.5, 5, 5)); } try { ImageIO.write(I, "png", new File("voronoi.png")); } catch (IOException e) { } } public void paint(Graphics g) { g.drawImage(I, 0, 0, this); } static double distance(int x1, int x2, int y1, int y2) { double d; d = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); // Euclidian // d = Math.abs(x1 - x2) + Math.abs(y1 - y2); // Manhattan // d = Math.pow(Math.pow(Math.abs(x1 - x2), p) + Math.pow(Math.abs(y1 - y2), p), (1 / p)); // Minkovski return d; } public static void main(String[] args) { new Voronoi().setVisible(true); } } 

检查由理查德·弗兰克斯在他的问题的答案伪码提出的暴力解决scheme如何得到一个Voronoi图给定其点集和德劳内三angular形?

最简单的algorithm来自于voronoi图的定义:“将具有n个点的平面划分成凸多边形,使得每个多边形恰好包含一个生成点,并且给定多边形中的每个点比其它生成点更接近其生成点。 “来自wolfram的定义。

这里的重要部分是关于每个点比任何其他点都更接近发生点,从这里algorithm是非常简单的:

  1. 有一个生成点的数组。
  2. 循环遍历canvas上的每个像素。
  3. 对于每个像素寻找最接近的生成点。
  4. 取决于你想得到什么图表颜色的像素。 如果要用边框分隔图表,请检查第二个到最近的点,然后检查它们与边界颜色的差异和颜色(如果它小于某个值)。

如果你想要一个颜色图,然后有一个颜色与每个生成点关联,并为每个像素着色,这是最接近的生成点相关的颜色。 这就是它,它不是有效的,但很容易实现。

在Fortune的algorithm/扫描线algorithm的基础上,在谷歌代码上find这个优秀的C#库

https://code.google.com/p/fortune-voronoi/

你只需要创build一个列表。 Vector可以通过传入两个数字(坐标)作为float来创build。 然后通过列表Fortune.ComputeVoronoiGraph()

您可以从这些维基百科页面中更多地了解algorithm的概念:

http://en.wikipedia.org/wiki/Fortune%27s_algorithm

http://en.wikipedia.org/wiki/Sweep_line_algorithm

虽然有一件事我不能理解的是如何创build一个部分无限边缘的线条(不太了解坐标几何:-))。 如果有人知道,请让我知道。

有几个VoronoiDiagramGenerator.cpp / h在附近

如果你计划一个实时的沉重的应用程序,要求所有的一些严重的内存清理

像所有的财富扫描线至less有非常接近的问题

从浮动移动到双倍

– 在开始时删除“相同”的点

然后在极less数情况下尝试处理精确度问题