Encontrar en qué triángulos están los puntos

Supongamos que tengo una malla 2D que consiste en triángulos que no se superponen , y un conjunto de puntos { p i } M i = 1 ⊂ ∪ N k = 1 T K . ¿Cuál es la mejor manera de determinar en qué triángulo se encuentra cada uno de los puntos?$\{T_k\}_{k=1}^N$$\{p_i\}_{i=1}^M \subset \cup_{k=1}^N T_K$

Por ejemplo, en la siguiente imagen tenemos , p 2 ∈ T 4 , p 3 ∈ T 2 , por lo que me gustaría una función f que devuelva la lista f ( p 1 , p 2 , p 3$p_1 \in T_2$$p_2 \in T_4$$p_3 \in T_2$$f$ .$f(p_1,p_2,p_3)=[2,4,2]$

Matlab tiene la función de asignación de puntos que hace lo que quiero para las mallas Delaunay, pero falla para las mallas generales.

Mi primer pensamiento (tonto) es, para todos los nodos , recorrer todos los triángulos para descubrir en qué triángulo p i está. Sin embargo, esto es extremadamente ineficiente: es posible que tenga que recorrer cada triángulo para cada punto, por lo que podría tomar trabajo O ( N ⋅ M ) .$p_i$$p_i$$O(N \cdot M)$

Mi siguiente pensamiento es, para todos los puntos , encontrar el nodo de malla más cercano a través de la búsqueda de vecino más cercano, luego mirar a través de triángulos unidos a ese nodo más cercano. En este caso, el trabajo sería O ( a ⋅ M ⋅ l o $p_i$ , donde a es el número máximo de triángulos unidos a cualquier nodo en la malla. Hay un par de problemas solucionables pero molestos con este enfoque,$O(a\cdot M\cdot log(N))$$a$

• Requiere implementar una búsqueda eficiente del vecino más cercano (o encontrar una biblioteca que lo tenga), lo que podría ser una tarea no trivial.
• Requiere almacenar una lista de los triángulos que están unidos a cada nodo, para lo cual mi código no está configurado actualmente; en este momento solo hay una lista de coordenadas de nodo y una lista de elementos.

En conjunto, parece poco elegante, y creo que debería haber una mejor manera. Este debe ser un problema que surge mucho, así que me preguntaba si alguien podría recomendar la mejor manera de abordar la búsqueda de los triángulos en los que se encuentran los nodos, ya sea teóricamente o en términos de bibliotecas disponibles.

¡Gracias!

El método de salto de borde aleatorio habitual debería funcionar. Básicamente, comience con cualquier triángulo de la malla, luego determine de cuál de los bordes se encuentra el punto objetivo en el lado opuesto. Es decir, determinar cuál de los bordes, cuando se extiende a una línea, separa el punto del interior del triángulo. Cuando hay dos posibilidades, elija una al azar, considere el triángulo adyacente a ese borde compartido y repita. La aleatorización debería hacer que este método converja con la probabilidad 1 para triangulaciones de Delaunay, y no puedo pensar en una razón por la que no funcionaría para triangulaciones arbitrarias.

Editar : debo agregar que el salto de borde debe ser con una constante razonable para un solo punto, por lo que sería O ( M $O(\log N)$$O(M \log N)$$M$ puntos. Sin embargo, si ordena sus puntos por localidad (como usar primero una curva de Hilbert que ordena), puede inicializar cada nueva consulta con el triángulo de la consulta anterior, para reducir aún más el tiempo de ejecución (no soy un teórico de CS, así que puedo ' No te diré cuál sería el Big-O allí).

Edit2 : Encontré este PDF que describe un esquema de "caminar" que se garantiza que terminará, y revisa los enfoques más ingenuos.

Otra alternativa al uso de quadtrees es usar una jerarquía de triangulación. Ver Olivier Devillers. Mejora de la triangulación aleatoria incremental de Delaunay. En proc. 14to aniversario Simposios ACM. Comput Geom., Páginas 106-115, 1998. Funciona mejor para triangulaciones de Delaunay, pero también puede funcionar para no Delaunay.

Básicamente, cualquier cosa que haga para acelerar la ubicación del punto requerirá la construcción de una estructura de datos auxiliar. En el caso de quadtrees o alguna otra subdivisión espacial, debe construir el árbol de subdivisión. En el caso de salto de borde, debe construir el triángulo adyacente a la estructura topológica. La jerarquía de triangulación también requiere construir un árbol de triangulaciones más gruesas.

No estoy convencido de que su solución sea realmente correcta. Considere la situación en la que tiene estos nodos:

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

Hay triángulos ABC y ACD. Ahora B es el punto más cercano al origen, pero el origen está en el triángulo ACD, que no contiene B.

$O(N \cdot M)$

Consideraría la opción de construir un quadtree que contenga los propios triángulos. Es decir, tiene un árbol cuaternario que se almacena en cada nodo (que corresponde a un cuadro delimitador):

• Las coordenadas en las que se divide el cuadro, o alternativamente, los cuadros delimitadores de los cuatro subárboles;
• Punteros a los subárboles;
• El conjunto de triángulos que se encuentran completamente dentro del cuadro delimitador de este rectángulo, pero no completamente dentro de ninguno de los cuatro subárboles. En otras palabras, los triángulos que se cruzan con cualquiera de los dos segmentos de línea de subdivisión del árbol cuadrangular.

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

CGAL maneja triangulaciones y ubicación de puntos (y mucho más). En particular, el módulo de triangulación 2D puede hacer lo que quiera.