Convertendo polígonos indexados ao ones não indexados. Vários problemas surgiram

Question

Mais uma vez eu tenho algumas perguntas sobre algoritmos de polígonos.

Vou tentar explicar o meu problema:

Eu estou usando um subconjunto de uma biblioteca de terceiros chamados Ferramentas geométricas (GT) para executar operações de boolean em meus polígonos. Para conseguir isso eu tenho que converter o meu formato de polígono interno para os usos formato GT.

O formato poligonal interna consiste de uma matriz de vértice, enquanto o polígono GT consiste de uma matriz de vértice indexada em que cada aresta está representado por um par de índices.

Exemplo de um quadrado de esclarecimento:

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.

Agora, eu escrevi um algoritmo que funciona na maioria dos casos, mas acidentes e queimaduras quando duas arestas compartilhar o mesmo vértice de partida. Deixe-me começar por explicar como o meu algoritmo funciona atuais.

Faça um std :: mapa onde a chave é um inteiro representando o índice de vértice. O valor representa onde na matriz borda existe uma aresta com a chave-índice começando como índice.

Maquete exemplo:

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 de borda correta para a borda correta que eu posso agora apenas fazer o seguinte dentro de um tempo loop:

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

Dentro deste ciclo não for feito alguma otimização, e os índices dos vértices são adicionadas a uma matriz.

Cada vez que um polígono está fechada i encontrar a primeira borda untraversed e começar a fazer outro polígono. Eu continuo fazendo isso até que não haja bordas não mais untraversed no GTPolygon.

Assim, cada GTPolygon pode resultar em vários Polygon (interna) objetos.

A falha neste algoritmo é evidente quando há duas arestas que compartilham o mesmo vértice como um vértice inicial. Exemplo:

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

Quando atravessando minhas extremidades, como vou saber qual dessas bordas pertence ao polígono Atualmente, estou atravessando? Eu poderia tentar atravessar as bordas trás quando uma situação tão duplicado ocorre. O problema, então, seria a possibilidade do traversation indo e voltando infinitamente se outro duplicado é encontrado ao inverter.

A minha pergunta é, como posso resolver isso? É solúvel em tudo? Posso usar a árvore BSP para resolver isso de alguma forma? A quantidade de casos de canto é um pouco assustador.

Qualquer ajuda é muito apreciada como 5 meses de trabalho depende deste trabalho.

Editar:

Para esclarecer:. Eu quero converter a partir da representação indexada de um polígono que a geometria Tools trabalha com o nosso formato de polígono interno, que é apenas uma série de vértices conectados em uma lista

Answer 1

Você está efetivamente tentando encontrar tudo ciclos em uma undirected gráfico onde cada ciclo representa os lados de um polígono original. Este artigo propõe uma busca em profundidade (DFS) solução .

Answer 2

Haha, ok caras. Parece que todo o hubub tem sido para nada. Eu achei que a geometria Tools tem a sua própria classe para lidar com problemas como estes.

Exemplo encontrado aqui .

Answer 3

Por que você não armazenar polígonos explicitamente como uma coleção ordenada de bordas? Isso iria garantir que você sempre sabe dado um polígono que bordas você deve considerar.