Descobrindo em quais pontos dos triângulos

16

Suponhamos que tem uma malha que consiste em 2D triângulos não sobrepostos , e um conjunto de pontos { p i } M i = 1N k = 1 T K . Qual é a melhor maneira de determinar em qual triângulo cada um dos pontos se encontra?{Tk}k=1N{pi}i=1Mk=1NTK

Por exemplo, na imagem a seguir, temos , p 2T 4 , , então eu gostaria de uma função que retorne a lista .p1T2p2T4 f f ( p 1 , p 2 , p 3 ) = [ 2 , 4 , 2 ]p3T2ff(p1 1,p2,p3)=[2,4,2]

insira a descrição da imagem aqui

O Matlab tem a função de localização de pontos que faz o que eu quero para malhas de Delaunay, mas falha em malhas gerais.

Meu primeiro pensamento (burro) é que, para todos os nós , percorra todos os triângulos para descobrir qual triângulo está. No entanto, isso é extremamente ineficiente - você pode precisar percorrer todos os triângulos para cada ponto, para que possa faça o trabalho de .p i O ( N M )pEupEuO(NM)

Meu próximo pensamento é, para todos os pontos , encontre o nó de malha mais próximo por meio da pesquisa do vizinho mais próximo e, em seguida, observe os triângulos anexados ao nó mais próximo. Nesse caso, o trabalho seria , onde é o número máximo de triângulos anexados a qualquer nó na malha. Existem alguns problemas solucionáveis, mas irritantes, com essa abordagem, ó ( um H l ó g ( N ) ) umpEuO(aMlog(N))a

  • Requer implementar uma pesquisa eficiente do vizinho mais próximo (ou encontrar uma biblioteca que a possua), o que pode ser uma tarefa não trivial.
  • Requer o armazenamento de uma lista de quais triângulos estão anexados a cada nó, para os quais meu código não está configurado atualmente - agora há apenas uma lista de coordenadas do nó e uma lista de elementos.

No geral, parece deselegante, e acho que deveria haver uma maneira melhor. Esse deve ser um problema que surge muito, então eu queria saber se alguém poderia recomendar a melhor maneira de abordar a localização dos triângulos nos nós, teoricamente ou em termos de bibliotecas disponíveis.

Obrigado!

Nick Alger
fonte

Respostas:

16

O método usual de salto aleatório de arestas deve funcionar. Basicamente, comece com qualquer triângulo da malha e determine qual das arestas o ponto de destino fica no lado oposto. Ou seja, determine quais arestas, quando estendidas até uma linha, separam o ponto do interior do triângulo. Quando houver duas possibilidades, escolha uma aleatoriamente, considere o triângulo adjacente à borda compartilhada e repita. A randomização deve fazer com que esse método converja com a probabilidade 1 para triangulações de Delaunay, e não consigo pensar em uma razão pela qual ele não funcionaria para triangulações arbitrárias.

O(registroN)O(MregistroN)M

Edit2 : Encontrei este PDF descrevendo um esquema de "caminhada" que é garantido para terminar e analisa as abordagens mais ingênuas.

Outra alternativa ao uso de quadras é usar uma Hierarquia de Triangulação. Veja Olivier Devillers. Triangulação Delaunay aleatória incremental aprimorada. Em Proc. 14º Annu. Simpósios da ACM. Comput. Geom., Páginas 106-115, 1998. Funciona melhor para triangulações de Delaunay, mas também pode funcionar para não-Delaunay.

Basicamente, o que você faz para acelerar a localização do ponto exigirá a construção de uma estrutura de dados auxiliar. No caso de quadríceps ou alguma outra subdivisão espacial, você precisa construir a árvore de subdivisão. No caso de pular arestas, você precisa construir a estrutura topológica adjacente ao triângulo. A hierarquia de triangulação também requer a construção de uma árvore de triangulações mais grossas.

Victor Liu
fonte
Victor - você conhece algum código de código aberto que implemente a abordagem de salto em borda? Parece uma solução muito boa para o meu caso. (modelo de rastreamento de partículas impulsionado por campos atuais num traingualr malha grade) -Obrigado
Chris Barker
Eu tenho um código para isso e posso enviá-lo para você; está em C / C ++. Ainda não tive tempo de limpá-lo e publicá-lo no Github. Eu tive que escrever isso pelo menos duas vezes na minha vida, uma vez com uma estrutura de dados de meia borda, novamente com uma quadedge, mas ela pode ser facilmente usada quando essas não estão disponíveis e você mesmo precisa construir uma estrutura topológica. Procure na minha página de perfil o meu site, onde você pode encontrar informações de contato. Podemos discutir isso ainda mais offline.
Victor Liu
Estou quase terminando de implementar isso no matlab usando a ordenação de curvas de Hilbert e a caminhada aleatória em triângulo. É um código de pesquisa: não otimizado, não documentado, etc., mas ainda bem rápido - posso fornecer o código se você estiver interessado.
Nick Alger
2
Sobre: ​​"" "o salto de borda deve ser O (logN)" "" Não vejo isso. Por exemplo, no caso patológico de uma grande faixa de triângulo longo (como um canal estreito apenas no triângulo de largura), na pior das hipóteses, você precisaria pular de um triângulo para o próximo até o final. No caso médio, a meio caminho. Portanto, se você dobrar o número de triângulos, seria O (N) No caso mais normal de uma disposição quadrada de triângulos, eu esperaria O (sqrt (N)). Ou eu estou esquecendo de alguma coisa? -Chris
Chris Barker
@ Chris - Bem-vindo ao scicomp! Como parte da manutenção do scicomp, migrei suas respostas e a conversa que se seguiu como comentários sobre a resposta de Victor. Aguardamos a sua participação no site.
Aron Ahmadia 02/07/12
8

Não estou convencido de que sua solução esteja correta. Considere a situação em que você possui esses nós:

  • A: (-3, 1)
  • B: (0, 2)
  • C: (3, 1)
  • D: (0, -5)

Existem triângulos ABC e ACD. Agora B é o ponto mais próximo da origem, mas a origem está no triângulo ACD, que não contém B.

O(NM)

Eu consideraria a opção de construir um quadtree que contenha os triângulos. Ou seja, você tem uma árvore quaternária que armazena em cada nó (que corresponde a uma caixa delimitadora):

  • As coordenadas nas quais a caixa está sendo dividida ou, alternativamente, as caixas delimitadoras das quatro subárvores;
  • Ponteiros para as subárvores;
  • O conjunto de triângulos que ficam completamente dentro da caixa delimitadora desse retângulo, mas não completamente dentro de qualquer uma das quatro subárvores. Em outras palavras, os triângulos que se cruzam com qualquer um dos dois segmentos de linha subdividida do quadtree.

nnregistronO(NM)

Erik P.
fonte
Hmm, você está certo. Por outro lado, se a triangulação fosse Delaunay, acho que o vizinho mais próximo funcionaria. É muito restritivo para o que estou tentando fazer, mas no caso de Delaunay, considere o diagrama duplo de Voronoi - as células Voronoi são o conjunto de pontos mais próximos de um nó, e as bordas dos triângulos delaunay encontram as bordas dos Voronoi células em ângulos retos, portanto, qualquer ponto deve estar em um triângulo conectado ao nó mais próximo. Gostaria de saber se é assim que a função pointLocation do matlab funciona sob o capô ..?
Nick Alger
1

A CGAL lida com triangulações e localização de pontos (e muito mais). Em particular, o módulo de triangulação 2D pode fazer o que você deseja.

Ronaldo Carpio
fonte