Der Graham Scan (nach Ronald Graham 1972) ist ein effizienter Algorithmus zur Berechnung der konvexen Hülle einer endlichen Menge von Punkten in der Ebene. Bei Punkten liegt seine asymptotische Laufzeit in .

Animation des Graham Scan Algorithmus

BeschreibungBearbeiten

VorbereitungBearbeiten

 
Sortierung einer Punktmenge nach Winkel mit Bezugspunkt  .

Sei   eine endliche Punktmenge. Der Algorithmus beginnt mit einem Punkt der Menge, welcher garantiert ein Eckpunkt der konvexen Hülle ist. Man sucht sich dazu den Punkt mit der kleinsten Ordinate. Sind dies mehrere, so sucht man sich aus diesen Punkten den mit der kleinsten Abszisse aus (lexikographische Suche). Diese Suche kann in   Schritten durchgeführt werden. Nachdem der Startpunkt   gefunden wurde, sortiert der Algorithmus die restlichen Punkte   in   nach aufsteigendem Winkel zwischen    und der x-Achse gegen den Uhrzeigersinn. Haben dabei zwei Punkte den gleichen Winkel (d. h. liegen mit   auf einer Linie, sind kollinear mit  ), so wird der Punkt, welcher näher an   liegt, verworfen.

HilfsfunktionBearbeiten

 
PAB und ABC sind positiv orientierte Dreiecke, BCD ist negativ orientiert. Oder anders, C liegt links von AB, D liegt rechts von BC. Der Stack wird bis [P,A,B,C] aufgebaut, im nächsten Schritt wird C zugunsten von D entfernt.

In der nachfolgenden Rechnung muss wiederholt entschieden werden, ob drei Punkte  ,  ,   in der Ebene ein positiv orientiertes Dreieck bilden. Äquivalente Formulierungen dafür sind, dass der Streckenzug   einen Knick nach links hat oder dass der Punkt   links der Strecke von   nach   bzw. der Punkt   rechts von der Strecke von   nach   liegt.

Diese Aufgabe kann man durch Bestimmen aller relevanten Winkel lösen, oder einfacher durch die Berechnung einer Determinante  , diese liefert das gewünschte Ergebnis mit weniger Rechenaufwand (fünf Subtraktionen, zwei Multiplikationen) und genauer. Das Ergebnis bleibt für rationale Koordinaten im rationalen Zahlenbereich, welcher ohne Verlust von Genauigkeit im Computer abgebildet werden kann. Das Ergebnis wird über den folgenden Ausdruck berechnet.

 

BerechnungBearbeiten

 
Nach Winkel sortierte Punktmenge –   wird als Startpunkt gewählt, da er den kleinsten Ordinatenwert hat.   fällt heraus, da er mit   und   kollinear ist.

  sei nun die sortierte Punktmenge. Als Nächstes läuft man alle Punkte in   durch und prüft, ob diese Eckpunkte der konvexen Hülle sind. Es wird ein Stapelspeicher (Stack) angelegt, auf welchem sich alle Eckpunkte der konvexen Hülle für alle bereits abgearbeiteten Punkte befinden. Zu Beginn liegen   und   auf dem Stapel. Im  -ten Schritt wird   zur Betrachtung herangezogen und berechnet, wie er die vorherige konvexe Hülle verändert. Aufgrund der Sortierung liegt   immer außerhalb der Hülle der vorherigen Punkte   mit  .

Durch das Hinzufügen des Punktes kann es vorkommen, dass bereits auf dem Stapel liegende Punkte nicht mehr zur neuen konvexen Hülle gehören. Diese Punkte müssen mittels der „pop“ Operation vom Stapel entfernt werden. Ob ein Punkt noch zur konvexen Hülle gehört oder nicht ermittelt man, indem man berechnet, ob   links oder rechts des Vektors PT2→PT1 liegt (PT1 = oberstes Element des Stapels, PT2 = Element direkt unter PT1). Liegt   links, so bleibt PT1 weiterhin auf dem Stapel und   wird mit „push“ auf dem Stapel abgelegt, liegt   rechts, so wird PT1 von der neuen konvexen Hülle verschluckt, vom Stapel entfernt und die nächsten beiden oberen Punkte untersucht.

