Generador de Triangulación de Delaunay

El Generador de Triangulación de Delaunay convierte cualquier conjunto de puntos 2D en la triangulación única que maximiza el ángulo interior más pequeño, el estándar de oro para el modelado de terrenos, el mallado de elementos finitos, la interpolación del vecino más cercano y las aulas de geometría computacional. Pegue las coordenadas (o elija un patrón de inicio rápido), y la herramienta ejecuta el algoritmo de Bowyer-Watson del lado del servidor, colorea cada triángulo según su calidad y muestra la propiedad de la circunferencia circunscrita vacía, la envoltura convexa y el dual de Voronoi a pedido.

Cómo leer la malla generada

Qué hace diferente a este triangulador de Delaunay

¿Qué es una triangulación de Delaunay?

Dado un conjunto de puntos 2D, generalmente existen muchas formas de conectarlos en una triangulación (un mosaico completo de su envoltura convexa mediante triángulos sin superposiciones ni espacios). La triangulación de Delaunay, nombrada en honor al matemático ruso Boris Delaunay (1934), es la que satisface la propiedad de la circunferencia circunscrita vacía: para cada triángulo en la malla, el círculo que pasa por sus tres vértices no contiene ningún otro punto de entrada. Esta única propiedad tiene una consecuencia notable: entre todas las triangulaciones del mismo conjunto de puntos, la de Delaunay maximiza el ángulo interior más pequeño. En lenguaje sencillo, produce los triángulos más "anchos" y "equilibrados" posibles.

Cómo funciona el algoritmo de Bowyer-Watson

1. Rodee todos los puntos de entrada con un súper triángulo muy grande.
2. Inserte un punto de entrada a la vez. Para cada punto nuevo, busque cada triángulo existente cuya circunferencia circunscrita contenga el nuevo punto; estos son los triángulos "malos".
3. Elimine los triángulos malos. El agujero que dejan atrás tiene un límite poligonal.
4. Conecte el nuevo punto a cada borde de ese límite, formando nuevos triángulos.
5. Después de insertar todos los puntos, elimine cualquier triángulo que todavía toque un vértice del súper triángulo. Lo que queda es la triangulación de Delaunay del conjunto de puntos original.

Dónde se utiliza la triangulación de Delaunay

• Modelado de terrenos (SIG): las muestras de elevación (generalmente espaciadas de manera irregular, como las estaciones de terreno) se conectan en una Red Irregular de Triángulos (TIN) para consultas de elevación, sombreado y visualización en 3D.
• Análisis de elementos finitos: los triángulos de Delaunay bien formados producen soluciones numéricas estables para ecuaciones diferenciales parciales en mecánica, transferencia de calor y electromagnetismo.
• Gráficos por computadora: generación de mallas para renderizado, modelado de personajes (rigging) y terreno procedimental; la garantía de Delaunay de "sin triángulos delgados" evita artefactos de estiramiento de texturas.
• Interpolación del vecino natural: se reconstruyen superficies lisas a partir de muestras dispersas calculando los vecinos naturales de cada punto de consulta a través del dual de Voronoi.
• Clases de geometría computacional: un algoritmo canónico con profundas conexiones con envolturas convexas, diagramas de Voronoi, localización de puntos y el enfoque de divide y vencerás.
• Laminadores de impresión 3D y trayectorias de herramientas CNC: Delaunay 2D (y su primo 3D, la tetraedrización de Delaunay) sirve de base para muchas estrategias de laminado y relleno.

Delaunay vs Voronoi: Dos caras de la misma moneda

El diagrama de Voronoi divide el plano en una celda por punto de entrada, donde cada celda contiene todo lo que está más cerca de su punto que de cualquier otro. Al conectar los puntos cuyas celdas comparten un límite, se obtiene exactamente la triangulación de Delaunay. Por el contrario, los circuncentros de los triángulos de Delaunay adyacentes, unidos por segmentos de línea, forman las aristas de Voronoi. Active "Dual de Voronoi" en esta herramienta para ver las líneas discontinuas naranjas superpuestas en el mismo gráfico: cada arista de Delaunay cruza exactamente una arista de Voronoi en ángulos rectos.

Calidad, triángulos delgados y refinamiento de malla

Delaunay maximiza el ángulo interior mínimo global, pero no puede solucionar una distribución de puntos fundamentalmente mala. Si sus puntos de entrada son casi colineales, están agrupados o dejan grandes regiones vacías, algunos triángulos seguirán siendo delgados (ángulo mínimo por debajo de 20°). La solución es la inserción de puntos de Steiner: algoritmos como el algoritmo de Ruppert y el segundo algoritmo de Chew añaden de forma iterativa nuevos puntos en el circuncentro de los triángulos delgados, retriangulando cada vez, hasta que cada triángulo cumpla con un límite de calidad objetivo. Este generador le muestra cuáles triángulos son delgados para que sepa dónde agregar puntos de Steiner si desea una malla más fina.

Ejemplo práctico

Haga clic en el ajuste preestablecido "Círculo + centro". La herramienta coloca 18 puntos alrededor de un círculo y 1 punto en el centro, y los triangula. El resultado es un abanico perfecto de 18 triángulos isósceles que se encuentran en el centro: cada uno tiene ángulos de 10° en el borde y 80°–80° en el centro. El peor ángulo mínimo es de 10°, todos los triángulos están marcados como delgados y el histograma muestra todo en el contenedor de 0°–10°. El ejemplo es un excelente caso de enseñanza: incluso la triangulación óptima de Delaunay puede tener triángulos delgados cuando la entrada los fuerza. Ahora haga clic en "Nube aleatoria": el mismo algoritmo produce triángulos bien formados porque los puntos están distribuidos de manera uniforme, y el histograma se desplaza hacia la derecha.

Conceptos erróneos comunes

• "La triangulación de Delaunay es única": por lo general sí, pero si cuatro puntos de entrada son cocirculares (todos se encuentran en el mismo círculo), existen dos triangulaciones de Delaunay válidas para ese grupo. El generador elige una de manera constante.
• "Más puntos siempre significan mejor calidad": agregar puntos mal colocados puede introducir nuevos triángulos delgados. Los algoritmos de puntos de Steiner colocan nuevos puntos con cuidado —en los circuncentros— por lo que se garantiza que la calidad mejorará.
• "Delaunay es lo mismo que una envoltura convexa": no. La envoltura convexa es el límite exterior; la triangulación de Delaunay rellena el interior con triángulos.
• "Todas las triangulaciones se ven casi iguales": la diferencia es drástica. Un "intercambio" de una arista de Delaunay puede convertir un triángulo de 25° en uno de 5°. El mapa de calor de calidad de la herramienta hace visible la diferencia.

Preguntas frecuentes