RSS
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.)
[...] rendered some images using the Voronoi Toy from my last [...]
Pingback by nodename » The Name of the Node: Image Fill with Spanning Trees — May 12, 2009 @ 1:31 pm
hi,
very comprhensive example, congats (once again…:))
I’m specially impressed by the onion structure, and the minimum spanning tree could be damn useful to unfold/unproject pictures/objects.
for example: http://www.win.tue.nl/~vanwijk/myriahedral/#paper
great job, keep it up!
Comment by nicoptere — May 13, 2009 @ 6:13 am
impressively fast…pheeeewww!
Comment by Frank — May 15, 2009 @ 3:35 am
[...] Click on the image to see 1000 Voronoi points in motion. Keyboard controls as in the Voronoi Toy. [...]
Pingback by nodename » Mona Voronita — May 18, 2009 @ 9:39 pm
[...] is already well implemented and made available by astatic, also nodename shows it off with his voronoi toy, even though you don’t see the sources. You get a different tool for the same job by HIDIHO!, [...]
Pingback by Controul > Speedy Voronoi diagrams in as3/flash — May 21, 2009 @ 7:23 pm
wow.. impressively fast… and loaded with unique features. Great!
Comment by Batuhan — June 12, 2009 @ 6:33 pm
Hello,
I’m doing a paper on skyline queries, and one of the papers I’m referencing talks about Voronoi diagrams and Convex Hulls. Do you mind if I use your program to show a diagram of these?
Thanks.
Comment by Scott — July 14, 2009 @ 12:21 pm
Go ahead, Scott…
Comment by alan — July 17, 2009 @ 2:40 pm
[...] few people have asked for the code for my Voronoi Toy. I haven’t made the entire program public yet, but I have released the underlying as3delaunay [...]
Pingback by nodename » Roll Over, Delaunay: Voronoi Library Goes Open-Source — December 3, 2009 @ 12:29 am