Saturday, February 02, 2013

Smooth Voronoi Diagrams

The paper.js project has a cool demo with polygon smoothing on a Voronoi diagram. For fun I decided to implement my own version from scratch.
The first step was to implement a system for polygon smoothing using Bézier splines. Here is a demo of the technique (you can click/drag to interact with the demo). The blue points are the original polygon vertices. For the Bézier spline, the midpoints become the vertices and the original vertices become the control points (making this a quadratic Bézier spline).

To compute the Voronoi diagram polygons I used this excellent JavaScript library. Next, I computed polygon centroids using this formula. To create the gap between polygons I scaled the vertices towards each centroid. Here is the final demo: The blue dots are the Voronoi seeds and the green dots are the polygon centroids. You can click to create new Voronoi seeds (or drag to move seeds).

I am not completely happy with the demo since there are some "jumps" in the animation when new vertices are added to a polygon. I tried several ideas to make the polygon smoothing more robust to adding vertices, but couldn't find anything I was happy with. Imagine adding a new polygon vertex exactly on top of an existing one. It doesn't change the shape of the original polygon, but it significantly changes the shape of the smoothed version using my algorithm. Intuitively it seems like something that would be easy to overcome, but I haven't been able to figure it out.

No comments: