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

In reply to Re: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks (Delaunay graph) by blokhead
in thread Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks by samtregar

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.