Voronoi Brute Force

Replies to This Discussion

Permalink Reply by David Rutten on September 26, 2009 at 11:16am

Hi Gennifer,

A single cell in a voronoi diagram can be constructed by cutting the (infinite) plane repeatedly with midlines and then tossing the piece that was cut off:

When there are 1000 points in the set, this method will have to be performed 999 times for each voronoi cell. That's 1000 × 999 = nearly a million intersections of polygons with rays which will take a long time. This is the brute force approach.

The default algorithm, which is much, much faster but sometimes gets confused near the edges of the set, is to only consider the midlines between the local point and the points in the set which are connected with the local point via a mesh edge when the delaunay triangulation of the set is computed first.

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

Permalink Reply by P. Casey Mahon on September 28, 2009 at 11:55am

David,

Is there anyway to set up the voronoi to find nearest points and use those to generate the cells. My students are replicating biological systems within grasshopper all semester and a lot of them are looking into ways of replicating venation systems in the leaves of plants, which I think this would be helpful for. Also is there a way to make this function recursive (voronoi's within voronoi's)

Permalink Reply by David Rutten on September 28, 2009 at 2:53pm

At the moment not. There is only 1 Voronoi component and it doesn't expose these functions.

If you start to ignore certain points in the set when making a voronoi diagram, for example by only considering nearby points, then the resulting diagram will no longer be watertight. You'll get overlapping cells.

The recursive option is definitely possible. The problem is merely one of control. How do you want to define these different recursive layers? Do you supply different points for each level?

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

Permalink Reply by P. Casey Mahon on September 28, 2009 at 3:12pm

David,
Thanks for your great response. I have done experiments with manually adding more random points within a voronoi cell to create voronoi's within voronoi's. I guess what I'm more interested in happening is setting up a system where a hierarchy could occur within the system. Most of the research I've looked at has come from this great paper even though I have to admit most of it is over my head. Here's a link in case your curious, the author's explain how using what they are calling Urquhart's Algorithm to test points neighborhood sets.Thanks for all of your help, creating this amazing plug-in, and being super involved with this discussion group.

http://algorithmicbotany.org/papers/venation.sig2005.pdf

- Casey

Permalink Reply by h on January 14, 2014 at 4:55pm

Did you ever figure out the implementation of this? I've been looking at this paper for the past couple of days. I have the basic algorithm worked out, but without Urquhart's Algorithm it is basically useless.

Googling "Python Urquhart" brought me right back here hahaha.