Trianguler un ensemble de points avec un domaine concave

Question

de configuration

Étant donné un certain ensemble de noeuds à l'intérieur d'une coque convexe, supposons que le nom de domaine contient une ou plusieurs zones concaves:

où des points bleus sont points, et la ligne noire illustre le domaine. Supposons que les points sont conservés sous la forme d'un tableau 2D points de longueur n, où n est le nombre de paires de points.

Laissez-nous triangule alors les points, en utilisant quelque chose comme la méthode de Delaunay scipy.spatial:

Comme vous pouvez le voir, on peut expérimenter la création de triangles qui traversent le domaine.

Question

Qu'est-ce qu'une bonne approche algorithmique de supprimer des triangles qui s'étendent en dehors du domaine? Idéalement mais pas nécessairement, là où les bords simplex conservent toujours la forme du domaine (c'est-à-dire, pas de trous majeurs où les triangles sont supprimés).

Answer 1

L'un des algorithmes classiques DT génère un premier triangle de délimitation, puis ajoute tous les nouveaux triangles triés par x, puis les pruneaux sur tous les triangles ayant un sommet dans le supertriangle.

Au moins à partir de l'image fournie, on peut déduire les heuristiques de l'élagage sur certains triangles ayant tous les sommets sur la coque concave. Sans preuve, les triangles à élaguer ont une zone négative lorsque leurs sommets sont triés dans le même ordre que la coque concave est définie.

Il peut être nécessaire d'insérer également la coque concave et de la tailler.

Answer 2

Calculer le centroïde des triangles et vérifier s'il se trouve à l'intérieur du polygone en utilisant this algorithm.

Answer 3

Vous pouvez essayer un algorithme contraint delaunay par exemple avec slogan algoritm ou bibliothèque cgal.

[1] A Brute-Force Constrained Delaunay Triangulation?