voronoi tutuorial??

Replies to This Discussion

Permalink Reply by David Rutten on November 7, 2010 at 11:08am

Voronoi on Wikipedia.

What do you want to know? What are you trying to accomplish with Voronoi diagrams?

--
David Rutten
david@mcneel.com
Seattle, WA

Permalink Reply by David Rutten on November 7, 2010 at 9:17pm

Well, that is exactly how I solve the Voronoi diagrams, but do note that you'll need a clever Delaunay algorithm that runs relatively fast. There is also something called Fortune's Sweep Line Algorithm (explained here and here) which has a better run-time complexity O(n log n). This algorithm however gives the edges of the graph, not the closed cells, so additional work is required to find the loops. It is quite difficult to implement and the delaunay short-cut seems fast enough for a medium sized collection of points.

However, if you're looking for understanding instead of runtime performance, I suggest you simply cut out the whole delaunay part and construct mid-lines between the active site and every other point in the set (as opposed to just the adjacent points in the delaunay triangulation). Your code will run much slower but it will be much simpler.

--
David Rutten
david@mcneel.com
Seattle, WA