Algoritmo para crear triángulos adyacentes.

14

Tengo un sistema donde puedes hacer clic una vez para colocar un nodo en una escena. Cuando coloca 3 nodos, forma un triángulo. Cuando coloca nodos futuros, crea un nuevo triángulo uniendo ese nodo a los 2 nodos existentes más cercanos.

Esto funciona bien la mayor parte del tiempo, pero es defectuoso cuando se usa cerca de triángulos con ángulos muy agudos, porque uno de los 2 nodos más cercanos a menudo no es uno que deba usarse.

Por ejemplo, vea la imagen a continuación. El triángulo magenta es el primero colocado. Si luego hago clic en la posición marcada como X, lo que obtengo es un nuevo triángulo donde está la superposición azul. Lo que quiero es un nuevo triángulo donde esté la superposición verde. (es decir, simétrico al magenta, en este ejemplo. Aclaración: los triángulos verde y magenta no se superponen; el verde se extiende debajo del azul hasta el nodo más a la izquierda)

Ejemplo de comportamiento real y deseado.

¿Cómo puedo determinar qué 2 vértices existentes usar al crear nuevos triángulos para que los triángulos no se superpongan de esta manera?

EDITAR : Buscar el borde más cercano da mejores resultados, pero no los perfectos. Considere esta situación:

ingrese la descripción de la imagen aquí

La prueba del "borde más cercano" es ambigua y puede devolver AB o AC (ya que el punto más cercano a X para ambos está en A). El resultado deseado sería AC, para formar el triángulo ACX sin bordes superpuestos. ¿Cómo podría asegurar este resultado? (Preferiría no tener que realizar pruebas de superposición de bordes individuales como un desempate si es posible, ya que me preocupa que la prueba de borde más cercana no necesariamente detecte que los 2 son exactamente equidistantes, dados los problemas de precisión de coma flotante).

Kylotan
fuente
¿No es suficiente mirar los últimos 5 vértices colocados y seleccionar los dos más cercanos al vértice recién colocado? Le señalaría los algoritmos para las tiras triangulares ( codercorner.com/Strips.htm ), pero a menudo solo usan las dos últimas o las últimas tres omitiendo una.
Roy T.
1
¿El triángulo verde se superpone al magenta? ¿Cuál es el objetivo de esto? ¿Necesita el usuario controlar dónde y cómo se crean los triángulos o sería aceptable la triangulación de una nube de puntos?
bummzack
Para poner esto en un contexto gráfico, ¿esencialmente desea conectar sus nodos, sin que se superpongan los bordes? (Asumiendo que los triángulos magenta / verde compartirían una ventaja)
MichaelHouse
Roy T: no, simplemente elegir los 2 más cercanos está mal, como pensé que muestra el ejemplo. ¿Algo no está claro? Bummzack: el verde no se superpone con el magenta. El objetivo es hacer una malla o gráfico de estos triángulos. El usuario necesita control, sí. Byte56: sí, no se deben cruzar bordes.
Kylotan
2
¿Verá realmente el usuario los triángulos individuales? ¿O va a ser una superficie continua?
bummzack

Respuestas:

11

En lugar de encontrar la distancia mínima a los nodos, encuentre la distancia mínima al borde (es decir, el segmento de línea definido por los nodos).

Luego, si el punto más cercano es un vértice (que tendrá que usar una prueba epsilon ** de coma flotante), compare el ángulo entre la línea desde el nuevo punto hasta el vértice y cada uno de los bordes conectados a ese vértice. Elija el que tenga el ángulo absoluto mínimo:

MinAngle(newPoint, vertex, edge1, edge2)
{
   newEdgeUnit = norm(newPoint - vertex); // don't actually need to normalize this
   edge1Unit = norm(edge1 - vertex);      // you probably have these from your dist to line tests
   edge2Unit = norm(edge2 - vertex);

   edge1Dot = dot(edge1Unit, newEdgeUnit);
   edge2Dot = dot(edge2Unit, newEdgeUnit);

   // you can simply compare dot products to find the minimum absolute angle
   if (edge1Dot > edge2Dot) return edge1;     // set up this way so you can generalize to an array
   return edge2;
}

** Para evitar agregar triángulos degenerados, que podrían interrumpir la prueba de épsilon, es posible que desee colocar una región alrededor de cada vértice donde no se permiten agregar puntos (algo así como no permitir puntos dentro de algún múltiplo del épsilon utilizado anteriormente).

Jeff Gates
fuente
3
+1: esta es en mi humilde opinión una respuesta mucho más directa que las otras, y es más probable que proporcione los resultados correctos. La distancia al segmento también es fácil de calcular, con un esquema inteligente.
Steven Stadnicki
De acuerdo, este es un método más limpio. Probablemente a lo que habría llegado si lo hubiera pensado más: /
MichaelHouse
¡Ah, qué cerca! Pero, al igual que con la respuesta de Byte56 y el diagrama de Jimmy, a veces hay 2 bordes equidistantes, y uno de ellos viola las restricciones. He actualizado mi pregunta.
Kylotan
@Kylotan ¿Quizás en ese caso, simplemente verificar cuál se superpone y tomar la otra opción? Busque triángulos que compartan el borde que eligió y verifique si su nuevo triángulo está en el mismo lado de ese borde que el existente.
Kevin Reid
@Kylotan ¿Se asegura de que sus triángulos siempre tengan el mismo devanado? En caso afirmativo, puede descartar el borde que tiene un apunte normal lejos de su nuevo vértice (usando punto-producto).
bummzack
6

