Hi Louis, On Mon, Sep 2, 2013 at 9:41 AM, Louis Lavery <zen218432@zen.co.uk> 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