Cerner un nuage de points
L'enveloppe convexe d'un nuage de points, c'est le plus petit polygone convexe qui les contient tous — l'élastique que l'on tendrait autour d'un ensemble de clous plantés dans une planche. C'est une brique de base en géométrie algorithmique : détection de collisions, reconnaissance de formes, calcul d'aire d'emprise. Je la construis ici from scratch en Canvas 2D, en animant chaque étape du raisonnement plutôt qu'en affichant seulement le résultat.
Le parcours de Graham, étape par étape
La démo suit le parcours de Graham. Première étape : choisir un point de départ qui appartient forcément à l'enveloppe — je prends le point le plus bas, celui qui a la plus grande ordonnée à l'écran (en départageant par l'abscisse la plus petite en cas d'égalité). Ce pivot sert d'ancre à toute la construction.
Trier par angle polaire
Deuxième étape : trier tous les autres points par angle polaire autour du pivot, du plus rasant au plus relevé. Une fois ce tri fait, on tient une liste dans laquelle on peut avancer une seule fois, dans l'ordre, sans jamais revenir en arrière. C'est ce tri qui donne à l'algorithme sa complexité en O(n log n) : le balayage qui suit est linéaire, c'est donc le tri qui domine le coût total.
Une pile et un test d'orientation
Troisième étape : parcourir la liste triée en maintenant une pile des sommets retenus. À chaque nouveau point, je regarde les deux derniers sommets empilés et le candidat. S'ils forment un tournant à gauche, le candidat prolonge proprement le contour : je l'empile. S'ils forment un tournant à droite, le dernier sommet empilé creusait une concavité : je le dépile, et je recommence le test. Ce virage se décide par le signe du produit vectoriel des deux segments — une soustraction et deux multiplications, sans trigonométrie ni division, donc rapide et sans erreur d'arrondi grossière. Chaque point est empilé puis dépilé au plus une fois : le balayage reste bien linéaire.
Manipulez la construction
Cliquez pour ajouter un point et voir l'enveloppe se recalculer, appuyez sur R pour repartir d'un nuage aléatoire, et sur Espace pour relancer ou mettre l'animation en pause. On observe alors le comportement clé de l'algorithme : un point ajouté à l'intérieur ne change rien au contour, tandis qu'un point ajouté à l'extérieur peut « avaler » plusieurs anciens sommets d'un coup lorsqu'ils sont dépilés en cascade.
Pourquoi je montre ça
Derrière ce petit polygone ambre, il y a la démarche que j'applique à vos projets : décomposer un problème en étapes justifiables, choisir l'algorithme dont le coût est maîtrisé et démontrable — ici le tri qui borne le tout à O(n log n) —, et le rendre lisible. Un code que l'on peut expliquer étape par étape est un code que votre équipe pourra reprendre, tester et faire évoluer sans dépendre de moi. C'est exactement ce que je vous livre : des fondations claires, pas des boîtes noires.
