Hispanopedia WikiEn 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.
Motivación
Al realizar simulaciones por computadora, como la dinámica de fluidos computacional , se parte de un modelo, como el contorno bidimensional de una sección de ala. La entrada para un método de elementos finitos bidimensional debe consistir en triángulos que ocupen todo el espacio, y cada triángulo debe estar relleno de un solo 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 suele ser proporcional al número de triángulos, por lo que se busca minimizar su número, utilizando suficientes triángulos para obtener resultados razonablemente precisos, generalmente mediante el uso de una malla no estructurada . La computadora utiliza un algoritmo de mallado para convertir el modelo poligonal en triángulos adecuados para el método de elementos finitos.
Segundo algoritmo de Chew
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 mallar superficies incrustadas en el espacio tridimensional, [ 1 ] el segundo algoritmo de Chew se ha adoptado como un generador de malla bidimensional debido a las ventajas prácticas sobre el algoritmo de Ruppert en ciertos casos y es el generador de malla de calidad predeterminado implementado en el paquete Triangle, disponible gratuitamente. [ 2 ] El segundo algoritmo de Chew garantiza la terminación y produce mallas graduadas en 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 el circuncentro de un triángulo de baja calidad en la triangulación, con una excepción: si el circuncentro se encuentra en el lado opuesto del segmento de entrada al del triángulo de baja calidad, se inserta el punto medio del segmento. Además, se eliminan de la triangulación los circuncentros previamente insertados dentro de la esfera diametral del segmento original (antes de su división). La inserción de circuncentros se repite hasta que no queden triángulos de baja calidad.
El algoritmo de Ruppert
El algoritmo de Ruppert toma un grafo plano de líneas rectas (o, en dimensiones superiores a dos, un sistema lineal a trozos ) y devuelve una triangulación de Delaunay conforme compuesta únicamente por triángulos de calidad. Un triángulo se considera de baja calidad si su relación entre el radio de la circunferencia circunscrita y la arista más corta es mayor que un umbral preestablecido. Descubierto por Jim Ruppert a principios de la década de 1990, [ 4 ] "el algoritmo de Ruppert para la generación de mallas bidimensionales de calidad es quizás el primer algoritmo de mallado teóricamente garantizado que resulta verdaderamente satisfactorio en la práctica". [ 5 ]
Algoritmo
El algoritmo comienza con una triangulación de Delaunay de los vértices de entrada y luego consta de dos operaciones principales.
- El punto medio de un segmento con círculos diametrales no vacíos se inserta en la triangulación.
- El circuncentro de un triángulo de baja calidad se inserta en la triangulación, a menos que dicho circuncentro se encuentre dentro del círculo diametral de algún segmento. En este caso, el segmento invadido se divide.
Estas operaciones se repiten hasta que no existan triángulos de mala calidad y ningún segmento se vea afectado.
- Pseudocódigo
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 : inserta 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 : agregar s a Q ; de lo contrario : insertar el circuncentro de t en T fin si fin si actualizar Q fin mientrasDevuelve T al final Ruppert.
Uso práctico
Sin modificaciones, el algoritmo de Ruppert garantiza la finalización y la generación de una malla de calidad para entradas no agudas y cualquier umbral de baja calidad inferior a unos 20,7 grados. Para flexibilizar estas restricciones, se han realizado varias pequeñas mejoras. Al relajar el requisito de calidad cerca de ángulos de entrada pequeños, el algoritmo puede extenderse para manejar cualquier entrada de línea recta. [ 6 ] Las entradas curvas también pueden mallarse utilizando técnicas similares. [ 7 ] El algoritmo de Ruppert puede extenderse naturalmente a tres dimensiones; sin embargo, sus garantías de salida son algo más débiles debido al tetraedro de tipo sliver.
Una extensión del algoritmo de Ruppert en dos dimensiones se implementa en el paquete Triangle, de libre acceso. Dos variantes del algoritmo de Ruppert incluidas en este paquete garantizan la terminación para un umbral de baja calidad de aproximadamente 26,5 grados. [ 8 ] En la práctica, estos algoritmos funcionan correctamente para umbrales de baja calidad superiores a 30 grados. Sin embargo, se conocen ejemplos que provocan que el algoritmo falle con un umbral superior a 29,06 grados. [ 9 ]
Véase también
Referencias
- ↑ Chew, L. Paul (1993). "Generación de mallas de calidad garantizada para superficies curvas". Actas del Noveno Simposio Anual sobre Geometría Computacional . págs. 274–280 .
- ↑ Shewchuk, Jonathan (2002). "Algoritmos de refinamiento de Delaunay para la generación de mallas triangulares" . Geometría Computacional: Teoría y Aplicaciones . 22 ( 1–3 ): 21–74 . doi : 10.1016/s0925-7721(01)00047-5 .
- ↑ Rand, Alexander (2011). "Dónde y cómo funciona el segundo algoritmo de refinamiento de Delaunay de Chew" (PDF) . Actas de la 23.ª Conferencia Canadiense sobre Geometría Computacional . págs. 157–162 .
- ↑ Ruppert, Jim (1995). "Un algoritmo de refinamiento de Delaunay para la generación de mallas bidimensionales de calidad". Journal of Algorithms . 18 (3): 548– 585. doi : 10.1006/jagm.1995.1021 .
- ↑ Shewchuk, Jonathan (12 de agosto de 1996). "Algoritmo de refinamiento de Delaunay de Ruppert" . Recuperado el 28 de diciembre de 2018 .
- ↑ Miller, Gary; Pav, Steven; Walkington, Noel (2005). "Cuándo y por qué funcionan los algoritmos de refinamiento de Delaunay". International Journal of Computational Geometry and Applications . 15 (1): 25– 54. doi : 10.1142/S0218195905001592 .
- ↑ Pav, Steven; Walkington, Noel (2005). Refinamiento de Delaunay mediante recorte de esquinas . Actas de la 14.ª Mesa Redonda Internacional sobre Mallado. págs. 165–181 .
- ↑ Shewchuk, Jonathan (2002). "Algoritmos de refinamiento de Delaunay para la generación de mallas triangulares" . Geometría Computacional: Teoría y Aplicaciones . 22 ( 1–3 ): 21–74 . doi : 10.1016/s0925-7721(01)00047-5 .
- ↑ Rand, Alexander (2011). "Improved Examples of Non-Termination for Ruppert's Algorithm". arXiv : 1103.3903 [ cs.CG ]..
Lecturas adicionales
- Rineau, Laurent. "Triangulaciones y mallas conformes en 2D" . Consultado el 28 de diciembre de 2018 .
- Shewchuk, Jonathan. "Triangle: Un generador de mallas de calidad bidimensional y triangulador de Delaunay" . Recuperado el 28 de diciembre de 2018 .
- Si, Hang (2015). "TetGen: Un generador de mallas tetraédricas de calidad y un triangulador de Delaunay 3D" . Archivado del original el 29 de diciembre de 2018. Recuperado el 28 de diciembre de 2018 .
{{cite web}}: CS1 maint: bot: estado de la URL original desconocido ( enlace )
- Generación de malla
- Triangulación (geometría)
