最简单的Voronoi图算法实现？

Question

实现Voronoi图的简单算法是什么？

我找不到任何特殊的伪形式算法.请分享Voronoi图算法,教程等的一些链接.

Answer 1

计算点集的Delaunay三角剖分的简单算法是翻转边缘.由于Delaunay三角剖分是Voronoi图的双重图,因此您可以在线性时间内从三角剖分构造图.

不幸的是,翻转方法的最坏情况运行时间是O(n ^ 2).存在更好的算法,例如Fortune的行扫描,这需要O(n log n)时间.尽管如此,这有点棘手.如果你是懒惰的(就像我一样),我建议寻找Delaunay三角测量的现有实现,使用它,然后计算双图.

一般来说,关于这个主题的好书是de Berg等人的计算几何.

Answer 2

最简单的？这是蛮力方法:对于输出中的每个像素,迭代所有点,计算距离,使用最接近的.尽可能慢,但非常简单.如果表现不重要,那就完成了工作.我自己一直在努力进行一项有趣的改进,但仍然在寻找是否有其他人有同样的(相当明显的)想法.

Answer 3

Bowyer-Watson算法很容易理解.这是一个实现:http://paulbourke.net/papers/triangulate/.对于一组点,它是一个delaunay三角剖分,但是你可以使用它来获得delaunay的双重关系,即voronoi图.BTW.最小生成树是delaunay三角剖分的子集.

Answer 4

构建voronoi图的最有效算法是Fortune的算法.它以O(n log n)运行.

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

我个人非常喜欢Bill Simons和Carson Farmer 的python实现,因为我发现它更容易扩展.

Answer 5

维基百科页面(http://en.wikipedia.org/wiki/Voronoi_diagram)有一个算法部分,其中包含用于实现Voronoi图的算法的链接.

Answer 6

Stephan Fortune/Shane O'Sullivan为C和C++中的二维图提供了一个免费的voronoi实现:

VoronoiDiagramGenerator.cpp 

VoronoiDiagramGenerator.h 

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

Answer 7

这是一个使用quat-tree并允许增量构造的javascript实现.

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

Answer 8

虽然最初的问题是关于如何实现Voronoi,但是当我在搜索关于这个主题的信息时,我发现了一个帖子说下面的内容,这会给我节省很多时间:

互联网上有很多"几乎正确"的C++代码用于实现Voronoi图.当种子点变得非常密集时,大多数都很少触发失败.我建议您在完成的项目中使用您希望在完成的项目中使用的点数来广泛测试您在线找到的任何代码,然后再浪费太多时间.

我在网上找到的最好的实现是从这里链接的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库".看起来很有希望.这带来了基准测试,以证明它的准确性和卓越的性能.该库具有适当的界面和文档.我很惊讶我之前没有找到这个库,所以我在这里写了这篇文章.(我在研究的早期就读过这篇文章.)

Answer 9

这是最快的——它是一个简单的 voronoi 但它看起来很棒。它将空间划分为一个网格，在每个随机放置的网格单元格中放置一个点，并沿着网格检查 3x3 单元格以查找它与相邻单元格的关系。

没有梯度它更快。

您可能会问什么是最简单的 3d 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 );
}

这与切比雪夫距离相同。您可以从这里使用 random2f 2d 浮动噪声：

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 );
 }

Answer 10

实际上，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);
    }
}