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

16

Supongamos que tengo una malla 2D que consiste en triángulos que no se superponen , y un conjunto de puntos { p i } M i = 1N k = 1 T K . ¿Cuál es la mejor manera de determinar en qué triángulo se encuentra cada uno de los puntos?{Tk}k=1norte{pagyo}yo=1METROk=1norteTK

Por ejemplo, en la siguiente imagen tenemos , p 2T 4 , p 3T 2 , por lo que me gustaría una función f que devuelva la lista f ( p 1 , p 2 , p 3 )pag1T2pag2T4 4pag3T2F .F(pag1,pag2,pag3)=[2,4 4,2]

ingrese la descripción de la imagen aquí

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 ) .pagyopagyoO(norteMETRO)

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 gpagyo , 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(unMETROlosol(norte))un

  • 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!

Nick Alger
fuente

Respuestas:

16

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 logO(Iniciar sesiónnorte)O(METROIniciar sesiónnorte)METRO 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.

Victor Liu
fuente
Victor: ¿conoces algún código de código abierto que implique el enfoque de salto de borde? Parece elegante, podría ser una muy buena solución para mi caso. (modelo de seguimiento de partículas impulsado por campos actuales en una cuadrícula de malla traingualr) -Gracias
Chris Barker
Tengo un código para esto y puedo enviárselo; Está en C / C ++. Aún no he tenido tiempo de limpiarlo y publicarlo en Github. He tenido que escribir esto al menos dos veces en mi vida, una vez con una estructura de datos de medio borde, otra vez con un quadedge, pero puede usarse fácilmente cuando no están disponibles y usted necesita construir una estructura topológica usted mismo. Busque en mi página de perfil mi sitio web, donde puede encontrar información de contacto. Podemos discutir esto más adelante sin conexión.
Victor Liu
Estoy cerca de terminar de implementar esto en matlab usando el orden de la curva de Hilbert y el recorrido del triángulo aleatorio. Es un código de investigación: no está optimizado, no está documentado, etc., pero sigue siendo bastante rápido: puedo darle el código si está interesado.
Nick Alger
2
Acerca de: "" "el salto de borde debería ser O (logN)" "" No veo eso. Por ejemplo, en el caso patológico de una gran franja triangular larga (como un canal estrecho solo en un triángulo ancho), en el peor de los casos, necesitaría saltar de un triángulo al siguiente hasta el final. En el caso promedio, a mitad de camino. Por lo tanto, si duplica el número de triángulos, sería O (N) En el caso más normal de una disposición de triángulos al cuadrado, esperaría O (sqrt (N)). ¿O me estoy perdiendo algo? -Chris
Chris Barker
@Chris - ¡Bienvenido a scicomp! Como parte del servicio de limpieza de scicomp, he migrado sus respuestas y la conversación posterior como comentarios sobre la respuesta de Victor. Esperamos su participación en el sitio.
Aron Ahmadia
8

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(norteMETRO)

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.

nortenorteIniciar sesiónnorteO(norteMETRO)

Erik P.
fuente
Hmm tienes razón. Por otro lado, si la triangulación fuera Delaunay, creo que el vecino más cercano funcionaría. Es demasiado restrictivo para lo que estoy tratando de hacer, pero en el caso de Delaunay considere el doble diagrama de Voronoi: las celdas de Voronoi son el conjunto de puntos más cercanos a un nodo, y los bordes de los triángulos de Delaunay se encuentran con los bordes del Voronoi. celdas en ángulo recto, por lo que cualquier punto debe estar en un triángulo conectado a su nodo más cercano. Me pregunto si así es como funciona la función pointLocation de matlab bajo el capó ...
Nick Alger
1

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.

Ronaldo Carpio
fuente