Construire le contour d'un polygone (en particulier une triangulation)

Question

Comment puis-je construire le contour du polygone 2d constitué uniquement de triangles et pouvant comporter des trous; le contour externe peut être concave / convexe et les trous pouvant également être concaves / convexes.

D'après ce que je lis ici , il semble que ce soit exactement l'inverse de la problème de triangulation. Connaissez-vous des articles traitant de ce type de problème?

Les octrees / quadtrees sont-ils pertinents à cet égard?

Answer 1

Je suppose que vous avez des données sous la forme d'ensembles de trois points, qui constituent un & "rempli &"; triangle, que ces triangles sont contigus le long des arêtes et que tous les sommets qui constitueront des angles de la forme complète sont également les sommets de tous les triangles qui touchent ce point. Il vous suffira alors de trouver toutes les arêtes qui ne sont pas doublées, c'est-à-dire qui n'appartiennent pas à deux triangles contigus.

Answer 2

Je pense que vous pouvez résoudre votre problème en créant une structure de données topologiques représentant votre ensemble de triangles, puis en utilisant cette structure pour effectuer une itération sur les bords du triangle situés sur la limite.

Par exemple: vous pouvez créer une structure de données halfedge. En supposant que vous insériez des demi-pointes même sur la limite (correctement), itérer sur le contour est aussi simple que de localiser une demi-arête sur la limite, puis de la parcourir au-dessus de & "; Suivant &"; pointeur jusqu’à ce que vous reveniez au demi-point de départ.

De la même manière que les demi-pointes, vous pouvez utiliser d'autres structures topologiques telles que les bords ailés, etc.