Re: [boost] [voronoi]medial axis

Subject: Re: [boost] [voronoi]medial axis
From: Michael Simbirsky (michael.simbirsky_at_[hidden])
Date: 2013-10-22 02:12:37

Thanks, Andrii, Louis,

Like Louis, I try to use Boost.Polygon Voronoi diagram for medial axis
computation. Since Voronoi diagram is stored as DCEL, it is not difficult
to represent it as a combination of two dual graphs. The "primal"
bidirected graph has Voronoi vertices as its vertices and (finite)
halfedges as edges. The "dual" graph has Voronoi cells as its vertices;
half-edges "connect" adjacent cells. This graph is also bi-directed.

I think this understanding of DCEL is rather common; I believe CGAL applies
similar approach to provide Boost Graph adapters for its DCEL arrangements.

For my purposes I am writing the adapters on my own. Iterator parts are
straight-forward. For efficiency it is also useful to convert some
internals into "property maps". For example, color map is already provided,
one has only to wrap it into boost::property_map with correct access
functions. Similarly, the fact that vertices are packed into continuous
storage gives us an efficient "vertex to integer" bimap, an important
ingredient for many search algorithms from Boost Graph library.

As the next step I hope to implement your discussion on vertices connected
to infinity, vertices in holes etc.using Boost.Graph.

Andrii, I would be glad to share this code with you and Boost.Polygon users.

Thanks,
-Michael