differentiated voronoi

Hi there, I'm looking for a little help on a problem related to the voronoi diagram. I'm looking to write my own definition of the voronoi diagram. This is because I want to differentiate/vary the cell radius of the points between them. So for example I'll have 5 type of points, and each type has an specific cell radius. (because usually all the points have the same cell radius, the intersection is always in the mid point between points, but I would like to have that line, instead of the mid point, closer to one point than another) And with that, do the voronoi diagram. Is this even possible? I thought that the method of constructing the voronoi diagram through circle intersections might be useful and I think is the one the current component use. Any thoughts??

Replies to This Discussion

Permalink Reply by David Rutten on October 25, 2013 at 8:07am

I don't know if it is possible to construct a complete voronoi diagram this way. Weighted voronoi diagrams (there's two common kinds to my knowledge) end up with edges that are either elliptic segments or hyperbolic segments and thus not straight lines.

David Rutten

david@mcneel.com

Seattle, WA

Permalink Reply by Andrew on October 25, 2013 at 8:57am

Thanks for the response David, I'll see what I can find on weighted voronoi diagrams; it seems the closer solution to my problem.

Permalink Reply by Daniel Piker on October 25, 2013 at 10:08am

I suppose another way to go about this would be to start from the Delaunay triangulation, and take the barycentric coordinates of the circumcenters. Joining these gives you the standard Voronoi diagram, but you could include an additional per-vertex weighting factor to increase or decrease the size of each cell.

Permalink Reply by David Rutten on October 25, 2013 at 10:11am

Would that not result in problems if a cell grows beyond the immediate neighbours?

David Rutten

david@mcneel.com

Seattle, WA

Permalink Reply by to] on October 25, 2013 at 10:47am

We wrote some time ago a weighted voronoi solution which is based on circle radius.

This kind of diagrams are also called power diagrams.

We never finished to make it totally bug free so we never released it.

but maybe with this phrase you will find some papers about it.

@ david:

When the weight grows over the influence of another attractor (center + radius) than it is no longer part of the solution.

Permalink Reply by David Rutten on October 25, 2013 at 10:57am

Ah, never heard of power diagrams before, neat.

David Rutten

david@mcneel.com

Seattle, WA

Permalink Reply by to] on October 25, 2013 at 11:01am

It is based on your voronoi diagram. But we run into problems that it had overlaps if they start to "eat points" So hopefully we have a view at it again and work on the neighbor relationship to fix this issue.

Permalink Reply by Danny Boyes on October 25, 2013 at 11:36am

Wow!

I wish I new this 5 years ago. I created a power diagram for a legal case and was asked by the lawyers what the type of diagram was called. I drew a blank as I had created it of off my own bat and called it a variation on Voronoi (which I only knew about because it had just found its way into Grasshopper.)

Permalink Reply by Andrew on November 4, 2013 at 2:37pm

Thanks all for the responses, I gave the power diagrams a try but failed completely! Hope someone can make it work though!

RSS