Voronoi图的最简单的算法来实现？ [关闭] Voronoi图的最简单的算法来实现？ [关

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

我不能在模拟性专门找到任何算法。 请分享Voronoi图算法的一些链接，教程等。

Answer 1:

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

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

在一般情况下，一本好书的话题是计算几何由德Berg等人。

Answer 2:

最简单的？ 这是蛮力的方法：对于你的输出的每个像素，遍历所有的点，计算距离，使用最接近。 慢如可以，但很简单。 如果性能并不重要，它的工作。 我一直有一个有趣的细化自己，但仍在寻找，看是否有人有相同的（相当明显）的想法。

Answer 3:

该鲍耶 - 沃森算法是很容易理解。 这是一个实现： http://paulbourke.net/papers/triangulate/ 。 它是一组点的Delaunay三角网，但你可以用它来获得双德劳内，即维诺 - 图的。 BTW。 最小生成树为德劳内三角的一个子集。

Answer 4:

最effecient算法构建Voronoi图是财富的算法 。 它运行在为O（n log n）的。

这里是他的一个链接在C基准执行 。

我个人非常喜欢Python实现由比尔·西蒙斯和卡森农民，因为我发现它更容易扩展。

Answer 5:

维基百科页面（ http://en.wikipedia.org/wiki/Voronoi_diagram ）与链接算法实现Voronoi图的算法部分。

Answer 6:

有一种在C和C ++编写从斯蒂芬财富/沙恩奥沙利文2-d的曲线图可自由availble的沃罗诺伊实现：

VoronoiDiagramGenerator.cpp 

VoronoiDiagramGenerator.h 

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

Answer 7:

下面是一个使用季铵盐树，并允许增量建设一个JavaScript实现。

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

Answer 8:

虽然原来的问题询问有关如何实现维诺，有我找到了一个职位，说，当我正在寻找在这个问题上，将有救了我大量的时间信息如下：

有互联网实现Voronoi图上有很多“接近正确的” C ++代码。 大多数人都很少引发故障时，种子点变得非常密集。 我建议你测试你希望在你完成的项目使用的点数在网上找到大量的任何代码，你浪费太多时间在它之前。

最好的实现的我在网上找到了从这里链接的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维诺库”。 它看起来非常有前途的。 这自带Benchmark测试，以证明它的准确性和具有卓越的性能。 图书馆有一个适当的界面和文档。 我很惊讶，我现在才没找到这个库，因此我写关于它在这里。 （我在我的研究早期阅读这篇文章。）

Answer 9:

这是最快的可能 - 这是一个简单的维诺，但它看起来很棒。 它把空格放入格，则以在每个网格单元沿网格检查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:

其实有可用的实现了25种不同的语言https://rosettacode.org/wiki/Voronoi_diagram

例如，对于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);
    }
}

Answer 11:

请与伪代码所提交的蛮力解决方案理查德·弗兰克斯在他的回答上这个问题我如何获得赋予其点集和德劳内三角Voronoi图？

Answer 12:

最简单的算法来自维诺图的定义：“与n个点的平面内的成凸多边形分隔，使得每个多边形正好包含一个生成点和在给定的多边形的每个点是比任何其它接近其生成点从钨“的定义。

这里最重要的部分是每一个点是比任何其他更接近生成点，从这里的算法非常简单：

1. 有生成点的阵列。
2. 通过你的画布上的每个像素循环。
3. 对于每一个像素寻找最接近的生成指向它。
4. 根据你的愿望图来获得色彩像素。 如果你想用一个边界分开的示意图，检查第二至最接近的点，然后检查他们的差异和颜色与边框颜色，如果它比一些值。

如果你想，那么色彩图与每一个生成点相关联的颜色和颜色的每个像素与它的最近的生成点相关联的颜色。 这就是它，它的效率不高，但很容易实现。

Answer 13:

发现在谷歌代码基于财富的算法/扫描线算法，这个优秀的C＃库

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

你只需要创建一个列表。 的矢量，可以通过使在两个数字（坐标）作为浮动来创建。 然后通过列表分为Fortune.ComputeVoronoiGraph（）

你可以理解的算法更从这些页面维基百科一点的概念：

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

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

虽然有一两件事我是无法理解的是如何创造无穷部分边缘的线（不知道太多关于坐标几何:-)）。 如果有人知道，请让我知道这一点。

Answer 14:

如果你试图把它拖到一个图像，你可以使用基于队列的洪水填充算法。

Voronoi::draw(){
    // define colors for each point in the diagram;
    // make a structure to hold {pixelCoords,sourcePoint} queue objects
    // initialize a struct of two closest points for each pixel on the map
    // initialize an empty queue;

    // for each point in diagram:
        // for the push object, first set the pixelCoords to pixel coordinates of point;
        // set the sourcePoint of the push object to the current point;
        // push the queue object;

    // while queue is not empty:
        // dequeue a queue object;
        // step through cardinal neighbors n,s,e,w:
            // if the current dequeued source point is closer to the neighboring pixel than either of the two closest:
                // set a boolean doSortAndPush to false;
                // if only one close neighbor is set:
                    // add sourcePoint to closestNeighbors for pixel;
                    // set doSortAndPush to true;
                // elif sourcePoint is closer to pixel than it's current close neighbor points:
                    // replace the furthest neighbor point with sourcePoint;
                    // set doSortAndPush to true;
                // if flag doSortAndPush is true:
                    // re-sort closest neighbors; 
                    // enqueue object made of neighbor pixel coordinates and sourcePoint;

    // for each pixel location:
        // if distance to closest point within a radius for point drawing:
            // color pixel the point color;
        // elif distances to the two closest neighbors are roughly equal:
            // color the pixel to your border color;
        // else 
            // color the pixel the color of the point's region; 

}

使用队列将确保区域并行传播，最大限度地减少像素的访问总次数。 如果使用堆栈中的第一个点，将填补整个图像，那么第二个将填充任何像素比第一点更靠近它。 这将继续，大大增加访问计数。 使用FIFO队列中，他们推动了顺序处理的像素。 所得到的图像将是大致相同的无论使用栈或队列，但是大-O为队列远远大于堆algoritm的大O接近线性（相对于图像的像素数）。 总的想法是，该地区将在同样的速度传播，碰撞通常会在对应区域的边界点恰好发生。

文章来源: Easiest algorithm of Voronoi diagram to implement? [closed]