backend / algorithmes-structures-donnees
Géométrie algorithmique : enveloppe convexe
Explication
Ce que vous allez apprendre
- Définir l'enveloppe convexe d'un nuage de points comme le plus petit polygone convexe qui les contient tous
- Calculer un sens de virage (gauche, droite, aligné) entre trois points via le produit vectoriel
- Construire l'enveloppe convexe avec l'algorithme d'Andrew (tri, puis chaîne basse et chaîne haute)
- Expliquer pourquoi cet algorithme élimine automatiquement les points intérieurs sans les tester individuellement
- Justifier la complexité globale O(n log n), dominée par le tri initial des points
Dans quel contexte ?
Un jeu vidéo doit calculer la zone de collision englobant un ensemble d'obstacles représentés par des dizaines de points, pour simplifier les calculs de physique. L'enveloppe convexe donne exactement le contour minimal de cette zone : au lieu de tester la collision contre des dizaines de points, le moteur physique ne teste plus que contre les quelques sommets qui forment réellement le pourtour de la zone.
D'abord, une image simple du problème
Imagine planter des clous aux positions d'un ensemble de points, puis tendre un élastique autour de tous les clous : la forme que prend l'élastique, c'est l'enveloppe convexe.
Ce que cette forme représente précisément
C'est le plus petit polygone "convexe" (sans aucun creux) qui contient tous les points du nuage.
Étape 1 : l'outil de base, déterminer un sens de virage
Toute la géométrie algorithmique en 2D repose sur une question simple : étant donné trois points consécutifs, tourne-t-on à gauche, à droite, ou sont-ils alignés ?
| Résultat du produit vectoriel | Interprétation géométrique |
|---|---|
| Positif | Virage à gauche (sens antihoraire) |
| Négatif | Virage à droite (sens horaire) |
| Nul | Les trois points sont alignés |
Prérequis
Cette leçon suppose à l'aise avec le tri (leçon 7) : l'algorithme d'Andrew commence toujours par trier les points, et sa complexité globale O(n log n) est directement celle de ce tri initial.
Comment répondre à cette question rapidement
Cette information se calcule directement avec le produit vectoriel des deux segments formés, un calcul purement arithmétique, sans jamais avoir besoin de fonctions trigonométriques coûteuses.
Astuce
Le produit vectoriel entre deux segments évite tout calcul d'angle ou de fonction trigonométrique coûteuse : un simple test de signe (positif, négatif, nul) suffit à déterminer le sens de virage. C'est cette opération arithmétique simple qui rend la géométrie algorithmique aussi rapide.
Étape 2 : construire l'enveloppe avec l'algorithme d'Andrew
On trie d'abord tous les points de gauche à droite, puis on construit deux "chaînes" : une chaîne basse en balayant de gauche à droite, une chaîne haute en balayant de droite à gauche.
Le mécanisme qui élimine les points inutiles
À chaque ajout d'un nouveau point, on vérifie si les trois derniers points forment un virage convexe ; sinon, on retire le point précédent, car il se trouve nécessairement à l'intérieur de l'enveloppe finale.
Pourquoi ce retrait garantit un résultat correct
Ce mécanisme de retrait répété garantit qu'aucun point non-convexe ne subsiste à la fin de la construction.
Pourquoi cette structure sert au-delà de la géométrie pure
De nombreux problèmes se réduisent à ne considérer que les points de l'enveloppe plutôt que tout le nuage : le diamètre d'un ensemble de points se trouve toujours entre deux points de l'enveloppe, jamais à l'intérieur.
Vers la suite
Après avoir accepté de calculer une forme exacte, la prochaine leçon présente l'inverse : une structure qui accepte délibérément de se tromper parfois, en échange d'un gain énorme en mémoire, le filtre de Bloom.
Commandes & code
Géométrie algorithmique : enveloppe convexe
L'enveloppe convexe est le plus petit polygone convexe contenant tous les points d'un nuage.
def produit_vectoriel(o: tuple, a: tuple, b: tuple) -> int:
# > 0 : virage à gauche (sens antihoraire), < 0 : virage à droite, 0 : points alignés
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
def enveloppe_convexe(points: list[tuple[int, int]]) -> list[tuple[int, int]]:
# Algorithme d'Andrew (monotone chain), variante simple et robuste du Graham scan -- O(n log n)
points = sorted(set(points))
if len(points) <= 2:
return points
# Construit la chaîne basse (de gauche à droite)
bas = []
for p in points:
while len(bas) >= 2 and produit_vectoriel(bas[-2], bas[-1], p) <= 0:
bas.pop() # le point précédent créait un virage à droite ou un alignement -> pas convexe
bas.append(p)
# Construit la chaîne haute (de droite à gauche)
haut = []
for p in reversed(points):
while len(haut) >= 2 and produit_vectoriel(haut[-2], haut[-1], p) <= 0:
haut.pop()
haut.append(p)
# Concatène les deux chaînes en retirant les points de jonction dupliqués
return bas[:-1] + haut[:-1]
points = [(0, 0), (1, 1), (2, 2), (2, 0), (0, 2), (1, 0), (0, 1), (3, 3), (-1, -1)]
resultat = enveloppe_convexe(points)
assert set(resultat) == {(-1, -1), (2, 0), (3, 3), (0, 2)} # les points intérieurs sont exclus
# Application : diamètre d'un nuage de points (plus grande distance entre deux points)
# -> il suffit de chercher parmi les points de l'ENVELOPPE, jamais à l'intérieur du nuage
def diametre_nuage_points(points: list[tuple[int, int]]) -> float:
hull = enveloppe_convexe(points)
if len(hull) < 2:
return 0.0
max_dist = 0.0
for i in range(len(hull)):
for j in range(i + 1, len(hull)):
dist = ((hull[i][0] - hull[j][0]) ** 2 + (hull[i][1] - hull[j][1]) ** 2) ** 0.5
max_dist = max(max_dist, dist)
return max_dist
# Complexité : O(n log n) pour l'enveloppe, puis O(h^2) sur ses points (h << n en général)
assert diametre_nuage_points([(0, 0), (4, 0), (2, 3)]) == 4.0Résumé
- Le produit vectoriel
(a-o) x (b-o)détermine si trois points tournent à gauche, à droite, ou sont alignés : c'est le test élémentaire de toute la géométrie algorithmique en 2D. - L'algorithme d'Andrew trie les points puis construit deux chaînes (basse et haute) en éliminant les virages non convexes -- O(n log n), dominé par le tri.
- De nombreux problèmes géométriques (diamètre d'un nuage, plus petit rectangle englobant orienté) se réduisent à ne considérer QUE les points de l'enveloppe convexe.
Exercices pratiques
Mission : simplifier la zone de collision d'un jeu vidéo qui rame
Objectif : Calculer une enveloppe convexe à la main via le produit vectoriel et l'appliquer à un problème dérivé (diamètre).
Contexte
Un moteur physique de jeu vidéo teste actuellement les collisions contre les 9 points d'un obstacle : (0,0), (1,1), (2,2), (2,0), (0,2), (1,0), (0,1), (3,3), (-1,-1). Le studio veut réduire ce test au strict nécessaire, sans jamais rater une collision réelle, en ne gardant que les points qui forment le contour extérieur de l'obstacle.