Étant donné un ensemble de points, je souhaite créer un polygone concave non-croisé en utilisant ces points. Une coque convexe annulerait la partie concave, alors que l'arrangement par des coordonnées x/y ou des angles du centre créerait des artefacts épineux. Y a-t-il un moyen simple de le faire?Créer un polygone concave passant par tous les points donnés
Un exemple du genre de polygone que je veux créer:
Si vous avez seulement les sommets du périmètre et peut garantir que la distance entre les sommets du périmètre sera inférieure à la distance entre les bords de le périmètre alors vous pourriez utiliser un arbre couvrant minimum.
Le sommet exemple montre où une MST fonctionne (avec les premiers et derniers sommets dans la polyligne résultant rejoint)
L'exemple de fond est ce qui se passe si les bords du périmètre trop près.
Merci. J'ai en fait un grand nombre d'ensembles de données, et je ne peux pas garantir que pour chaque ensemble de données, la distance entre les sommets du périmètre sera inférieure à la distance entre les bords du périmètre. Y a-t-il une approche qui ne suppose pas cela? – phalanx
La réponse à cette question aborde certains des problèmes avec une solution plus générale: http://stackoverflow.com/questions/20141812/ordering-concave-polygon-vertices-in-counterclockwise – shouston
... quel ensemble de points? –
un ensemble de points qui définit les bordures du polygone concave. – phalanx
voir SO [Créer un polygone sans intersection passant par tous les points donnés] (http://stackoverflow.com/questions/14263284/create-non-intersecting-polygon-passing-through-all-given-points) – stefan