Easiest algorithm of Voronoi diagram to implement?

问题:

What are the easy algorithms to implement Voronoi diagram?

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

回答1:

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.

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.

回答2:

Easiest? That's the brute-force approach: For each pixel in your output, iterate through all points, compute distance, use the closest. Slow as can be, but very simple. If performance isn't important, it does the job. I've been working on an interesting refinement myself, but still searching to see if anyone else has had the same (rather obvious) idea.

回答3:

The Bowyer-Watson algorithm is quite easy to understand. Here is an implementation: http://paulbourke.net/papers/triangulate/. It's a delaunay triangulation for a set of points but you can use it to get the dual of the delaunay,i.e. a voronoi-diagram. BTW. the minimum spanning tree is a subset of delaunay triangulation.

回答4:

The Wikipedia page (http://en.wikipedia.org/wiki/Voronoi_diagram) has an Algorithms section with links to algorithms for implementing Voronoi diagrams.

回答5:

The most effecient algorithm to construct a voronoi diagram is Fortune's algorithm. It runs in O(n log n).

Here is a link to his reference implementation in C.

Personally I really like the python implementation by Bill Simons and Carson Farmer, since I found it easier to extend.

回答6:

There is a freely availble voronoi implementation for 2-d graphs in C and in C++ from Stephan Fortune / Shane O'Sullivan:

VoronoiDiagramGenerator.cpp 

VoronoiDiagramGenerator.h 

You'll find it at many places. I.e. at http://www.skynet.ie/~sos/masters/

回答7:

Here is a javascript implementation that uses quat-tree and allows incremental construction.

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

回答8:

While the original question asks about how to implement Voronoi, had I found a post that said the following when I was searching for info on this subject it would have saved me a lot of time:

There's a lot of "nearly correct" C++ code on the internet for implementing Voronoi diagrams. Most have rarely triggered failures when the seed points get very dense. I would recommend to test any code you find online extensively with the number of points you expect to use in your finished project before you waste too much time on it.

The best of the implementations I found online was part of the MapManager program linked from here: http://www.skynet.ie/~sos/mapviewer/voronoi.php It mostly works but i'm getting intermittent diagram corruption when dealing with order 10^6 points. I have not been able to work out exactly how the corruption is creeping in.

Last night I found this: http://www.boost.org/doc/libs/1_53_0_beta1/libs/polygon/doc/voronoi_main.htm "The Boost.Polygon Voronoi library". It looks very promising. This comes with benchmark tests to prove it's accuracy and has great performance. The library has a proper interface and documentation. I'm surprised I didn't find this library before now, hence my writing about it here. (I read this post early in my research.)

回答9:

This is the fastest possible - it's a simple voronoi but it looks great. It divides spaces into a grid, places a dot in each grid cell randomly placed and moves along the grid checking 3x3 cells to find how it relates to adjacent cells.

It's faster without the gradient.

You may ask what the easiest 3d voronoi would be. It would be fascinating to know. Probably 3x3x3 cells and checking gradient.

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

and here is the same with chebychev distance. you can use a random2f 2d float noise from here:

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

edit: I have converted this to C like code

This was a while ago, for the benefit of those who what it, i believe this is cool:

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

回答10:

Actually there are implementations for 25 different languages available on https://rosettacode.org/wiki/Voronoi_diagram

E.g for 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);
    }
}

回答11:

Check brute-force solution presented with pseudo-code by Richard Franks in his answer on the question How do I derive a Voronoi diagram given its point set and its Delaunay triangulation?

回答12:

The simplest algorithm comes from the definition of a voronoi diagram: "The partitioning of a plane with n points into convex polygons such that each polygon contains exactly one generating point and every point in a given polygon is closer to its generating point than to any other." definition from wolfram.

The important part here is about every point being closer to the generating point than any other, from here the algorithm is very simple:

1. Have an array of generating points.
2. Loop through every pixel on your canvas.
3. For every pixel look for the closest generating point to it.
4. Depending on what diagram you wish to get color the pixel. If you want a diagram separated with a border, check for the second to closest point, then check their difference and color with the border color if it's smaller than some value.

If you want a color diagram then have a color associated with every generating point and color every pixel with it's closest generating point associated color. And that's about it, it's not efficient but very easy to implement.

回答13:

Found this excellent C# library on google code based on Fortune's algorithm/Sweep line algorithm

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

You just need to create a List. A Vector can be created by passing in two numbers (coordinates) as float. Then pass the list into Fortune.ComputeVoronoiGraph()

You can understand the concept of the algorithm a bit more from these wikipedia pages:

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

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

Though one thing I was not able to understand is how to create a line for Partially Infinite edges (don't know much about coordinate geometry :-)). If someone does know, please let me know that as well.

回答14:

If you are trying to draw it to an image, you can use a queue-based flood-filling algorithm.

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; 

}

Using a queue will ensure that regions spread in parallel, minimizing total number of pixel visits. If you use a stack the first point will fill the whole image, then the second will fill any pixels closer to it than the first point. This will continue, greatly increasing visit counts. Using a FIFO queue processes pixels in the order that they are pushed. The resulting images will be roughly the same whether you use stack or queue, but the big-O for queue is far closer to linear (in relation to number of image pixels) than the stack algoritm's big-O. The general idea is that the regions will spread at the same rate and collisions will generally happen exactly at points that correspond to region boundaries.

回答15:

there is several VoronoiDiagramGenerator.cpp/h around

requiring all some serious clean up on memory if you plan a realtime heavy app

like all fortune sweepline have trouble with very close points at least

-move from float to double

-remove "identical" point at start

-then try to deal with precision issue in rare case