Re: [boost] [voronoi]medial axis

Subject: Re: [boost] [voronoi]medial axis
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2013-09-01 04:41:39

Hi Louis,

On Fri, Aug 30, 2013 at 11:02 AM, Louis Lavery <zen218432_at_[hidden]> wrote:

> I'm hoping to use boost voronoi to construct the (internal) medial axis
> for closed shapes (with holes). I need to work out which vertices of the
> voronoi are inside, outside and on a boundary. So my first goal is to
> determine which vertices correspond to the ends of the input segments
> (boundary vertices).
>
> The way I do this at the moment, is to look at each edge and test if its
> source vertex, vertex0(), is equal to either end point of the segment
> contained by the edge's cell.
>
> (1) If it is then it's a boundary vertex otherwise it's not. Is that
> correct?
>
> (2) When comparing a vertex with an input point can I do an exact compare
> (==) or should I use a tolerance (epsilon)?
>

As you've noticed in your second question, this comparison might not be
exact.
However, there is a slightly simpler way to do the check you are interested
in, that is 100% robust.

The procedure is the following:
1) Instead of iterating over Voronoi edges, iterate over all Voronoi
vertices.
2) For each Voronoi vertex check all Voronoi edges incident to it (in
general case there should be 3 edges).
For each such edge find the input point or segment located within the cell,
that the edge belongs to.
Check if all input object share a common endpoint. If yes, then the Voronoi
vertex is located on the boundary, otherwise no.
You can find more details on how to iterate over incident objects and
Voronoi diagram topology here:
http://www.boost.org/doc/libs/1_54_0/libs/polygon/doc/voronoi_diagram.htm

Let me know if you have more questions.

Andrii