Re: [boost] [voronoi]medial axis

Subject: Re: [boost] [voronoi]medial axis
From: Louis Lavery (zen218432_at_[hidden])
Date: 2013-09-02 03:41:34

Hello Andrii,

Thanks for the reply, and the link to the new (?) documentation.

On 01/09/13 09:41, Andrii Sydorchuk wrote:
> Hi Louis,
[snip]
> 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
>

Yes, that's better than my idea, as it avoids comparing voronoi co-ords 
with user input points, so I don't need an epsilon.

> Let me know if you have more questions.
>

After I've identified and marked the boundary vertices I need to 
identify and mark which vertices are outside and which are inside the 
shape. The shape is closed, but can have holes e.g. an annulus. I don't 
know if the following procedure is correct.

Assume vertices on boundaries have been marked 1 and all others are 0.

(1) Find an unmarked vertex and mark it and all unmarked vertices that 
can be reached from it via primary edges with 2.

(2) Keep repeating (1) but mark vertices with 3,4,..., until all 
vertices are marked.

(3) That identifies the separate areas, but I don't know which areas are 
outside, which are holes and which are inside.

(4) If outside vertices (not in a hole) are always connected to an 
infinite vertex then I can use that fact to identify the outside area 
(and can deduce the others from that).

So my question is, is each outside vertex connected to an infinite 
vertex via primary edges? [1]

Thanks for your help, Louis

[1] I assume inside vertices, and those in a hole, are not connected to 
an infinite vertex (via primary edges).