En la generación de mallas , los refinamientos de Delaunay son algoritmos para la generación de mallas basados en el principio de agregar puntos de Steiner a la geometría de una entrada que se va a mallar, de manera que la triangulación de Delaunay o la triangulación de Delaunay restringida de la entrada aumentada cumpla con los requisitos de calidad de la aplicación de mallado. Los métodos de refinamiento de Delaunay incluyen los métodos de Chew y de Ruppert.
El segundo algoritmo de Chew toma un sistema lineal por partes (PLS) y devuelve una triangulación de Delaunay restringida de solo triángulos de calidad donde la calidad se define por el ángulo mínimo en un triángulo. Desarrollado por L. Paul Chew para generar mallas de superficies incrustadas en un espacio tridimensional, [1] el segundo algoritmo de Chew se ha adoptado como un generador de mallas bidimensionales debido a las ventajas prácticas sobre el algoritmo de Ruppert en ciertos casos y es el generador de mallas de calidad predeterminado implementado en el paquete Triangle disponible de forma gratuita . [2] Se garantiza que el segundo algoritmo de Chew terminará y producirá mallas con clasificación de tamaño de característica local con un ángulo mínimo de hasta aproximadamente 28,6 grados. [3]
El algoritmo comienza con una triangulación de Delaunay restringida de los vértices de entrada. En cada paso, se inserta en la triangulación el circuncentro de un triángulo de mala calidad, con una excepción: si el circuncentro se encuentra en el lado opuesto de un segmento de entrada que el triángulo de mala calidad, se inserta el punto medio del segmento. Además, se eliminan de la triangulación todos los circuncentros insertados previamente dentro de la esfera diametral del segmento original (antes de que se divida). La inserción del circuncentro se repite hasta que no existan triángulos de mala calidad.
El algoritmo de Ruppert toma un gráfico de línea recta plana (o de dimensión superior a dos en un sistema lineal por partes ) y devuelve una triangulación de Delaunay conforme con solo triángulos de calidad. Se considera que un triángulo es de mala calidad si tiene una relación entre el radio circunscrito y el borde más corto mayor que un umbral prescrito. Descubierto por Jim Ruppert a principios de la década de 1990, [4] "el algoritmo de Ruppert para la generación de mallas de calidad bidimensionales es quizás el primer algoritmo de mallado con garantía teórica que es verdaderamente satisfactorio en la práctica". [5]
Al realizar simulaciones por computadora, como dinámica de fluidos computacional , se comienza con un modelo como un contorno 2D de una sección de ala. La entrada a un método de elementos finitos 2D debe estar en forma de triángulos que llenen todo el espacio, y cada triángulo debe llenarse con un tipo de material: en este ejemplo, "aire" o "ala". Los triángulos largos y delgados no se pueden simular con precisión. El tiempo de simulación generalmente es proporcional al número de triángulos, por lo que se desea minimizar el número de triángulos, mientras se siguen utilizando suficientes triángulos para dar resultados razonablemente precisos, generalmente mediante el uso de una cuadrícula no estructurada . La computadora utiliza el algoritmo de Ruppert (o algún algoritmo de malla similar) para convertir el modelo poligonal en triángulos adecuados para el método de elementos finitos.
El algoritmo comienza con una triangulación de Delaunay de los vértices de entrada y luego consta de dos operaciones principales.
Estas operaciones se repiten hasta que no existan triángulos de mala calidad y no se invadan todos los segmentos.
La función Ruppert( puntos , segmentos , umbral ) es T := DelaunayTriangulation( puntos ) Q := el conjunto de segmentos invadidos y triángulos de mala calidad mientras Q no esté vacío: // El bucle principal si Q contiene un segmento s : inserte el punto medio de s en T, de lo contrario Q contiene un triángulo t de mala calidad : si el circuncentro de t invade un segmento s : añadir s a Q ; de lo contrario : inserta el circuncentro de t en T fin si fin si actualiza Q fin mientras volver T fin Ruppert.
Sin modificación, el algoritmo de Ruppert garantiza la terminación y la generación de una malla de calidad para entradas no agudas y cualquier umbral de mala calidad menor a aproximadamente 20,7 grados. Para relajar estas restricciones se han realizado varias pequeñas mejoras. Al relajar el requisito de calidad cerca de ángulos de entrada pequeños, el algoritmo se puede extender para manejar cualquier entrada en línea recta. [6] La entrada curva también se puede mallar utilizando técnicas similares. [7] El algoritmo de Ruppert se puede extender naturalmente a tres dimensiones, sin embargo, sus garantías de salida son algo más débiles debido al tetraedro de tipo astilla.
Una extensión del algoritmo de Ruppert en dos dimensiones se implementa en el paquete Triangle , disponible de forma gratuita . Se garantiza que dos variantes del algoritmo de Ruppert en este paquete finalizan con un umbral de mala calidad de aproximadamente 26,5 grados. [8] En la práctica, estos algoritmos son exitosos con umbrales de mala calidad superiores a 30 grados. Sin embargo, se conocen ejemplos que hacen que el algoritmo falle con un umbral mayor de 29,06 grados. [9]