Enveloppe convexe de points

L'enveloppe convexe est le plus petit polygone convexe qui contient tous les points d'un ensemble fini — le contour d'un élastique tendu autour de clous sur une planche. Géomètres, analystes SIG, développeurs de jeux et étudiants en géométrie algorithmique ont besoin de ce contour à partir d'échantillons non ordonnés : traces GPS, emprises de bâtiments, sommets de sprites ou nuages de classe de paires (x, y). Cet outil d'enveloppe convexe de points exécute le balayage de chaîne monotone d'Andrew : il trie les points par coordonnée horizontale puis verticale, construit les chaînes inférieure et supérieure en passes linéaires et renvoie les sommets extrêmes dans le sens antihoraire. Les points intérieurs et les échantillons colinéaires au milieu d'une arête sont éliminés automatiquement. Vous pouvez envoyer des paires planaires x/y ou des points géographiques lat/lon ; le mode geo calcule encore une enveloppe planaire dans le plan longitude–latitude, approximation locale habituelle pour des enveloppes à l'échelle d'une ville ou d'un site.

Qu'est-ce qu'une enveloppe convexe et comment fonctionne la chaîne monotone

Étant donné un ensemble fini de points dans le plan, l'enveloppe convexe est l'unique plus petit ensemble convexe qui les contient tous. Sa frontière est un polygone convexe dont les sommets sont un sous-ensemble de l'entrée : tout point extrême qui « dépasse » apparaît sur l'enveloppe, et tout point exprimable comme combinaison convexe d'autres points se trouve strictement à l'intérieur ou sur une arête. La chaîne monotone d'Andrew (aussi appelée balayage de chaîne monotone) calcule cette frontière en temps O(n log n) dominé par le tri.

Après tri par x croissant (et par y en cas d'égalité sur x), l'algorithme parcourt de gauche à droite pour l'enveloppe inférieure en maintenant toujours un virage strict à gauche sur les trois derniers sommets de la pile ; puis il parcourt de droite à gauche pour l'enveloppe supérieure avec le même test de virage.

Concaténer les deux chaînes sans dupliquer les extrémités partagées les plus à gauche et les plus à droite produit l'enveloppe complète dans le sens antihoraire, en partant de l'extrême le plus à gauche (puis le plus bas). Un test de virage non strict (produit vectoriel inférieur ou égal à zéro) supprime les points colinéaires intermédiaires afin que chaque arête soit maximale.

Les ensembles dégénérés sont traités proprement : un seul point unique renvoie une enveloppe à un sommet ; deux points distincts, un segment à deux sommets ; trois points colinéaires ou plus, seulement les deux extrêmes. Ce comportement correspond aux définitions de cours de l'enveloppe des points extrêmes et évite les « encoches » d'aire nulle dans les outils de polygone en aval causées par des échantillons au milieu d'arête.

Où un contour convexe se révèle utile

Les équipes cartographie et logistique calculent l'enveloppe convexe d'arrêts de livraison, de pings d'actifs ou de jalons de levé pour tracer un contour extérieur simple sans numérisation manuelle. Les pipelines jeux et CAD réduisent les proxies de collision ou les boîtes de sélection d'interface à l'enveloppe des sommets de maillage ou de sprite afin que les tests de chevauchement restent peu coûteux.

Les carnets de science des données utilisent l'enveloppe comme contour extérieur robuste pour nuages de points et revue d'anomalies lorsqu'une bounding box est trop lâche et qu'une forme alpha concave est trop lourde. Les plateformes de cours et de concours ont besoin d'un oracle déterministe pour les exercices « listez les points extrêmes dans l'ordre » ; une capacité parse pure renvoie des coordonnées stables à précision fixe pour que les correcteurs ne cassent pas sur le bruit flottant. Une validation échouée ne consomme pas de solde.

Gardez les nuages sous le plafond de dix mille points, figez les sommets d'enveloppe dans les tests, et vous obtenez des enveloppes reproductibles pour ETL SIG, workers de bord et devoirs sans monter une bibliothèque de géométrie complète en propre.