Re: [boost] [voronoi]medial axis
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
Hi Michael, That's great! I am looking forward to see your code. Andrii
Hi, Andrii, I did not create an account at boost SVN yet, so I will try to attach/paste the file here. The code provides Boost graph adapter for "primal" graph, where vertices and edges are (finite) vertices and (finite) edges of Voronoi diagram. I tested this code in my application, the vertex and edge iterators provided by global functions in_edges(v,g), out_edges(v,g), vertices(g) etc. seems to work correctly. I did not test the customized property maps yet. Dual graph looks very similar except it does not exclude infinite edges: vertices of the dual graph are cells, edges are represented by type voronoi_edge and connect adjacent cells. Hope this code helps. It need further polishing, of course. Thanks, -Michael BoostVoronoiPrimalGraph.hpp http://boost.2283326.n4.nabble.com/file/n4653652/BoostVoronoiPrimalGraph.hpp -- View this message in context: http://boost.2283326.n4.nabble.com/Re-voronoi-medial-axis-tp4653498p4653652.... Sent from the Boost - Dev mailing list archive at Nabble.com.
Hi, Andrii, Below I upload the files for both Primal and Dual Voronoi graphs. I also modified the property maps and checked they work correctly. A simple way to use/test the graphs and the properties is as follows: I also realized that Middle Axis algorithms present some challenge here. Voronoi diagram does not keep its input and knows almost nothing about it. To discriminate "inner" and "outer" parts of polygons we should make some assumptions about the structure of input segments. One convenient way to do so is to pass some "polygon model" to future Middle-Axis functor. This model can be one of the concepts from Boost.Geometry (ring, polygon, multi-polygon). These models correspond to Boost.Polygon concepts of Polygon, Polygon_With_Holes and Polygon_Set, respectfully. (The library Boost.Geometry actually provides adapters for major Boost.Polygon concepts). Still, the functor can get into troubles when comparing the input vertices for equality. Comparing the input coordinates is not guaranteed to be robust; however, comparing input indexing can also get into trouble, e.g. when hole vertex coincides with external boundary vertex. Probably, one needs to provide several policies and traits of the Middle-Axis functor and let user decide on trade-offs. Thank you, -Michael BoostVoronoiPrimalGraph.hpp http://boost.2283326.n4.nabble.com/file/n4653800/BoostVoronoiPrimalGraph.hpp BoostVoronoiDualGraph.hpp http://boost.2283326.n4.nabble.com/file/n4653800/BoostVoronoiDualGraph.hpp -- View this message in context: http://boost.2283326.n4.nabble.com/Re-voronoi-medial-axis-tp4653498p4653800.... Sent from the Boost - Dev mailing list archive at Nabble.com.
participants (2)
-
Andrii Sydorchuk -
Michael Simbirsky