Descobrindo em quais pontos dos triângulos

Suponhamos que tem uma malha que consiste em 2D triângulos não sobrepostos , e um conjunto de pontos { p i } M i = 1 ⊂ ∪ N k = 1 T K . Qual é a melhor maneira de determinar em qual triângulo cada um dos pontos se encontra?$\{T_k\}_{k=1}^N$$\{p_i\}_{i=1}^M \subset \cup_{k=1}^N T_K$

Por exemplo, na imagem a seguir, temos , p 2 ∈ T 4 , , então eu gostaria de uma função que retorne a lista .$p_1 \in T_2$$p_2 \in T_4$ f f ( p 1 , p 2 , p 3 ) = [ 2 , 4 , 2 $p_3 \in T_2$$f$$f(p_1,p_2,p_3)=[2,4,2]$

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 $p_i$$p_i$$O(N \cdot M)$

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 ) ) $p_i$$O(a\cdot M\cdot log(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!

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(\log N)$$O(M \log N)$$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.

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(N \cdot M)$

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.

$\sqrt{n}$$n$$\log n$$O(N\cdot M)$

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.