Easiest algorithm of Voronoi diagram to implement?

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.)

Answer 4

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.

Answer 5

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

Answer 6

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

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