Incremental Voronoi construction

Jul 17, 2014 at 10:49 AM

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


Here, I've moved it to the right:


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 : has done something similar in javascript - I think it's a bespoke algorithm..

Any feedback greatly appreciated


Jul 17, 2014 at 11:59 AM
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
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 12: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)
.. If i remember correctly, it was still using the older Points class.
Jul 19, 2014 at 12:27 PM
Edited Jul 19, 2014 at 12:27 PM
I've made some slides for the bounded case:

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 3: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.