Pourquoi Graham et QuickHull donnent-ils parfois des listes de sommets différentes ?

Tous les points **extrêmes** sont sur le bord de l’enveloppe convexe, mais lorsque beaucoup de points sont sur **une même droite**, les algorithmes ne retiennent pas les mêmes **sommets** du polygone. Graham avec le test **≤ 0** ne garde en général que les **extrémités** du segment colinéaire ; QuickHull, sans filtrage supplémentaire, peut inclure des points **intermédiaires** sur l’arête. L’**enveloppe convexe** comme ensemble du plan coïncide ; seule change la représentation polygonale.

Que représente la ligne brisée bleu clair en mode Graham ?

C’est la **pile** actuelle des candidats sommets de l’enveloppe au **pas** choisi — l’enveloppe partielle après traitement du préfixe correspondant de la liste triée. L’**anneau rose** est le point que l’on examine maintenant pour l’inclusion.

Quelle est la robustesse numérique ?

On utilise des **float64** ordinaires et des produits vectoriels. Si les points presque coïncident ou sont presque alignés, l’orientation peut vaciller ; à l’ajout des points, un petit **écart** aux voisins évite les doublons accidentels.

Comment QuickHull partage-t-il les points ?

Après le choix de **L** et **R**, les points **strictement à gauche** de la droite orientée **LR** entrent dans la chaîne **haute**, ceux **strictement à droite** dans la **basse**. À chaque pas, parmi les points restants, on prend le point **C** **le plus éloigné** de l’arête courante **AB** (module de l’aire orientée), puis la récursion continue sur les ensembles à l’extérieur des triangles **ABC**, jusqu’à ce qu’il ne reste plus de point du côté externe de l’arête.

Enveloppe convexe (Graham et QuickHull)

Points du plan : parcours de Graham avec animation pas à pas, ou QuickHull ; comparaison des ensembles de sommets.

À propos du modèle

L’enveloppe convexe d’un ensemble fini de points du plan est le plus petit polygone convexe qui les contient tous ; de façon équivalente, l’intersection de tous les convexes qui le contiennent. Deux constructions classiques en O(n log n) sont implémentées. Le parcours de Graham choisit un point d’appui (le plus bas, et à y égal le plus à gauche), trie les autres par angle polaire autour de cet appui (à angle égal, par la distance) et parcourt la liste en maintenant une pile : avant d’ajouter le point suivant, on dépile tant que l’orientation du dernier triplet n’est pas un virage à gauche strict dans le sens antihoraire (produit vectoriel : on retire les cas cross ≤ 0, c’est-à-dire un virage à droite ou un triplet aligné). Des instantanés enregistrent la pile et le point « à l’étude » pour le déroulement pas à pas. QuickHull prend les extrêmes en x, L et R, partage l’ensemble en points au-dessus et au-dessous de la droite orientée LR, et ajoute récursivement, sur chaque arête, le point de plus grande aire orientée du triangle (via |cross|) ; les points du segment sont rejetés comme intérieurs à l’arête. En cas de colinéarités, les implémentations peuvent retenir des sous-ensembles de sommets différents sur un même côté ; l’interface indique si les ensembles d’indices des sommets de Graham et de QuickHull coïncident. Un clic dans le vide ajoute un point (avec une garde contre les quasi-coïncidences), un glissement près d’un point le déplace ; le nombre de points et la graine fixent un nuage aléatoire.

Public : Mathématiques discrètes et géométrie algorithmique : construction incrémentale et « diviser pour régner ».

Notions clés

enveloppe convexe
parcours de Graham
QuickHull
tri polaire
pile monotone
orientation d’un triplet
diviser pour régner
colinéarité

Comment ça marche

L’enveloppe convexe est le plus petit polygone convexe qui contient tous les points. Graham : point d’appui, tri polaire, pile et test de virage via cross ; QuickHull : extrêmes en x, récursion sur le point le plus éloigné de l’arête (aire ∝ |cross|). Les colinéarités peuvent donner des listes de sommets différentes pour la même enveloppe.