Dieser Test wird solange durchgeführt, bis   links des Vektors PT2→PT1 oder nur noch   und ein weiterer Punkt auf dem Stapel liegt. In beiden Fällen wird dann   auf dem Stapel abgelegt und mit dem nächsten Punkt   weitergerechnet. Die folgende Abbildung zeigt ein Beispiel, in welchem alle Fälle des eben beschriebenen Tests auftreten.

 
Beispiel – Graham Scan Algorithmus

In nebenstehender Abbildung werden zunächst die Punkte Pt4, Pt3, Pt2 und   auf den Stack gelegt. Zu jedem Zeitpunkt bilden die Punkte auf dem Stack ein konvexes Polygon (gestrichelte Linien). Erst als   hinzukommen soll, fallen   und Pt2 wieder raus, da sie zusammen mit   nicht konvex sind. Die konvexe Hülle dieser Punktmenge besteht aus  , Pt4, Pt3 und  .   liegt dabei auf dem Stack ganz unten und   ganz oben. Die Punkte des gesuchten konvexen Polygons können mit „pop“ im Uhrzeigersinn vom Stapel geholt werden.

AnmerkungBearbeiten

Die Anzahl der „push“ und „pop“ Operationen übersteigt die obere Grenze von   (  = Anzahl der Punkte in der Eingabemenge) nicht. Die Berechnung ist also  . Die Sortierung der Punkte nach Winkel kann mit jedem beliebigen Sortieralgorithmus durchgeführt werden, z. B. Mergesort. Dieser hat eine asymptotische Laufzeit von  . Das bedeutet, dass die Laufzeit des Algorithmus durch die Sortierung vorgegeben ist, da  .

PseudocodeBearbeiten

Unter Nutzung eines StacksBearbeiten

Funktion GrahamScan
  Eingabe: Punktemenge S = {P}
  Ausgabe: konvexe Hülle von S
  Beginn Funktion
    Sei S die nach dem Winkel zu P0 sortierte Punktemenge
    PUSH(P0)
    PUSH(P1)
    i := 2
    n := Anzahl der Punkte in S
    
    Solange i < n, führe aus:
      Sei Pt1 der oberste Punkt auf dem Stack
      Sei Pt2 der zweitoberste Punkt auf dem Stack
      Wenn Si links des Vektors Pt2→Pt1 liegt oder Stack enthält 2 Elemente, dann führe aus:
        PUSH(Si)
        i := i + 1
      Ansonsten führe aus:
        POP(Pt1)
      Ende Bedingung
      
    Ende Schleife
    
  Ende Funktion

Ohne Nutzung eines StacksBearbeiten

Funktion GrahamScan
  Eingabe: Punktemenge S = {P}
  Ausgabe: konvexe Hülle von S
  Beginn Funktion
    Sei S die nach dem Winkel zu P0 sortierte Punktemenge
    i := 1
    
    Solange i ≤ |S|:
      Wenn Si rechts des Vektors Si−1→Si+1 liegt, dann führe aus:
        i := i + 1
      Ansonsten führe aus:
        Entferne das Element Si aus S
        i := i - 1
      Ende Bedingung
    
    Ende Schleife
  
  Ende Funktion

Im Code sei punkte ein Array aus Punkten, aus dem man mit punkte[i] das i-te Element erhält und welches schon nach dem Winkel zu punkte[0] sortiert ist. Der Code verändert dieses Array, indem die Elemente gelöscht werden, die nicht zur konvexen Hülle gehören.

ProgrammierungBearbeiten

Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung des Graham Scan Algorithmus. Die Punkte und die konvexe Hülle werden auf dem Hauptfenster gezeichnet. Das Programm verwendet mehrere Klassen. Die Methoden für den eigentlichen Algorithmus werden in der Klasse GrahamScan deklariert.[1][2]

