Polygone entourant un ensemble de points
J'ai un ensemble S de points (2D: défini par x et y) et je veux trouver P, le plus petit (ce qui signifie : avec le plus petit nombre de points) polygone englobant tous les points de L'ensemble, P étant un sous-ensemble ordonné de S.
Existe-t-il des algorithmes connus pour calculer cela? (mon manque de culture dans ce domaine est étonnante...)
Merci pour votre aide
4 réponses
Il existe de nombreux algorithmes pour ce problème. Il est appelé "boîte de délimitation minimale ". Vous trouverez aussi des solutions à la recherche de " coque convexe ", surtout ici .
Est Une façon de trouver le point le plus à gauche, puis répétez pour rechercher un point où tous les autres points sont à droite de la ligne p(n-1)p(n).
Voici une solution simple...
Commencez par trois points pour former un triangle. Ajoutez chaque point supplémentaire au polygone avec l'opération suivante:
Divisez les bords en deux chemins continus, où dans un chemin la ligne de chaque bord sépare le point à ajouter du reste du polygone (appelons cela le "chemin de séparation") et dans l'autre chemin, la ligne de chaque bord a le point du même côté que le polygone.
(Note: aussi longtemps que votre forme reste convexe, ce qu'il faut, ces deux chemins seront continus et formeront toute la forme)
Si le chemin de séparation n'a pas d'arêtes, le point est à l'intérieur du polygone et doit être ignoré, sinon, supprimez le chemin de séparation du polygone. Remplacez-le par deux segments, en connectant chaque extrémité du chemin de séparation au nouveau point.
Ta-da! :)
Vous voulez probablement dire que vous voulez la plus petite zone, qui est la coque convexe.
Si vous voulez vraiment le moins de points , Vous pouvez simplement faire un triangle avec des positions de Sommets super grandes afin que tous vos points soient fermés.
Voici une bonne ressource sur les algorithmes de coque convexe: La coque convexe d'un ensemble de points 2D ou D'un polygone (par Dan Sunday)