Une méthode ou un algorithme pour trouver le plus petit ensemble convexe (l’enveloppe convexe) contenant un ensemble fini de points ; l’enveloppe convexe est le polygone ou polytope convexe minimal qui enferme les points et constitue un primitif géométrique fondamental.

Principe

L’enveloppe convexe se caractérise comme l’intersection de tous les ensembles convexes contenant les points ou, de façon équivalente, comme l’ensemble des combinaisons convexes des points ; les méthodes de calcul exploitent les points extrêmes, le tri angulaire, l’insertion incrémentale ou la division et conquête pour produire les sommets de l’enveloppe.

Démonstration

Pour des points planaires, on peut calculer l’enveloppe en trouvant d’abord un sommet extrême, en triant les autres points par angle polaire autour de celui-ci, puis en effectuant un balayage à l’aide d’une pile qui élimine les points intérieurs pour produire la séquence des sommets de l’enveloppe convexe.

Mauvaise application

Employer des vérifications géométriques naïves en O(n^2) ou ne pas gérer les colinéarités et la précision numérique peut produire des enveloppes incorrectes (points extrêmes manquants ou points intérieurs inclus) ou des ordres de sommets instables pour un traitement ultérieur.

Conséquence

Une construction correcte de l’enveloppe convexe donne un recouvrement convexe minimal utile pour la détection de collisions, l’approximation de forme, le calcul du diamètre et de la largeur, et comme étape de prétraitement dans de nombreux algorithmes géométriques, réduisant souvent la complexité du problème.

Inversion

La notion duale est le noyau convexe ou l’intersection des demi‑espaces supports d’un polygone ; inverser l’attention du sur-ensemble convexe minimal aux sous‑ensembles convexes maximaux ou noyaux éclaire des problèmes complémentaires de faisabilité et de visibilité.

Limite

S’applique aux ensembles finis de points dans l’espace euclidien et se généralise en dimensions supérieures en polytopes convexes ; exclut les ensembles infinis sans hypothèses de compacité et demande de la prudence en géométries non euclidiennes ou face à des configurations dégénérées colinéaires/coplanaires.

Tension sémantique

L’enveloppe convexe est parfois confondue avec des boîtes englobantes ou d’autres enveloppes ; contrairement aux boîtes alignées aux axes ou aux rectangles d’aire minimale, l’enveloppe convexe est le plus petit ensemble convexe et peut comporter un nombre arbitraire de sommets selon la distribution des points.

Synthèse

La construction de l’enveloppe convexe calcule le sur‑ensemble convexe minimal d’un ensemble de points en identifiant les points extrêmes et en les ordonnant pour former un polytope convexe ; elle réduit de nombreux problèmes géométriques à l’opération sur une structure combinatoire plus petite qui capture la géométrie extérieure de l’ensemble.