Code-Schnipsel  
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;

// Klasse, die die Methoden für den Algorithmus Graham Scan deklariert
class GrahamScan
{
	// Diese Methode gibt das zweitoberste Element im Stack der Punkte zurück
	private PointF GetNextToTopElement(Stack<PointF> points)
	{
		PointF topElement = points.Peek();
		points.Pop();
		PointF nextToTopElement = points.Peek();
		points.Push(topElement);
		return nextToTopElement;
	}
	
	// Diese Methode gibt den Abstand der zwei Punkte zurück
	private float GetDistance(PointF point1, PointF point2)
	{
		return (point1.X - point2.X) * (point1.X - point2.X) + (point1.Y - point2.Y) * (point1.Y - point2.Y);
	}
	
	// Diese Methode bestimmt die Orientierung des drei Punkte. Wenn die Punkte im Uhrzeigersinn sind, wird der Wert 1 zurückgegeben. Wenn die Punkte im Gegenuhrzeigersinn sind, wird der Wert -1 zurückgegeben. Wenn die Punkte kollinear sind, wird der Wert 0 zurückgegeben.
	private int GetOrientation(PointF point1, PointF point2, PointF point3)
	{
		float area = (point2.Y - point1.Y) * (point3.X - point2.X) - (point2.X - point1.X) * (point3.Y - point2.Y);
		if (area > 0) // Wenn das Vorzeichen positiv ist, sind die Punkte im Uhrzeigersinn
		{
			return 1;
		}
		if (area < 0) // Wenn das Vorzeichen negativ ist, sind die Punkte im Gegenuhrzeigersinn
		{
			return -1;
		}
		return 0; // Wenn der Flächeninhalt gleich 0 ist, sind die Punkte kollinear
	}
	
	// Diese Klasse implementiert eine Vergleichsmethode für das Sortieren der Punkte
	class PointComparer : Comparer<PointF>
	{
		public PointF center;
		public GrahamScan grahamScan;
		
		// Vergleichsmethode, die die Punkte in Bezug auf den Punkt center sortiert
		public override int Compare(PointF point1, PointF point2)
		{
			int orientation = grahamScan.GetOrientation(center, point1, point2);
			if (orientation == 0)
			{
				if (grahamScan.GetDistance(center, point2) >= grahamScan.GetDistance(center, point1))
				{
					return -1;
				}
				return 1;
			}
			return orientation;
		}
	}
	
	// Diese Methode gibt eine Liste der Punkte der konvexen Hülle zurück
	public List<PointF> GetConvexHull(List<PointF> points)
	{
		List<PointF> convexHull = new List<PointF>(); // Initialisiert die Liste der Punkte der konvexen Hülle
		float minimumY = points[0].Y;
		int indexOfMinimum = 0;
		int numberOfpoints = points.Count;
		// Diese for-Schleife durchläuft die verbleibenden Punkte und ermittelt den untersten Punkt und bei Gleichheit den Punkt ganz links
		for (int i = 1; i < numberOfpoints; i++)
		{
			float y = points[i].Y;
			if (y < minimumY || minimumY == y && points[i].X < points[indexOfMinimum].X)
			{
				minimumY = points[i].Y;
				indexOfMinimum = i;
			}
		}
		// Setzt den untersten Punkt an die erste Position
		PointF point = points[0];
		points[0] = points[indexOfMinimum];
		points[indexOfMinimum] = point;
		// Initialisiert das Objekt, das die Vergleichsmethode bereitstellt
		PointComparer pointComparer = new PointComparer();
		pointComparer.center = points[0];
		pointComparer.grahamScan = this;
		points.Sort(pointComparer); // Sortiert die Punkte in Bezug auf den ersten Punkt
		// Wenn zwei oder mehr Punkte den gleichen Winkel mit dem Punkt point bilden, werden alle entfernt außer dem Punkt, der am weitesten vom Punkt point entfernt ist
		int index = 1;
		for (int i = 1; i < numberOfpoints; i++)
		{
			// Entfernt jeweils das Element mit Index i, solange die Punkte der gegebenen Elemente kollinear sind
			while (i < numberOfpoints - 1 && GetOrientation(pointComparer.center, points[i], points[i + 1]) == 0)
			{
				i++;
			}
			points[index] = points[i];
			index++;
		}
		if (index < 3) // Wenn weniger als 3 Punkte vorhanden sind, wird eine leere Liste zurückgegeben
		{
			return convexHull;
		}
		// Erzeugt einen Stack und fügt die ersten 3 Punkte hinzu
		Stack<PointF> pointStack = new Stack<PointF>();
		pointStack.Push(points[0]);
		pointStack.Push(points[1]);
		pointStack.Push(points[2]);
		// Diese for-Schleife durchläuft die verbleibenden Punkte
		for (int i = 3; i < index; i++)
		{
			// Entfernt jeweils das oberste Element des Stack, solange die Punkte der gegebenen Elemente im Uhrzeigersinn sind
			while (pointStack.Count > 1 && GetOrientation(GetNextToTopElement(pointStack), pointStack.Peek(), points[i]) != -1)
			{
				pointStack.Pop();
			}
			pointStack.Push(points[i]);
		}
		// Fügt die Punkte des Stack der Liste der Punkte der konvexen Hülle hinzu
		while (pointStack.Count != 0)
		{
			convexHull.Add(pointStack.Peek());
			pointStack.Pop();
		}
		return convexHull;
	}
}

