Konvexe Hülle

Konvexe Hülle einer Punktmenge

Über diesen Rechner

Der Rechner für die konvexe Hülle findet mit Andrews monotone-Kette-Algorithmus das kleinste konvexe Polygon, das eine Menge von 2D-Punkten umschließt. Er listet die Eckpunkte der Hülle gegen den Uhrzeigersinn auf, zählt, wie viele Punkte auf der Hülle im Vergleich zu innerhalb liegen, und gibt die exakte Fläche und den Umfang an, mit einem Streudiagramm, das das Ergebnis umrandet. Doppelte und kollineare Punkte werden korrekt behandelt.

So finden Sie eine konvexe Hülle

  1. Geben Sie Ihre Punkte als durch Kommas getrennte x,y-Paare ein — die Reihenfolge spielt keine Rolle.
  2. Der Rechner fasst Duplikate zusammen und sortiert die Punkte von links nach rechts.
  3. Er durchläuft die sortierten Punkte, um den unteren und oberen Rand aufzubauen, und behält nur die Eckpunkte, an denen der Umriss nach links abbiegt.
  4. Lesen Sie die Hülleneckpunkte, die Fläche und den Umfang ab und sehen Sie den über Ihren Punkten gezeichneten Umriss.

Häufige Beispiele

  • Quadratecken 0,0 6,0 6,4 0,4 mit inneren Punkten 3,2 und 2,1 → 4 Hülleneckpunkte, Fläche 24, Umfang 20
  • Dreieck 0,0 4,0 0,3 → 3 Hülleneckpunkte, Fläche 6, Umfang 12
  • Kollineare Punkte 0,0 1,1 2,2 3,3 → entartete Hülle (eine Strecke), Fläche 0
  • Quadrat 0,0 4,0 4,4 0,4 plus Spitze 2,5 → 5 Hülleneckpunkte, da die Spitze die obere Kante erweitert

Häufig gestellte Fragen

Was ist eine konvexe Hülle?

Die konvexe Hülle einer Punktmenge ist das kleinste konvexe Polygon, das alle Punkte enthält — als würde man ein Gummiband um die äußersten Punkte spannen und es straff zuschnappen lassen.

Welche Punkte werden zu Hülleneckpunkten?

Nur die äußersten Eckpunkte liegen auf der Hülle. Punkte streng innerhalb der Form sowie Punkte, die genau auf einer Hüllenkante liegen, werden nicht als Eckpunkte aufgeführt.

Wie werden doppelte oder kollineare Punkte behandelt?

Identische Punkte werden zuerst zusammengefasst. Wenn alle Punkte auf einer einzigen Geraden liegen, schrumpft die Hülle zu einer Strecke mit Fläche null, was der Rechner als entartete Hülle meldet.

Wie viele Punkte benötige ich?

Es sind mindestens drei verschiedene, nicht kollineare Punkte erforderlich, um eine Hülle mit positiver Fläche zu bilden.