Incremental Voronoi construction

Jul 17, 2014 at 11:49 AM
Hello,

Is there a correct /optimised method to add/remove points to a generated voronoi on the fly?

I'm generating points via noise on a 100x100 grid which is moved around. As the points are updated so is the mesh / voronoi diagram

For example, here is the grid in the center

Image


Here, I've moved it to the right:

Image

Currently I'm just triangulating all the points then creating a new voronoi diagram. Obviously, this is really expensive as every update includes a load of unnecessary calculations. This : https://code.google.com/p/javascript-voronoi/ has done something similar in javascript - I think it's a bespoke algorithm..

Any feedback greatly appreciated

Thanks

R
Coordinator
Jul 17, 2014 at 12:59 PM
I have no plans to add this, but it should be straightforward to do. There are actually only two things to take care of:
  1. Use an efficient spatial index (like a Quadtree) to find the Voronoi cell that contains the new vertex (should be O(log n))
  2. Update all affected cells (should be O(k), k the number of affected cells, usually O(1)). If you google "incremental Voronoi" you'll find details, for example in http://students.info.uaic.ro/~emilian.necula/vor2.pdf
The javascript code seems to do exactly that, using a winged edge datastructure instead of DCEL.

BTW: the new Voronoi code should be safe to use by now and I'd be glad if someone would test it :-)
Jul 17, 2014 at 1:55 PM
The first bit sounds easy, the second a little more challenging ! will give it a go :)

The link makes sense, however math formula is a little over my head - are there any Triangle functions that'd make my life a bit easier? (eg: getting affected cells, calculating new boundaries etc)




PS: I'm testing it the code now :) Had to make a few small changes to get it working. Will dig out my notes later - the one I remember off the top of my head was line 125 of Rectangle.cs being changed to:
   public void Expand(IEnumerable<Vertex> points)
        {
            foreach (var p in points)
            {
                Expand(p);
            }
        }
.. If i remember correctly, it was still using the older Points class.
Coordinator
Jul 19, 2014 at 1:27 PM
Edited Jul 19, 2014 at 1:27 PM
I've made some slides for the bounded case: http://wo80.bplaced.net/projects/voronoi/

No guarantees for completeness, though - only a starting point.

From the other discussion:
If I was creating a new cell from a point inside an existing cell with infinite edges do I need to do anything clever with the bisector calculations ?
Yes, the handling of unbounded cells will be different. And there are at least two cases to consider seperately:
Does the new vertex lie inside or outside the convex hull of the old generators?
Jul 19, 2014 at 4:00 PM
Thank you! Incredibly helpful :)

As the grid is moving, it's most likely that the new vertex will be outside the convex hull of the old generators.