Algoritmo para achado original bordas de malha de polígono

StackOverflow https://stackoverflow.com/questions/207744

Pergunta

Eu estou procurando um bom algoritmo que pode me dar as bordas originais de um conjunto de dados de polígono. Neste caso, os polígonos são definidos por duas matrizes. Uma matriz é o número de pontos por polígono, e outra matriz é uma lista de índices de vértice.

Eu tenho uma versão que está funcionando, mas o desempenho fica lento ao atingir mais de 500.000 polígonos. Minha versão caminha cada face e adiciona vértices classificadas de cada ponta para um STL :: set. Meu conjunto de dados será principalmente triângulo e quádruplos polys, ea maioria das bordas será compartilhado.

Existe um algoritmo inteligente para isso?

Foi útil?

Solução

Sim
Use um mapa duplo hash.
Cada extremidade tem dois índices A, B. Vamos dizer que A> B.
A primeira, de nível superior hash mapa mapas A para outro de hash-map que é por sua vez mapeia B para algum valor que representa as informações que deseja sobre cada borda. (Ou apenas um bool se você não precisa manter informações para bordas).
Essencialmente, isso cria uma árvore de dois níveis composto por mapas hash.

Para procurar uma vantagem nesta estrutura você tomar o índice maior, procurá-lo em nível superior e acabar com um mapa hash. em seguida, tomar o índice menor e procurá-lo neste segundo mapa hash.

Outras dicas

Só para esclarecer, você quer, para uma lista polígono assim: 

A +-----+ B
   \    |\
    \ 1 | \
     \  |  \
      \ | 2 \
       \|    \
      C +-----+ D

Então, em vez de arestas como este: 

A - B -+
B - C  +- first polygon
C - A -+

B - D -+
D - C  +- second polygon
C - B -+

então você deseja remover o duplicado B - C C vs. -? B borda e compartilhá-lo

Que tipo de problema de desempenho que você está vendo com o seu algoritmo? Eu diria que um conjunto que tem uma implementação de hash razoável deve executar muito ok. Por outro lado, se o seu hash não é o ideal para os dados, você terá lotes de colisões que podem afetar o desempenho mal.

Você estão corretos. Usando um bom hashset tem obtido o desempenho bem além dos níveis exigidos. Eu acabei rolando o meu próprio conjunto pouco hash.

O número total de bordas será entre N / 2 e N sendo N o número de vértices únicas na malha. Todas as bordas compartilhadas será N / 2, e todas as arestas únicas será N. De lá, eu alocar um buffer de uint64 de e embalar meus índices para esses valores. Usando um pequeno conjunto de tabelas únicas posso encontrar as bordas únicas rápido!

Primeiro, você precisa ter certeza de seus vértices são únicos. Isto é, se você quiser apenas uma borda em uma determinada posição. Então eu uso essa estrutura de dados

typedef std::pair<int, int> Edge;

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Borda contém os índices de vértices que compõem a borda em ordem de classificação. Portanto, se sampleEdge é uma aresta formada por vértices com números de índice 12 e 5, 5 e sampleEdge.first = sampleEdge.12

Em seguida, você pode apenas fazer

uniqueEdges[sampleEdge] = true;

para todas as arestas. uniqueEdges irá realizar todas as arestas únicas.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top