Convertir polígonos indexados a no indexados. Han surgido varios problemas

Question

Una vez más, tengo algunas preguntas sobre los algoritmos de polígono.

Trataré de explicar mi problema:

Estoy usando un subconjunto de una biblioteca de terceros llamada Geometric Tools (GT) para realizar operaciones booleanas en mis polígonos. Para lograr esto, tengo que convertir mi formato de polígono interno al formato que utiliza GT.

Nuestro formato de polígono interno consiste en una matriz de vértices, mientras que el polígono GT consiste en una matriz de vértices indexados donde cada borde está representado por un par de índices.

Ejemplo de un cuadrado para aclaración:

Formato interno:

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

Formato externo:

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.

Ahora, escribí un algoritmo que funciona en la mayoría de los casos, pero se bloquea y se quema cuando dos bordes comparten el mismo vértice inicial. Permítanme comenzar explicando cómo funciona mi algoritmo actual.

Haga un mapa std :: donde la clave sea un número entero que represente el índice de vértice. El valor representa dónde en la matriz de borde hay un borde con el índice clave como índice inicial.

Ejemplo de maqueta:

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;
}

Para saltar del borde correcto al borde correcto ahora puedo hacer lo siguiente dentro de un ciclo while:

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

Dentro de este bucle se realiza una optimización y se agregan índices de vértice a una matriz.

Cada vez que se cierra un polígono encuentro el primer borde sin recorrer y empiezo a hacer otro polígono. Sigo haciendo esto hasta que no haya más bordes sin recorrer en el GTPolygon.

Por lo tanto, cada GTPolygon puede generar varios objetos Polygon (internos).

La falla en este algoritmo es evidente cuando hay dos bordes que comparten el mismo vértice como un vértice inicial. Ejemplo:

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

Al atravesar mis bordes, ¿cómo sabré cuál de estos bordes pertenece al polígono que estoy atravesando actualmente? Podría intentar atravesar los bordes HACIA ATRÁS cuando se produzca una situación tan duplicada. El problema sería la posibilidad de que la travesía vaya y venga infinitamente si se encuentra otro duplicado mientras se invierte.

Mi pregunta es, ¿cómo puedo resolver esto? ¿Es solucionable en absoluto? ¿Puedo usar el árbol BSP para resolver esto de alguna manera? La cantidad de casos de esquina es un poco desalentador.

Cualquier ayuda es muy apreciada ya que 5 meses de trabajo dependen de este trabajo.

Editar:

Para aclarar: quiero convertir de la representación indexada de un polígono con el que trabaja Geometry Tools a nuestro formato de polígono interno, que es solo una serie de vértices conectados en una lista.

Answer 1

Estás intentando encontrar todos los ciclos en un no dirigido graph donde cada ciclo representa los bordes de un polígono único. Este documento propone un solución de búsqueda en profundidad (DFS) .

Answer 2

Jaja, ok chicos. Parece que todo el hubub ha sido para nada. Descubrí que Geometry Tools tiene su propia clase para tratar problemas como estos.

Ejemplo encontrado aquí .

.

Answer 3

¿Por qué no almacena polígonos explícitamente como una colección ordenada de bordes? Eso aseguraría que siempre sepa, dado un polígono, qué bordes debe considerar.