Polygone entourant un ensemble de points

Question

J'ai un ensemble S de points (2D: défini par x et y) et je veux trouver P, le plus petit polygone (signifiant: avec le plus petit nombre de points) entourant 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 étonnant ...)

Merci de votre aide

Answer 1

Il existe de nombreux algorithmes pour résoudre ce problème. Il s'appelle " cadre de sélection minimal " ;. Vous trouverez également des solutions en recherchant les coque convexe , en particulier ici .

Une solution consiste à rechercher le point le plus à gauche, puis de répéter pour rechercher un point où tous les autres points se trouvent à droite de la ligne p (n-1) p (n).

Answer 2

Voici une solution simple ...

Commencez avec trois points quelconques pour former un triangle. Ajoutez chaque point supplémentaire au polygone avec l'opération suivante:

Divisez les arêtes 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, le la ligne de chaque bord a le point du même côté que le polygone.

(Remarque: tant que votre forme reste convexe, ce qui doit être le cas, ces deux chemins seront continus et formeront la forme entière.)

Si le chemin de séparation n'a pas d'arête, le point se trouve à 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! :)

Answer 3

Vous voulez probablement dire que vous voulez la plus petite zone, à savoir la coque convexe.

Si vous souhaitez réellement disposer du moins de points , vous pouvez créer un triangle avec des positions de sommet très grandes afin que tous vos points soient enfermés.

Answer 4

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)