Comment générer la coque non-convexe à partir d'une série de points?

Question

J'essaie actuellement de construire la zone couverte par un appareil sur une période de fonctionnement. La première étape de ce processus semble être la construction d'un polygone de la zone couverte. Étant donné que le motif n'est pas une forme standard, les coques convexes surestiment la zone couverte en sautant vers la plus grande zone de couverture possible.

J'ai trouvé un article qui semble couvrir le concept de génération de coque non-convexe, mais pas de discussions sur la façon de l'implémenter dans un langage de haut niveau. Est-ce que quelqu'un a vu un algorithme simple pour construire une coque non-convexe ou une coque concave ou peut-être n'importe quel code de python pour obtenir le même résultat?

J'ai essayé des coques convexes principalement qhull, avec une taille de bord limitée avec un succès limité. J'ai aussi remarqué des bibliothèques sous licence qui ne pourront pas être distribuées, donc malheureusement, c'est hors de la table. De meilleures idées ou livres de cuisine?

Answer 1

Vous pourriez essayer d'explorer les formes alpha. La bibliothèque CGAL peut les calculer.

Édition: Je vois que le papier que vous avez lié référence des formes alpha et possède également une liste d'algorithmes. N'est-ce pas assez haut niveau pour vous? Puisque vous avez listé Python comme une balise, je suis sûr qu'il y a des bibliothèques de triangulation de Delaunay en Python, ce qui, je pense, est la partie la plus difficile de l'implémentation de l'algorithme; Vous devez juste vous assurer que vous pouvez modifier la sortie de triangulation résultante. Les fonctions de requête de limites peuvent probablement être implémentées avec des tableaux associatifs.

Answer 2

J'ai écrit an application pour calculer la coque non-convexe d'un ensemble de points (vous aurez besoin de java jre pour l'exécuter).