Hi Louis,
On Fri, Aug 30, 2013 at 11:02 AM, Louis Lavery
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