Después de colocar el primer triángulo, al colocar un nuevo vértice, siempre generará dos bordes nuevos. El tercer borde para el nuevo triángulo siempre será un borde compartido con un triángulo anterior. Si pudiera encontrar una manera de determinar el borde compartido, sabría a qué vértices conectarse, pero esa es la parte difícil. Creo que de una manera puedes hacer esto dibujando una línea desde tu nuevo vértice hasta el centro de cada uno de los últimos tres bordes generados (o probablemente los 3 bordes más cercanos).

ingrese la descripción de la imagen aquí

Si la línea desde su vértice hasta el centro del borde no cruza ninguno de los otros dos bordes, tiene su borde compartido. El borde compartido le dirá a qué dos vértices conectar su nuevo vértice.

Jimmy planteó el caso por un punto que es ambiguo en cuanto a dónde iría el nuevo triángulo así:

triángulo ambiguo

Eso le daría la oportunidad de elegir entre dos triángulos válidos. Quizás el desempate sea cuál es el punto central más cercano.

Teniendo en cuenta su actualización, aunque es más compleja, mi solución solo resultará en un empate cuando tenga dos triángulos válidos. Usando este método, su segunda imagen de ejemplo produciría el resultado que desea.

ingrese la descripción de la imagen aquí

MichaelHouse
fuente
Es posible tener una situación en la que dos de las líneas no se cruzan con los bordes (cuando X está más cerca de un vértice que del borde)
Jimmy
@ Jimmy, ¿puedes dibujar una imagen de tal situación?
MichaelHouse
Ah sí, ¡entonces tienes dos opciones de dónde colocar el triángulo! Cualquier lado funcionaría. Quizás pueda vincular el break con el que tenga la distancia más corta al centro.
MichaelHouse
@Kylotan ¿esta solución no funciona? Usted mencionó en un comentario a Jeff que la imagen de Jimmy tiene dos casos y uno viola las restricciones, pero eso no es cierto. En la imagen de Jimmy, los dos casos producirían triángulos válidos utilizando mi método.
MichaelHouse
1

Con tu triángulo magenta ABC, incorporas un nuevo vértice X. Creo que es obvio que habrá dos líneas que comienzan en D que no se intersecarán entre ninguno de los bordes del triángulo ABC.

Estas dos líneas pueden ser AX y BX, BX y CX o AX y CX. Entonces puede tratar su problema como el problema clásico de "¿se cruzan dos líneas"? Luego puede verificar cuál de estos pares de líneas no se cruza con ninguno de los bordes del triángulo ABC siguiendo, por ejemplo, cualquiera de los métodos de esta pregunta . Por lo tanto, tendrá los dos nuevos bordes del nuevo triángulo.

Dan
fuente
Esto parece bueno, pero la forma en que lo has dicho parece suponer que solo hay un triángulo existente. ¿Cómo se generalizaría a muchos?
Kylotan
Hum ... si tu X y tu triángulo ABC son fijos, supongo que solo hay uno, ¿no?
Dan
El sistema crea un nuevo triángulo para cada nodo después del segundo.
Kylotan
Lo siento, no entendí tu pregunta. Déjame ver cómo puedo extender esto a muchos triángulos.
Dan
Bueno, supongo que podrías buscar los dos vértices más cercanos a X que no cruzan ningún borde cuando estás conectado a X.
bummzack
1

Averiguar si estás en una de las regiones inequívocas (1, 2, 3 a continuación) es bastante fácil: trata cada borde de tu triángulo como un plano 2D y prueba en qué lado del plano está tu nuevo punto. Si estás dentro de dos de ellos pero fuera de uno, ese corresponde al borde del triángulo que aporta dos vértices a tu nuevo triángulo.

Regiones Voronoi de un triángulo

Si estás dentro de uno y fuera de dos, estás en el caso ambiguo donde la parte más cercana del triángulo a tu nuevo punto es una esquina. En ese caso, puede formar un plano 2D desde el punto medio del borde opuesto (el que está dentro) y el vértice más cercano (el que comparten los dos planos fuera del que está). Puede elegir una arista dependiendo de qué lado de este plano esté su nuevo punto.

Tenga en cuenta que una prueba de plano en 2D funciona de la misma manera que en 3D: puntee un vector desde cualquier parte del plano hasta su punto con la normal del plano (en 2D, esta es la línea perpendicular).

(Por cierto, las regiones delimitadas por magenta en esta imagen se denominan regiones de Voronoi; son las áreas del espacio que contienen puntos que están más cerca de una característica particular (borde o vértice) del triángulo. Editar: Mi terminología aquí no es realmente bastante correcto, estas no son exactamente regiones de Voronoi).

John Calsbeek
fuente
No tengo claro de inmediato cómo esto se generaliza a múltiples triángulos en la escena, especialmente si la característica más cercana es un vértice que puede ser compartido por más de 1 triángulo.
Kylotan
@Kylotan Simplemente ejecute el algoritmo para todos los triángulos y elija la característica más cercana en general. Necesitas algo de lógica de desempate sin importar qué. Si terminas con la entidad más cercana como un vértice compartido, entonces deberías estar en la región del borde (# 1, # 2, # 3) para un solo triángulo, entonces ¿tal vez puedas elegir eso?
John Calsbeek