Re: [boost] [voronoi]medial axis

Subject: Re: [boost] [voronoi]medial axis
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2013-09-02 16:19:07

Hi Louis,

On Mon, Sep 2, 2013 at 9:41 AM, Louis Lavery <zen218432_at_[hidden]> wrote:

> 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]
>

The current implementation doesn't contain explicit representation of the
infinite vertex. However, you can start from any infinite edge.

All the steps seem to be correct. I will also recommend to use a bit
modified procedure:
1) Identify the outside area first by iterating from infinite edge;
2) Iterate over boundary vertices reachable from the infinite vertex and
fill the inside area.
Note: you might need to iterate over a few boundary vertices, because there
won't be any primary Voronoi edges coming from the obtuse angles.
As long as you use DFS or BFS for traversal with keeping the track of
visited Voronoi edges, iterating over the outside boundary vertices won't
change the complexity of the algorithm.
3) Your solution and the above approach will work properly as long as there
is no hole, that shares a common point with the outer boundary.
Let me know if that's not the case, and I will provide the improved
procedure.

If you have any question, feel free to ask.

Regards,
Andrii