Warum liefern Graham und QuickHull manchmal verschiedene Knotenlisten?

Alle **extremen** Punkte liegen auf dem Rand der konvexen Hülle, aber bei vielen Punkten auf **einer Geraden** wählen die Verfahren unterschiedlich, welche davon **Knoten** des Polygons bleiben. Graham mit dem Test **≤ 0** behält in der Regel nur die **Enden** der kollinearen Strecke; QuickHull ohne zusätzliche Filterung kann **Zwischenpunkte** auf der Kante mitnehmen. Die **konvexe Hülle** als Menge in der Ebene fällt zusammen; verschieden ist nur die polygonale Darstellung.

Was bedeutet der hellblaue Streckenzug im Graham-Modus?

Das ist der aktuelle **Stapel** der Kandidaten für Hüllenknoten am gewählten **Schritt** — die Teilhülle nach dem entsprechenden Anfangsstück der sortierten Liste. Der **rosafarbene Ring** ist der Punkt, der gerade auf Aufnahme geprüft wird.

Wie numerisch robust ist das?

Es werden gewöhnliche **float64**-Zahlen und Kreuzprodukte verwendet. Liegen Punkte fast aufeinander oder fast auf einer Geraden, kann die Orientierung zittern; beim Hinzufügen gilt ein kleiner **Abstand** zu Nachbarn, damit keine zufälligen Doppelpunkte entstehen.

Wie teilt QuickHull die Punkte?

Nach der Wahl von **L** und **R** gehen Punkte **streng links** der orientierten Geraden **LR** in die **obere** Kette, **streng rechts** in die **untere**. In jedem Schritt wird unter den übrigen der Punkt **C** gewählt, der von der aktuellen Kante **AB** **am weitesten** entfernt ist (Betrag der orientierten Fläche); die Rekursion läuft dann auf den Mengen außerhalb der Dreiecke **ABC**, bis außen an der Kante keine Punkte mehr liegen.

Konvexe Hülle (Graham und QuickHull)

Punkte in der Ebene: Graham-Scan mit Schrittanimation oder QuickHull; Vergleich der Knotenmengen.

Zum Modell

Die konvexe Hülle einer endlichen Punktmenge in der Ebene ist das kleinste konvexe Polygon, das alle Punkte enthält; gleichwertig ist sie der Schnitt aller konvexen Obermengen. Zwei klassische Konstruktionen der Ordnung O(n log n) sind umgesetzt. Der Graham-Scan wählt einen Stützpunkt (den untersten, bei gleichem y den linkesten), sortiert die übrigen nach dem Polarwinkel um diesen Stützpunkt (bei gleichem Winkel nach der Entfernung) und durchläuft die Liste mit einem Stapel: bevor der nächste Punkt aufgenommen wird, werden Knoten aus dem Stapel genommen, bis die Orientierung des letzten Tripels beim Gegenuhrzeigersinn ein streng linker Knick ist (Kreuzprodukt: Fälle cross ≤ 0 werden entfernt, also Rechtsknick oder gestrecktes Tripel). Einzelbilder halten den Stapel und den gerade betrachteten Punkt fest, damit der Ablauf Schritt für Schritt sichtbar bleibt. QuickHull nimmt die in x äußersten Punkte L und R, teilt die Menge in Punkte oberhalb und unterhalb der orientierten Geraden LR und hängt an jeder Kante rekursiv den Punkt mit dem größten Betrag der orientierten Dreiecksfläche an (über |cross|); Punkte auf der Strecke gelten als innenliegend zur Kante und fallen weg. Bei Kollinearität können verschiedene Umsetzungen unterschiedliche Teilmengen der Knoten auf einer Seite behalten; die Anzeige zeigt, ob die Indexmengen der Knoten bei Graham und QuickHull übereinstimmen. Ein Klick ins Leere fügt einen Punkt hinzu (mit Schutz vor fast zusammenfallenden Punkten), Ziehen in der Nähe eines Punktes verschiebt ihn; Punktzahl und Startwert erzeugen eine Zufallswolke.

Für wen: Diskrete Mathematik und algorithmische Geometrie: inkrementeller Aufbau und Teile-und-Herrsche.

Wichtige Begriffe

konvexe hülle
graham-scan
quickhull
polarwinkelsortierung
monotoner stapel
orientierung eines tripels
teile-und-herrsche
kollinearität

So funktioniert es

Die konvexe Hülle ist das kleinste konvexe Polygon, das alle Punkte enthält. Graham: Stützpunkt, Polarwinkelsortierung, Stapel und Knicktest über cross; QuickHull: Extreme in x, Rekursion über den von der Kante am weitesten entfernten Punkt (Fläche ∝ |cross|). Kollinearität kann verschiedene Knotenlisten bei derselben Hülle liefern.

