Boost logo

Boost :

Subject: Re: [boost] [voronoi]medial axis
From: Michael Simbirsky (michael.simbirsky_at_[hidden])
Date: 2013-10-26 19:10:26

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,



View this message in context:
Sent from the Boost - Dev mailing list archive at

Boost list run by bdawes at, gregod at, cpdaniel at, john at