Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks (Delaunay graph)

by blokhead (Monsignor)
on Jul 02, 2008 at 12:28 UTC ( #695124=note: print w/ replies, xml ) Need Help??


in reply to Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks

The Voronoi diagram of a set of points is the dual graph of the Delaunay triangulation of the points. The Voronoi regions for p,q share an edge if and only if p,q have a Delaunay edge between them.

This means that questions about Voronoi region adjacency can be more conveniently framed as questions about adjacency/connectivity in a plain graph, if you have both structures available as well as the correspondence between the two. In terms of your sets of points, if some Delaunay edge has its two endpoints in the same set/grouping, then you would have colored those two Voronoi regions the same, and you can throw out the dual edge (this is the edge in the Voronoi diagram that the two regions share).

Following this Delaunay-adjacency idea through, you can compute in the Delaunay graph the "contiguous" components (there's probably a better name for this -- I just made it up). In other words, partition the Delaunay graph into maximal connected subgraphs whose vertices are all in the same set (starting at each unseen vertex, traverse with BFS/DFS only to neighbors in the same set as the root). These partitions will correspond exactly to the polygons you want. You can take each contiguous component, and traverse around its perimeter, accumulating the border Voronoi edges. If removing a particular component disconnects the Delaunay graph into k components, then the corresponding compound Voronoi polygon will have k-1 holes, so you'd need to traverse those perimeters as well (although the perimeters are shared by other components and traced out there too).

blokhead


Comment on Re: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks (Delaunay graph)
Re^2: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks (Delaunay graph)
by samtregar (Abbot) on Jul 02, 2008 at 18:39 UTC
    This sounds correct to me. You're definitely right about Delauney graphs and you can get that data from my module by looking at which points correspond to an edge. The problem for me is that I don't know if I can actually translate this solution into code! Maybe I'll give it a try and see what I can come up with.

    -sam

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://695124]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (10)
As of 2014-12-28 15:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (182 votes), past polls