Questions fréquentes

Pourquoi Graham et QuickHull donnent-ils parfois des listes de sommets différentes ?: Tous les points extrêmes sont sur le bord de l’enveloppe convexe, mais lorsque beaucoup de points sont sur une même droite, les algorithmes ne retiennent pas les mêmes sommets du polygone. Graham avec le test ≤ 0 ne garde en général que les extrémités du segment colinéaire ; QuickHull, sans filtrage supplémentaire, peut inclure des points intermédiaires sur l’arête. L’enveloppe convexe comme ensemble du plan coïncide ; seule change la représentation polygonale.
Que représente la ligne brisée bleu clair en mode Graham ?: C’est la pile actuelle des candidats sommets de l’enveloppe au pas choisi — l’enveloppe partielle après traitement du préfixe correspondant de la liste triée. L’anneau rose est le point que l’on examine maintenant pour l’inclusion.
Quelle est la robustesse numérique ?: On utilise des float64 ordinaires et des produits vectoriels. Si les points presque coïncident ou sont presque alignés, l’orientation peut vaciller ; à l’ajout des points, un petit écart aux voisins évite les doublons accidentels.
Comment QuickHull partage-t-il les points ?: Après le choix de L et R, les points strictement à gauche de la droite orientée LR entrent dans la chaîne haute, ceux strictement à droite dans la basse. À chaque pas, parmi les points restants, on prend le point C le plus éloigné de l’arête courante AB (module de l’aire orientée), puis la récursion continue sur les ensembles à l’extérieur des triangles ABC, jusqu’à ce qu’il ne reste plus de point du côté externe de l’arête.

Poursuivez avec des thèmes proches de cette catégorie — ou les 85 de «Visualisation mathématique».

Toute la catégorie →

NouveauCollège–lycée

Courbes de Bézier et de Casteljau

Lancer la simulation

Les points de contrôle fixent la courbe de Bézier ; l’algorithme de de Casteljau construit B(t) par interpolation linéaire emboîtée.

NouveauCollège–lycée

Triangulation de Delaunay et diagramme de Voronoï

Lancer la simulation

Triangulation de Bowyer–Watson et diagramme de Voronoï dual : un clic ajoute des sites, un glissement les déplace.

NouveauCollège–lycée

Régression linéaire : MCO, ridge, lasso et R²

Lancer la simulation

Points du plan et modèle y = β₀ + β₁x : moindres carrés ordinaires (MCO), ridge (pénalité L₂ sur la pente) ou lasso (pénalité L₁). Le décalage Δy du point de plus grand |x| est une valeur aberrante à fort levier ; on compare SSE et R².

NouveauCollège–lycée

k-moyennes (algorithme de Lloyd)

Lancer la simulation

Points du plan, nombre de classes k et centroïdes de départ. Un pas de Lloyd : affectation au centre le plus proche et déplacement du centroïde au barycentre. Démonstration : mélange de gaussiennes ; somme des carrés intra-classes.

NouveauCollège–lycée

Descente de gradient (2D)

Lancer la simulation

Lignes de niveau de f(x, y) et trajectoire (x, y) ← (x, y) − η∇f ; cuvette ou puits elliptique.

NouveauCollège–lycée

Réseau à deux couches et rétropropagation

Lancer la simulation

Deux caractéristiques et une étiquette binaire : couche cachée à tanh et sortie logistique. Gradient complet sur l’entropie croisée binaire moyenne ; carte de chaleur des probabilités et frontière de niveau 0,5 (XOR ou spirales).

Enveloppe convexe (Graham et QuickHull)

À propos du modèle

Comment ça marche

Questions fréquentes

Simulations voisines

Courbes de Bézier et de Casteljau

Triangulation de Delaunay et diagramme de Voronoï

Régression linéaire : MCO, ridge, lasso et R²

k-moyennes (algorithme de Lloyd)

Descente de gradient (2D)

Réseau à deux couches et rétropropagation

Enveloppe convexe (Graham et QuickHull)

À propos du modèle

Comment ça marche

Questions fréquentes