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).