Triangulación Poligonal Con Agujeros

Question

Estoy buscando un algoritmo o una biblioteca (mejor) para dividir un polígono en triángulos. Usaré estos triángulos en una aplicación Direct3D. ¿Cuáles son las mejores opciones disponibles?

Esto es lo que he encontrado hasta ahora:

1. notas de Ben Discoe
2. FIST: Triangulación rápida de fuerza industrial de polígonos
3. Sé que CGAL proporciona triangulación, pero no estoy seguro de que sea compatible con agujeros.

Realmente apreciaría algunas opiniones de personas con experiencia previa en esta área.

Editar: este es un polígono 2D.

Answer 1

La biblioteca de triángulos de Jonathan Shewchuk es fenomenal; Lo he usado para automatizar la triangulación en el pasado. Puede pedirle que intente evitar los triángulos pequeños / estrechos, etc., por lo que aparece " bueno " triangulaciones en lugar de cualquier triangulación.

Answer 2

Para ofrecerle más opciones de bibliotecas:

Polyboolean. Nunca probé esto, pero parece prometedor: http: //www.complex-a5. ru / polyboolean / index.html

General Polygon Clipper. Éste funciona muy bien en la práctica y hace triangulación, así como también agujeros de recorte y agujeros: http://www.cs.man.ac.uk/~toby/alan/software/

Mi recomendación personal: use la teselación de la GLU (biblioteca de utilidades OpenGL). El código es sólido como la roca, más rápido que GPC y genera menos triángulos. No necesitas un OpenGL-Handle inicializado ni nada como esto para usar la biblioteca.

Si no te gusta la idea de incluir las librerías del sistema OpenGL en una aplicación DirectX, también hay una solución: simplemente descarga el código de implementación de referencia SGI OpenGL y levanta el triangulador. Solo usa los nombres OpenGL-Typedef y una mano llena de enumeraciones. Eso es. Puede extraer el código y crear una biblioteca independiente en una o dos horas.

---

En general, mi consejo sería usar algo que funcione bien y no comience a escribir su propia triangulación.

Es tentador rodar el tuyo si has leído sobre el algoritmo de recorte de orejas o de línea de barrido, pero el hecho es que los algoritmos de geometría computacional son increíblemente difíciles de escribir de manera que funcionen de manera estable, nunca se bloqueen y siempre regresen Un resultado significativo. Los errores numéricos de redondeo se acumularán y lo matarán al final.

Escribí un algoritmo de triangulación en C para la empresa con la que trabajo. Conseguir que el algoritmo central funcione tomó dos días. Conseguir que funcionara con todo tipo de insumos degenerados tomó otros dos años (no estaba trabajando a tiempo completo en eso, pero confía en mí, dediqué más tiempo al mismo de lo que debería).

Answer 3

CGAL tiene la herramienta que necesitas: Triangulaciones restringidas

Puede simplemente proporcionar límites de su polígono (incluyendo los límites de los agujeros) como restricciones (lo mejor sería que inserte todos los vértices, y luego especifique las restricciones como pares de vértices).

Luego, puede etiquetar los triángulos de la triangulación mediante cualquier algoritmo transversal: comience con un triángulo que incide en el vértice infinito y etiquételo como fuera, y cada vez que cruce una restricción, cambie a la etiqueta opuesta (adentro si anteriormente etiquetaban los triángulos como forastero, afuera si antes etiquetabas triángulos como información privilegiada).

Answer 4

He encontrado que la biblioteca poly2tri es exactamente lo que necesitaba para la triangulación. Produce una malla mucho más limpia que otras bibliotecas que he probado (incluida libtess), y también admite agujeros. Se ha convertido a un montón de idiomas. La licencia es New BSD , por lo que puede usarla en cualquier proyecto.

biblioteca Poly2tri en Google Code

Answer 5

Puedes agregar los agujeros con relativa facilidad. Básicamente, triangule con respecto al casco convexo de los puntos de entrada, según CGAL, y luego elimine cualquier triángulo cuyo incentivo se encuentre dentro de cualquiera de los polígonos de agujero (o fuera de cualquiera de los límites externos). Cuando se trata de un montón de agujeros en un conjunto de datos grande, se pueden usar técnicas de enmascaramiento para acelerar significativamente este proceso.

editar: una extensión común a esta técnica es eliminar los triángulos débiles en el casco, donde el borde más largo o el ángulo interno más pequeño excede un valor dado. Esto formará un mejor casco cóncavo.

Answer 6

prueba libtess2

https://code.google.com/p/libtess2/downloads/list

basado en el tesselator SGI GLU original (con licencia liberal). Resuelve algunos problemas de administración de memoria en torno a muchos mallocs pequeños.

Answer 7

Este es un problema común en el análisis de elementos finitos. Se llama "generación automática de malla". Google encontró este sitio con enlaces a fuentes comerciales y de código abierto software. Por lo general, suponen algún tipo de representación CAD de la geometría para comenzar.

Answer 8

Otra opción (con una licencia muy flexible) es transferir el algoritmo desde VTK:

vtkDelaunay2D

Este algoritmo funciona bastante bien. Es posible usarlo directamente, pero requiere enlaces a VTK, que pueden tener más sobrecarga de la que desea (aunque también tiene muchas otras características interesantes).

Admite restricciones (agujeros / límites / etc), así como triangular una superficie que no está necesariamente en el plano XY. También es compatible con algunas funciones que no he visto en ningún otro lugar (consulte las notas sobre los valores Alpha).

Answer 9

He implementado un polígono 3D triangulator en C # utilizando el método de recorte de orejas. Es fácil de usar, admite orificios, es numéricamente robusto y es compatible con polígonos convexos / no convexos (no intersección).