Construyendo el contorno de un polígono (en particular una triangulación)

Question

¿Cómo haría para construir el contorno del polígono 2D que está formado solo por triángulos y puede tener agujeros y el contorno externo puede ser cóncavo / convexo y los agujeros también pueden ser cóncavos / convexos.

De lo que estoy leyendo aquí parece que es exactamente lo contrario de problema de triangulación ¿Conoces algún artículo que trate este tipo de problema?

¿Son relevantes los octrees / quadtrees para esto?

Answer 1

Supongo que tiene datos en forma de conjuntos de tres puntos, que constituyen un & "; lleno &"; triángulo, que estos triángulos están unidos a lo largo de los bordes, y que todos los vértices que serán esquinas de la forma completa también son vértices de todos los triángulos que tocan este punto. Entonces solo tendría que encontrar todos los bordes que no estén duplicados, es decir, que no pertenezcan a dos triángulos adyacentes.

Answer 2

Creo que puede resolver su problema creando una estructura de datos topológicos para representar su conjunto de triángulos, y luego usando esa estructura para iterar en orden sobre los bordes del triángulo que se encuentran en el límite.

Por ejemplo: puede crear una estructura de datos de medio borde. Suponiendo que inserta medios bordes incluso en el límite (correctamente), iterar sobre el contorno del límite es tan simple como ubicar un medio borde en el límite y luego iterar sobre él & "; Siguiente &"; puntero hasta que regrese al medio punto desde el que comenzó.

De manera similar a los halfedges, puede usar otras estructuras topológicas como borde con alas, etc., pero el concepto es el mismo.