Converting indexed polygons to unindexed ones. Several problems have cropped up.

Question

Yet again I have some questions regarding polygon algorithms.

I'll try to explain my problem:

I am using a subset of a third party library called Geometric Tools(GT) to perform boolean operations on my polygons. To accomplish this I have to convert my internal polygon format to the format GT uses.

Our internal polygon format consists of a vertex array, while the GT polygon consists of an indexed vertex array where each edge is represented by a pair of indices.

Example of a square for clarification:

Internal format:

vertices[0] = Vertex2D(1,0) -> start
vertices[1] = Vertex2D(1,1)
vertices[2] = Vertex2D(0,1)
vertices[3] = Vertex2D(0,0)
vertices[4] = Vertex2D(1,0) -> end

External format:

vertices[0] = Vertex2D(1,0) 
vertices[1] = Vertex2D(1,1)
vertices[2] = Vertex2D(0,1)
vertices[3] = Vertex2D(0,0)

edges[0] = std::pair<int,int>(0,1)
edges[1] = std::pair<int,int>(1,2)
edges[2] = std::pair<int,int>(2,3)
edges[3] = std::pair<int,int>(3,0)

//There is also a BSP tree of the polygon which I don't care to depict here.

Now, I wrote an algorithm that works in most cases, but crashes and burns when two edges share the same starting vertex. Let me start by explaining how my current algorithm works.

Make a std::map where the key is an integer representing the vertex index. The value represents where in the edge array there is an edge with the key-index as starting index.

Mockup example:

std::vector< std::pair< int, int > > edge_array;

edge_array.push_back( std::pair< int, int >( 0, 1 ) );
edge_array.push_back( std::pair< int, int >( 2, 3 ) );
edge_array.push_back( std::pair< int, int >( 1, 2 ) );
edge_array.push_back( std::pair< int, int >( 3, 0 ) );

std::map< int, int > edge_starts;
for ( int i = 0 ; i < edge_array.size(); ++i ) {
  edge_starts[ edge_array[i].first ] = i;
}

To jump from correct edge to correct edge i can now just do the following inside a while loop:

while ( current_placed_index = first_index_in_polygon ) {
  int index_to_next_edge_to_be_traversed = edge_starts[ current_edge.second ];
}

Inside this loop there is done some optimization, and vertex indices are added to an array.

Each time a polygon is closed i find the first untraversed edge and start making another polygon. I keep on doing this until there are no more untraversed edges in the GTPolygon.

So each GTPolygon can result in several Polygon(internal) objects.

The flaw in this algorithm is evident when there are two edges sharing the same vertex as a starting vertex. Example:

<1,2>
<1,3>
<1,5>

When traversing my edges, how will i know which of these edges belongs to the polygon I am currently traversing? I could try traversing the edges BACKWARDS when such a duplicate situation occurs. The problem then would be the possibility of the traversation going back and forth infinitely if another duplicate is found while reversing.

My question is, how can I solve this? Is it solvable at all? Can I use the BSP tree to solve this in some way? The amount of corner cases is a bit daunting.

Any help is greatly appreciated as 5 months of work depends on this working.

Edit:

To clarify: I want to convert from the indexed representation of a polygon that Geometry Tools works with to our internal polygon format, which is just a series of connected vertices in a list.

Answer 1

Why don't you store polygons explicitly as an ordered collection of edges? That would ensure that you always know given a polygon which edges you should consider.

Answer 2

You are effectively trying to find all cycles in an undirected graph where each cycle represents the edges of a unique polygon. This paper proposes a depth-first search (DFS) solution.

Answer 3

Haha, ok guys. It seems like all the hubub has been for nothing. I found that Geometry Tools has it's own class to deal with problems like these.

Example found here.