relax, v.
10. Chiefly Physics. To return towards a state of equilibrium. (OED)

Here’s the planar analog of my earlier post Distributing Points on the Sphere. This time I’ve ported Steve Fortune’s C implementation of his sweepline algorithm for Voronoi diagrams, and applied Lloyd’s algorithm to change the input values (the point locations) iteratively so the output function (the stress or energy) approaches a minimum. Lloyd’s algorithm works by repeatedly computing the Voronoi diagram and moving each point to the centroid of its region. Soon the points converge to an even distribution. You can see this in action by starting the app by clicking on the image, and then pressing the “r” key.

While I was at it I built out some more of the basic Voronoi-related geometric structures: the Delaunay triangulation, the convex hull, the onion, and the minimum spanning tree.

I’ve had fun playing with this app, changing the display options while moving, adding, or removing points. I hope you enjoy it.

(The app is built for Flash Player 10.)