Häufige Fragen

Warum liefern Graham und QuickHull manchmal verschiedene Knotenlisten?: Alle extremen Punkte liegen auf dem Rand der konvexen Hülle, aber bei vielen Punkten auf einer Geraden wählen die Verfahren unterschiedlich, welche davon Knoten des Polygons bleiben. Graham mit dem Test ≤ 0 behält in der Regel nur die Enden der kollinearen Strecke; QuickHull ohne zusätzliche Filterung kann Zwischenpunkte auf der Kante mitnehmen. Die konvexe Hülle als Menge in der Ebene fällt zusammen; verschieden ist nur die polygonale Darstellung.
Was bedeutet der hellblaue Streckenzug im Graham-Modus?: Das ist der aktuelle Stapel der Kandidaten für Hüllenknoten am gewählten Schritt — die Teilhülle nach dem entsprechenden Anfangsstück der sortierten Liste. Der rosafarbene Ring ist der Punkt, der gerade auf Aufnahme geprüft wird.
Wie numerisch robust ist das?: Es werden gewöhnliche float64-Zahlen und Kreuzprodukte verwendet. Liegen Punkte fast aufeinander oder fast auf einer Geraden, kann die Orientierung zittern; beim Hinzufügen gilt ein kleiner Abstand zu Nachbarn, damit keine zufälligen Doppelpunkte entstehen.
Wie teilt QuickHull die Punkte?: Nach der Wahl von L und R gehen Punkte streng links der orientierten Geraden LR in die obere Kette, streng rechts in die untere. In jedem Schritt wird unter den übrigen der Punkt C gewählt, der von der aktuellen Kante AB am weitesten entfernt ist (Betrag der orientierten Fläche); die Rekursion läuft dann auf den Mengen außerhalb der Dreiecke ABC, bis außen an der Kante keine Punkte mehr liegen.

Machen Sie mit verwandten Themen in dieser Kategorie weiter — oder alle 85 in „Mathematische Visualisierung“.

Ganze Kategorie →

NeuSchule

Bézier-Kurven und de Casteljau

Simulation starten

Kontrollpunkte legen die Bézier-Kurve fest; der Algorithmus von de Casteljau baut B(t) durch geschachtelte lineare Interpolation.

NeuSchule

Delaunay-Triangulation und Voronoi-Diagramm

Simulation starten

Bowyer–Watson-Triangulation und duales Voronoi-Diagramm: ein Klick ergänzt Standorte, Ziehen verschiebt sie.

NeuSchule

Lineare Regression: KQ, Ridge, Lasso und R²

Simulation starten

Punkte in der Ebene und das Modell y = β₀ + β₁x: gewöhnliche kleinste Quadrate, Ridge (L₂-Strafterm nur auf die Steigung) oder Lasso (L₁-Strafterm). Die Verschiebung Δy am Punkt mit größtem |x| ist ein Ausreißer mit starker Hebelwirkung; verglichen werden SSE und R².

NeuSchule

k-Means (Lloyd-Algorithmus)

Simulation starten

Punkte in der Ebene, Clusterzahl k und Startzentroide. Lloyd-Schritt: Zuordnung zum nächsten Zentrum und Verschiebung des Zentroids in den Schwerpunkt. Demo — Gauß-Mischung; Summe der Quadrate innerhalb der Cluster.

NeuSchule

Gradientenverfahren (2D)

Simulation starten

Niveaulinien von f(x, y) und Bahn (x, y) ← (x, y) − η∇f; Schale oder elliptische Mulde.

NeuSchule

Zweischichtiges Netz und Backpropagation

Simulation starten

Zwei Merkmale und eine binäre Klasse: verdeckte Schicht mit tanh und logistischer Ausgang. Vollständiger Gradient zur mittleren binären Kreuzentropie; Wärmekarte der Wahrscheinlichkeit und Grenze zum Niveau 0,5 (XOR oder Spiralen).

Konvexe Hülle (Graham und QuickHull)

Zum Modell

So funktioniert es

Häufige Fragen

Ähnliche Simulationen

Bézier-Kurven und de Casteljau

Delaunay-Triangulation und Voronoi-Diagramm

Lineare Regression: KQ, Ridge, Lasso und R²

k-Means (Lloyd-Algorithmus)

Gradientenverfahren (2D)

Zweischichtiges Netz und Backpropagation

Konvexe Hülle (Graham und QuickHull)

Zum Modell

So funktioniert es

Häufige Fragen