🟦 Enveloppe Convexe

En physique de jeu 2D, l'enveloppe convexe d'un polygone est son emballage convexe minimal. Deux polygones convexes peuvent être testés pour l'intersection à l'aide du théorème de l'axe séparateur (SAT) : s'il existe une ligne séparant les deux enveloppes, elles ne se chevauchent pas — et seulement O(h₁ + h₂) axes séparateurs candidats doivent être testés (un par arête). L'algorithme GJK (Gilbert-Johnson-Keerthi) étend cela à la 3D et gère les objets courbes en calculant la différence de Minkowski, atteignant O(1) itérations en pratique pour des formes simples. SAT et GJK sont tous deux des outils fondamentaux dans Unity, Bullet et d'autres moteurs physiques.

Les points situés sur une arête de l'enveloppe mais qui ne sont pas des sommets (ils sont colinéaires entre deux sommets de l'enveloppe) peuvent être inclus ou exclus selon la variante d'algorithme. Le balayage de Graham standard exclut les points intérieurs colinéaires (il les retire pendant l'étape de déduplication du tri), donnant l'ensemble minimal de sommets. Certaines applications (par exemple le calcul d'aire de polygone) préfèrent inclure tous les points de la frontière. Ce choix affecte h (taille de l'enveloppe), le temps d'exécution, et le comportement du test d'orientation par produit vectoriel (un produit vectoriel nul doit être géré avec soin pour éviter les boucles infinies dans la marche de Jarvis).

L'algorithme de Chan (Timothy Chan, 1996) atteint un temps de O(n log h), où h est le nombre de sommets de l'enveloppe — c'est optimal car produire h sommets prend un temps Ω(h) et trier n points prend Ω(n log n). L'approche de Chan devine h par phases de doublement (essayer h = 2, 4, 8, …), exécute une mini-marche de Jarvis qui s'arrête après h étapes en utilisant un balayage de Graham précalculé sur n/h groupes de points comme oracles internes. Quand la supposition est égale au véritable h, l'algorithme se termine avec une enveloppe correcte. Chaque phase coûte O(n log h) ; le doublement n'ajoute qu'un facteur constant, donnant un total de O(n log h).

En programmation linéaire 2D, la région réalisable définie par m contraintes d'inégalité est un polygone convexe — une enveloppe convexe des points d'intersection des contraintes. La solution optimale d'un programme linéaire se trouve toujours à un sommet du polytope réalisable. La méthode du simplexe parcourt les sommets de ce polytope ; les méthodes de points intérieurs parcourent l'intérieur. En dimensions supérieures (d variables, m contraintes), calculer l'énumération des sommets du polytope réalisable équivaut à calculer une enveloppe convexe en d dimensions — un problème résolu par les algorithmes de double description et beneath-beyond.

En 3D, l'enveloppe convexe de n points est un polyèdre convexe avec au plus O(n) sommets, arêtes et faces (par la formule d'Euler : V − E + F = 2, et pour les polyèdres convexes F ≤ 2n − 4). Les algorithmes incluent le balayage de Graham 3D (insertion incrémentale), diviser-pour-régner (O(n log n)), et la variante d'emballage cadeau (marche de Jarvis en 3D). L'algorithme QuickHull3D de Barber, Dobkin et Huhdanpaa (1996, bibliothèque qhull) est la norme pratique — utilisé dans ConvexHull de SciPy, MATLAB, et les outils physiques de moteurs de jeu.

Les points en double (coordonnées identiques) doivent être gérés explicitement ; la plupart des implémentations dédupliquent l'entrée avant d'exécuter l'algorithme d'enveloppe. Dans le balayage de Graham, des points en double produiraient des produits vectoriels nuls causant une ambiguïté dans le tri angulaire. Dans la marche de Jarvis, sélectionner un doublon comme sommet suivant de l'enveloppe pourrait causer une boucle infinie. Une implémentation robuste supprime soit les doublons lors d'un prétraitement en O(n log n), soit utilise une arithmétique exacte avec perturbation (perturbation symbolique / SOS — simulation de simplicité) pour gérer de façon cohérente toutes les configurations dégénérées.

Il existe une dualité classique : le diagramme de Voronoï 2D de n points est équivalent à la projection de l'enveloppe convexe 3D des mêmes points relevés sur le paraboloïde z = x² + y². Plus précisément, on relève chaque point (xᵢ, yᵢ) vers (xᵢ, yᵢ, xᵢ² + yᵢ²), on calcule l'enveloppe convexe 3D, puis on projette les faces inférieures de l'enveloppe de retour en 2D — le résultat est la triangulation de Delaunay, et son graphe dual est le diagramme de Voronoï. Cela signifie que tout algorithme d'enveloppe convexe 3D en O(n log n) donne immédiatement un algorithme de Voronoï en O(n log n), correspondant à l'algorithme classique de balayage de Fortune.

Dans les machines à vecteurs de support (SVM), le classificateur à marge maximale entre deux classes de points correspond à trouver les points les plus proches sur les enveloppes convexes des deux classes — le dual de la « boule englobante minimale ». Les vecteurs de support du SVM sont exactement les points de l'enveloppe les plus proches de l'hyperplan séparateur. Les enveloppes convexes apparaissent aussi en profondeur de données (profondeur de Tukey, l'algorithme « d'épluchage d'oignon »), en détection d'anomalies (les points de données hors de l'enveloppe sont des valeurs aberrantes), et en optimisation multi-objectifs où la frontière de Pareto est une portion de l'enveloppe convexe des vecteurs objectifs réalisables.