Re: [boost] [voronoi]medial axis

Subject: Re: [boost] [voronoi]medial axis
From: Louis Lavery (zen218432_at_[hidden])
Date: 2013-09-11 09:33:46

Hello Andrii,

Sorry for being away so long, got caught up in other things.
Anyway, I've a small change in what I need to do. All I require is to 
identify boundary vertices and inside vertices (not in a hole). However, 
to do that I still need to identify the outside vertices, AFAICS. I 
still identify and visit the boundary vertices using the method we've 
already discussed (that's working just fine).

Here's what I'm now doing (cut and paste from the actual .cpp file)

// Assume boundary vertices are visited and labeled as boundary.
//
// (6) We want to find the inside vertices (not in a hole).
// (6.1)
// The only sure way to do that, as far as I know, is to
// visit and label each outside vertex. To do that we start
// a bfs from the finite vertex of each primary infinite
// edge, if that finite vertex is not already visited.
//
// (6.2)
// Once we've visited, and labelled, these outside vertices
// we find an edge (which may be secondary) incident to both
// a boundary and an outside vertex, and rot_next about the
// boundary end of that edge until we hit an unvisited vertex,
// which we can be sure will happen(?). We then bfs from that
// unvisited vertex to label inside vertices.
//
// (6.3)
// Once we've done the above the only unvisited vertices will
// be those in holes (and we could repeat something similar to
// the above to label those hole vertices and discover any
// holes within the holes, if we so wished).
//
// (6.4)
// Note: the bfs searches along primary edges, it ignores
// secondary edges.

I'm pretty sure that should work okay, if I can assume rot_next about 
the boundary end of the edge will get me to an inside vertex, see '(?)' 
in the above (6.2) paragraph.

I'm not sure what you mean by the following...

On 02/09/13 21:19, Andrii Sydorchuk wrote:
> 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.

...regards obtuse angles. If my revised algorithm above will work, then 
I don't need to know what you mean (and am happy if that's the case).

Thanks for your help, Louis.