// Klasse für das Hauptfenster
public partial class MainForm : Form
{
	private Graphics graphics;
	
	private List<PointF> points = new List<PointF>(); // Liste der Punkte
	private List<PointF> convexHull = new List<PointF>(); // Liste der Punkte der konvexen Hülle
	private double x1, y1, x2, y2;
	
	public MainForm()
	{
		x1 = 100; y1 = 100; x2 = 700; y2 = 700; // Setzt die Koordinaten der Eckpunkte der quadratischen Zeichenfläche
		Random random = new Random(); // Initialisiert den Zufallsgenerator
		int numberOfPoints = 100;
		for (int i = 0; i < numberOfPoints; i++) // Diese for-Schleife erzeugt 100 zufällige Punkte innerhalb der quadratischen Zeichenfläche
		{
			PointF point = new PointF();
			point.X = (float)(random.NextDouble() * (x2 - x1) + x1);
			point.Y = (float)(random.NextDouble() * (y2 - y1) + y1);
			points.Add(point); // Fügt den Punkt der Liste hinzu
		}
		
		GrahamScan grahamScan = new GrahamScan(); // Erzeugt ein Objekt der Klasse GrahamScan
		convexHull = grahamScan.GetConvexHull(points); // Aufruf der Methode, die die konvexe Hülle zurückgibt
		
		InitializeComponent();
		Text = "Konvexe Hülle";
		Width = 800;
		Height = 800;
		graphics = CreateGraphics(); // Erzeugt ein Grafikobjekt für das Zeichnen auf dem Hauptfenster.
		Paint += OnPaint; // Verknüpft die Ereignisbehandlungsmethode mit dem Paint Ereignis des Hauptfensters.
	}
	
	// Diese Methode wird aufgerufen, wenn das Hauptfenster gezeichnet wird.
	private void OnPaint(object sender, PaintEventArgs e)
	{
		for (int i = 0; i < points.Count; i++)
		{
			graphics.FillRectangle(new SolidBrush(Color.FromArgb(0, 0, 0)), points[i].X - 1, points[i].Y - 1, 2, 2); // Zeichnet die Punkte
		}
		int numberOfPoints = convexHull.Count;
		for (int i = 0; i < numberOfPoints; i++)
		{
			graphics.DrawLine(new Pen(Color.FromArgb(0, 0, 255)), convexHull[i], convexHull[(i + 1) % numberOfPoints]); // Zeichnet die Kanten der konvexen Hülle
		}
	}
}

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  1. Rosetta Code: Convex hull
  2. GeeksforGeeks: Convex Hull