Je recherche une implémentation python pour le problème de la coque concave. Mon problème est un peu différent car je n'ai pas un ensemble de points, mais un ensemble de lignes, où le résultat Concave-Hull sera à peu près lié le long des lignes (comme dans le dessin de gauche). 
Je comprends qu'il n'y a pas une seule «bonne réponse». Mais une certaine approximation suffira à mes besoins. Une solution possible est de prendre chaque ligne et de l'interpoler sur une plage de disons 20 points et de trouver la coque concave de tous les points créés. Je n'en suis pas sûr.
Éditer:
Je pense que les lignes ajoutent de la valeur, rendant la coque plus claire et plus facile à trouver.
Une bonne implémentation python pour le problème, même si vous n'utilisez pas les lignes (trouver simplement une coque concave à partir d'une liste de points) sera également utile
3 Réponses :
Voici un repo github sur la recherche de la coque concave pour un ensemble de points à l'aide de python.
Ma recommandation est la suivante. Créez un ensemble de points en utilisant les extrémités de chaque ligne. Ensuite, utilisez le code lié pour générer une coque concave pour ces points, avec une estimation de la valeur alpha. Une fois cela fait, vous pouvez vérifier si la coque générée coupe l'une de vos lignes et si elle modifie l'alpha. Vous pouvez automatiser la vérification des intersections et des réglages si vous le souhaitez.
Vous pouvez également essayer d'ajouter les points médians de vos lignes à votre ensemble de points, ce qui peut réduire le nombre d'alphas que vous devez essayer.
Voici une réponse à votre sous-question:
Une bonne implémentation python pour le problème, même si vous n'utilisez pas les lignes (trouver simplement une coque concave à partir d'une liste de points) sera également utile
Vous pouvez utiliser alphashape . Le plus délicat est de choisir un alpha qui correspond à vos besoins. Alphashape est livré avec une fonction pour trouver la valeur alpha optimale. Fondamentalement, il commence par 0 (= coque convexe) et augmente l'alpha jusqu'à ce qu'il commence à perdre des points. De cette valeur optimale, nous prenons 95%, ce qui est, bien sûr, une solution plutôt arbitraire, mais cela vous donnera une bonne approximation dans de nombreux cas.
import alphashape import matplotlib.pyplot as plt from descartes import PolygonPatch points = [(17, 158),(15, 135),(38, 183),(43, 19),(93, 88),(96, 140),(149, 163),(128, 248),(216, 265),(248, 210),(223, 167),(256, 151),(331, 214),(340, 187),(316, 53),(298, 35),(182, 0),(121, 42)] alpha = 0.95 * alphashape.optimizealpha(points) hull = alphashape.alphashape(points, alpha) hull_pts = hull.exterior.coords.xy fig, ax = plt.subplots() ax.scatter(hull_pts[0], hull_pts[1], color='red') ax.add_patch(PolygonPatch(hull, fill=False, color='green'))
Une solution possible est de prendre chaque ligne et de l'interpoler sur une plage de disons 20 points et de trouver la coque concave de tous les points créés.
Cela ne vous donnera pas le résultat souhaité car la coque concave suivra ces (faux) points supplémentaires et deviendra plus concave qu'elle ne peut l'être avec les points d'origine.
Je pense que la meilleure solution pour tout le problème est de commencer par la coque concave des points pour l'alpha optimal obtenu à partir d' optimizealpha , puis de la diminuer jusqu'à ce que votre coque ne coupe aucune de vos lignes comme suggéré par @sgillen. Cela peut être fait de la même manière que pour trouver l'alpha optimal en utilisant une boucle de bissection en testant any([polygon.crosses(line) for line in lines]) .
Je pense alphashape ne prend en charge que python 3.
Bien que cette question puisse déjà trouver une réponse, voici également mon approche:
Comme les autres l'ont également dit, vous devez d'abord convertir les extrémités des lignes en une liste de points.
Après cela, vous pourriez avoir besoin de cette fonction bien rangée de la bibliothèque SciPy: scipy.spatial.ConvexHull() . Fondamentalement, vous passez simplement un tableau numpy avec les sommets à la fonction (créé avec numpy.array() ) et il retourne un hull-Object
Voici la documentation
Avec l' .points .points, vous pouvez soit obtenir tous les points, soit avec l' .vertices .vertices, vous pouvez obtenir les indices de la liste d'entrée qui forment la coque. Vous pouvez également obtenir des éléments tels que Surface ou Volume (pour les formes 3D) si cela vous intéresse.
~ Okaghana
Je pense que l'OP demande une coque concave.
Ne pourriez-vous pas créer un ensemble de points basé sur les extrémités des lignes? Ensuite, ce serait le même que le problème de coque concave «normal».
Premièrement, j'ai toujours besoin d'une implémentation python pour cela (et j'aimerais en avoir une, même si elle ne prend pas en charge les informations de lignes), Deuxièmement, je pense que les lignes elles-mêmes ajoutent des informations au problème qui devraient être utilisées
Pourquoi les lignes ajouteraient-elles des informations? En fin de compte, la coque concave concerne les points (d'extrémité) et à partir de ceux-ci, vous pouvez quand même générer les lignes (et vice versa). Comme vous ne nous avez montré aucun code pour commencer, il est difficile de vous aider avec votre implémentation spécifique. Pourriez-vous fournir un exemple?
Votre question, telle que formulée, prête à confusion. Vous devez préciser si les points d'intersection des lignes devraient contribuer ou non à la coque. Sinon, les lignes sont des informations non pertinentes et distrayantes.
Il existe de nombreux algorithmes de coque convexe à sommet uniquement
O(n log n), mais le nombre de lignes joignantnpoints peut être aussi grand queO(n^2)(maximum théoriquen(n-1)/2) - l'acte même de les créer lui-même peut être plus coûteux (asymptotiquement parlant) que de calculer directement la coque convexe à partir des points.