Algorithme

• Trianguler d'abord l'envelope convexe du domaine par l'algorithme précédent.
• Pour toute arête frontière e de D qui ne serait pas une arête de la triangulation, trouver tous les triangles coupés par e. Ils forment un polygone Pe. Considerer Pe comme la reunion de 2 polygones, l'un Ped à droite de Pe, l'autre Pel à gauche.
• Appliquer le présent algorithme récursivement à Pel et Ped.
• Retirer tous les triangles ayant pour sommet un point du type qN+1,...,qN+4.
• Retirer tous les triangles adjacent par une arête et à droite de la frontière de D.

Pour construire les polygones Pe, le mieux est de partir d'une extrémité d'arête, de parcourir la liste des triangles ayant ce point pour sommet (cf le champ supp dans la classe Vertex), de calculer leurs intersection avec e et de prendre l'autre triangle adjacent par l'arête qui coupe e, etc jusqu'a ce qu'on arrive à l'autre extrémité de l'arête e.