Ereignisgesteuerte Animation des Graham Scans
Abstract
Graham Scan is a popular method for identifying the convex hull of a set of points. Here we show how event-driven animation can be applied to illustrate this algorithm.
First, we give an outline of the Graham method. Using a simple example, we then demonstrate the animation by showing a series of pictures produced by the animation program. Finally, we discuss the modules of the program, thereby concentrating on the differences to the normal (i.e. the non-animating) version.
Download available (see bottom of the page)
Der Graham Scan ist eine beliebte Methode zur Bestimmung der konvexen Hülle einer Punktemenge. Der Algorithmus ist in der Rubrik Excel-VBA | Anwendungsbeispiele | konvexe Hülle ausführlich besprochen. Hier soll nun gezeigt werden, wie man die Technik der ereignisgesteuerten Animation auf diesen Algorithmus anwenden kann.
Wir betrachten zunächst den Algorithmus in seinen Grundzügen, damit die anschließende Beschreibung der Animation verständlich wird:
Die Graham-Methode zur Ermittlung der konvexen Hülle
Der Graham Scan ist ein sehr eleganter Algorithmus, der einen Stapel (stack) benutzt, um die Punkte der Hülle zusammen zu stellen. Außerdem wird eine Sortierfunktion gebraucht.
Die Graham-Methode basiert auf der folgenden Eigenschaft der konvexen Hülle:
Folgt man der Linie der konvexen Hülle gegen den Uhrzeigersinn, so muss auf diesem Weg niemals nach rechts abgebogen werden.
Das Vorgehen in sehr grober Form (in Anlehnung an Cormen et al.: Introduction to Algorithms):
1. Bestimme den untersten Punkt p(0) (falls nicht eindeutig, dann von den untersten den am weitesten links liegenden).
2. Ordne die restlichen Punkte P(i) nach dem Winkel zwischen der Horizontalen durch P(0) und der Verbindung zwischen P(0) und P(i) (sog. Polarwinkel). Gibt es mehrere Punkte mit demselben Winkel, so nimm nur den am weitesten von P(0) entfernten.
3. Durchlaufe die Punkte P(0), P(1), …, P(n) in dieser Reihenfolge und sammle die Punkte der Hülle nach der folgenden Regel: wird auf dem Weg von P(i) nach P(k) über P(j) in P(j) nicht links abgebogen, so gehört P(j) nicht zur Hülle.
Die vorbereitende Sortierung (Schritt 2) ist im Vergleich zum eigentlichen Scan (Schritt 3) aufwändiger. Schritt 3 ist mit Hilfe eines Stapels ohne großen Aufwand durchzuführen. Hier der detaillierte Ablauf in Pseudocode:
Beginne mit einem leeren Stapel S
Push (S, P(0))
Push (S, P(1))
Push (S, P(2))
For i = 3 to n
Do While (der von NextToTop(S), Top(S) und P(i) gebildete Winkel
ist nicht nach links gerichtet)
Pop(S)
Loop
Push (S, P(i))
Next i
Die Animation
Unser Animationsprogramm führt zwar den gesamten Algorithmus durch, die Animation selbst, also die dem Benutzer gezeigte Bilderfolge, konzentriert sich jedoch auf den dritten Hauptabschnitt, den eigentlichen Scan.
Wie der oben stehende Pseudocode dieses Abschnitts zeigt, werden in diesem Abschnitt die Punkte der Hülle auf dem Stapel gesammelt. Hierzu werden die vorsortierten Punkte nacheinander inspiziert und auf den Stapel gelegt. Stellt sich bei der Inspektion eines Punktes heraus, dass er nur durch ein Abbiegen nach rechts erreichbar wäre, so werden nacheinander von den bereits auf dem Stapel gesammelten Punkten so viele entfernt, bis der nächste Punkt durch Linksabbiegen erreicht werden kann.
Man kann es auch so ausdrücken: wird ein Punkt auf den Stapel gelegt, dann weiß man noch nicht, ob er wirklich zur Hülle gehören wird. Dies wird erst deutlich, wenn man die folgenden Punkte betrachtet.
Die folgende Bildserie entspricht den Bildern, die bei einem Animationslauf mit einer kleinen Punktemenge nacheinander ausgegeben wurden. Der jeweilige Stand der Hüllenberechnung, also der Inhalt des Stapels, entspricht den durch den roten Linienzug verbundenen Punkten.
Der provisorische Charakter der Punktsammlung kann anhand des Beispiels gut nachvollzogen werden. Um vom dritten zum vierten Punkt zu gelangen, musste man scharf links abbiegen (s. viertes Bild). Vom vierten zum fünften Punkt wäre danach eine unzulässige Abbiegung nach rechts nötig gewesen. Nach Entfernung des vierten Punkts aus dem Stapel (Bild 5), kann der Weg zum fünften Punkt (= vierter Punkt der Hülle) ohne Rechtsabbiegen fortgesetzt werden (Bild 6).
Das Animationsprogramm
Es besteht aus drei Schichten, welche der unter Rubrik “ereignisgesteuerte Animation” beschriebenen Architektur genügen. Die Schichten sind, von oben nach unten:
- Das UI, hier in Gestalt eines Formulars CHDiagrammForm. Mit Hilfe dieses Formulars werden die Animationsparameter vom Benutzer eingelesen. Diese sind: (1) Bereich auf einem Arbeitsblatt, wo sich die Wertetabelle der Punkte befindet, die eingehüllt werden sollen, (2) Dauer der gewünschten Verzögerung zwischen den Animationsschritten. Nach dem Einlesen der Parameter werden diese mit einem Aufruf an ein Objekt der Klasse GrahamAnimator weitergegeben.
- Die Klasse GrahamAnimator, welche die Animation durchführt, indem es ein Objekt der Klasse convexHull mit der Errechnung der konvexen Hülle beauftragt und die von diesem Objekt ausgelösten Ereignisse auffängt und das Diagramm auf dem Arbeitsblatt einfügt.
- Eine Klasse convexHull, welche für die Durchführung des Algorithmus zuständig ist und während dieser Durchführung Ereignisse auslöst, die vom GrahamAnimator verwertet werden können.
Das Programm zur Ermittlung der konvexen Hülle ist bereits unter der Rubrik Excel-VBA | Anwendungsbeispiele behandelt worden. Wir betrachten deshalb hier nur die Änderungen, welche die Animation gegenüber der Normalversion erforderlich macht. Beginnen wir bei der untersten Schicht:
Klasse convexHull
Die Änderungen gegenüber der Normalversion sind durch grüne Schrift hervorgehoben:
- Die Klasse beginnt nun mit der Deklaration eines Ereignisses stackChanged. Bei der Auslösung dieses Ereignisses wird ein Parameter stateA an die ereignisbehandelnde Stelle geliefert. Es handelt sich hierbei um ein Array, das die Koordinaten der Punkte enthält, die sich gerade auf dem Stapel befinden.
- Die Funktion getStatus ist eine Hilfsfunktion, welche das mit dem Ereignis zu liefernde Punkte-Array zusammenstellt. Sie benötigt hierfür den Inhalt des Stapels und, weil dieser nur die Indizes der Punkte enthält, zusätzlich das Array mit deren Koordinaten.
- An mehreren Stellen der Funktion convexHull_GS wird mit RaiseEvent das Ereignis stackChanged ausgelöst. Dies sind, wie zu erwarten, die Stellen, an denen etwas auf den Stapel gelegt oder davon weggenommen wird. Ein letztes Mal wird dann das Ereignis nach dem Scan ausgelöst, um eine zusätzliche Verzögerung auszulösen, bevor dem Hüllenbild die letzte Einzellinie (die zum Ausgangspunkt) hinzugefügt wird.
‘----------------------
‘class convexHull
‘----------------------
Option Explicit
'produces a list of points representing the convex hull for the
'set of points p by use of the Graham scan method; animation version
'--------------------------------------------------------------------------------------------
Public Event stackChanged(ByRef stateA() As Double)
Public Function convexHull_GS(ByRef p() As Double) As Double()
Dim i As Long, j As Integer, k As Long
Dim numPts As Long, numNpts As Long, minPt As Long
Dim h() As Double 'contains all pts, but not starting pt, with neg.
' direction cosines and distance from starting pt
Dim s() As Double 'for sorted pts
Dim t() As Double 'points, sorted and unnecessary ones ommitted
Dim st As stack
numPts = UBound(p, 1)
'search starting point (point having min x within min y
minPt = 1
For i = 2 To numPts
If p(i, 2) < p(minPt, 2) Then
minPt = i
Else
If p(i, 2) = p(minPt, 2) And p(i, 1) < p(minPt, 1) Then minPt = i
End If
Next i
'copy points (without starting point) to h;
'add neg. direction cosines and distances from starting point
ReDim h(1 To numPts - 1, 1 To 4)
j = 1
For i = 1 To numPts
If i <> minPt Then
h(j, 1) = p(i, 1)
h(j, 2) = p(i, 2)
'calculating negative of direction cosine
h(j, 3) = -((p(i, 1) - p(minPt, 1)) / _
((p(i, 1) - p(minPt, 1)) ^ 2 + (p(i, 2) - p(minPt, 2)) ^ 2) ^ 0.5)
'add distance from starting point
h(j, 4) = Dist(p(minPt, 1), p(minPt, 2), p(i, 1), p(i, 2))
j = j + 1
End If
Next i
'sort according to negative of direction cosine and distance
'from starting point; copy to s
s = sort.matrSort2(h, 3, 4)
'eliminate all but one point with identical cosines by copying selectively
ReDim t(0 To numPts - 1, 1 To 3) 'index 0 is for starting point
Dim copy As Boolean
numNpts = 0
i = 1
Do While i <= numPts - 1
If i = numPts - 1 Then
copy = True
Else
If s(i, 3) <> s(i + 1, 3) Then copy = True Else copy = False
End If
If copy Then
numNpts = numNpts + 1
For j = 1 To 3
t(numNpts, j) = s(i, j)
Next j
End If
i = i + 1
Loop
t(0, 1) = p(minPt, 1) 'insert starting point
t(0, 2) = p(minPt, 2)
'scan and hold back the points of the hull in the stack
'the elements of the stack are indices referring to array t
Set st = New stack
st.initStack
st.push (0)
st.push (1)
RaiseEvent stackChanged(getStatus(st.stackArray, t))
st.push (2)
RaiseEvent stackChanged(getStatus(st.stackArray, t))
For i = 3 To numNpts
'remove from stack points that are not part of the hull
Do While Not isLeft(t(st.nextToTop, 1), t(st.nextToTop, 2), _
t(st.top, 1), t(st.top, 2), t(i, 1), t(i, 2))
st.pop
RaiseEvent stackChanged(getStatus(st.stackArray, t))
Loop
'push the current point on the stack
st.push (i)
RaiseEvent stackChanged(getStatus(st.stackArray, t))
Next i
RaiseEvent stackChanged(getStatus(st.stackArray, t))
'get stack contents in total; copy its elements from t to d
Dim sa() As Variant
sa = st.stackArray
Dim d() As Double
ReDim d(1 To UBound(sa) + 1, 1 To 2)
For i = 1 To UBound(d, 1) - 1
For j = 1 To UBound(d, 2)
d(i, j) = CDbl(t(CLng(sa(i)), j))
Next j
Next i
d(UBound(d, 1), 1) = t(0, 1) 'add starting point a second time
d(UBound(d, 1), 2) = t(0, 2) 'in order to close the circle
convexHull_GS = d
End Function
'providing points on stack for animation purposes
Private Function getStatus(ByRef sa As Variant, _
ByRef t() As Double) As Double()
Dim i As Long, j As Long
Dim d() As Double
ReDim d(1 To UBound(sa), 1 To 2)
For i = 1 To UBound(d, 1)
For j = 1 To UBound(d, 2)
d(i, j) = CDbl(t(CLng(sa(i)), j))
Next j
Next i
getStatus = d
End Function
'takes the coordinates of three points p1, p2, p3, and checks if
'we turn to the left in p2 when following the path p1p2p3
Private Function isLeft(ByVal x1 As Double, ByVal y1 As Double, _
ByVal x2 As Double, ByVal y2 As Double, _
ByVal x3 As Double, ByVal y3 As Double) As Boolean
isLeft = (x3 - x2) * (y2 - y1) - (y3 - y2) * (x2 - x1) < 0
End Function
'calculates euclidian distance between (x1,y1) and (x2,y2)
Private Function Dist(ByVal x1 As Double, ByVal y1 As Double, _
ByVal x2 As Double, ByVal y2 As Double) As Double
Dist = ((x2 - x1) ^ 2 + (y2 - y1) ^ 2) ^ 0.5
End Function
Klasse GrahamAnimator
Die Klasse besitzt eine Instanzenvariable vom Typ convexHull, welche mit der Durchführung des Algorithmus betraut wird. Wichtig ist, dass diese Variable mit dem Zusatz WithEvents deklariert wird. Die Instanzenvariable serH dient der Übergabe der Hüllenpunkte an das Diagramm. Die dritte Instanzenvariable, d, speichert die gewünschte zeitliche Verzögerung zwischen den Einzelschritten.
Die Hauptprozedur ist doAnimation. Dies ist die Prozedur, die aus dem UI zur Ausführung der Animation aufgerufen wird. Die Prozedur bereitet das Diagramm vor und besetzt es schon vor der Durchführung des Graham Scans mit den Punkten des Streudiagramms. Dann stößt sie die Ermittlung der konvexen Hülle an und fügt schließlich das Ergebnis dieser Ermittlung in das Diagramm ein.
Die Prozedur convH_stackChanged tritt in Aktion, wenn im Objekt convH das Ereignis stackChanged ausgelöst wird, also immer dann, wenn ein Punkt auf den Stapel gelegt oder von dort weggenommen wird. Die Prozedur aktualisiert das Diagramm sofort mit dem aktuellen Stand der Hüllenermittlung.
Das Hüllen-Diagramm wird also während der Durchführung von doAnimation von zwei Stellen aus aktualisiert: die Verantwortung für die Aktualisierung vor der Fertigstellung liegt bei der Ereignisprozedur convH_stackChanged, die Aktualisierung nach der Fertigstellung bei doAnimation selbst.
‘------------------------------
‘class GrahamAnimator
‘------------------------------
Option Explicit
Private serH As Series 'for the chart, points of the hull
Private WithEvents convh As convexHull 'calculates the hull
Private d As Single 'delay
'controls the animation
Public Sub doAnimation(ByRef pts() As Double, _
ByVal outR As Range, _
ByVal duration As Single)
Dim serA As Series 'for the scatter plot
Dim hull() As Double 'pts of the hull
Dim w As Worksheet 'output worksheet
Dim sh As Shape
Set convh = New convexHull
d = duration
'prepare chart
Set w = outR.Parent
w.Activate
On Error Resume Next
w.ChartObjects.Delete
Set sh = w.Shapes.AddChart
With outR
sh.top = .top
sh.Left = .Left
sh.Height = .Height
sh.Width = .Width
End With
With sh.Chart
'scatter plot
Set serA = .SeriesCollection.NewSeries
serA.values = col(pts, 2)
serA.XValues = col(pts, 1)
.ChartType = xlXYScatter
.HasLegend = False
'convex hull
Set serH = .SeriesCollection.NewSeries
hull = convh.convexHull_GS(pts)
serH.XValues = col(hull, 1)
serH.values = col(hull, 2)
serH.ChartType = xlXYScatterLinesNoMarkers
End With
End Sub
'extracts column colNo from matrix m
Public Function col(ByRef m() As Double, ByVal colNo As Integer) As Double()
Dim i As Integer
Dim c() As Double
ReDim c(1 To UBound(m, 1))
For i = 1 To UBound(m, 1)
c(i) = m(i, colNo)
Next i
col = c
End Function
'causes a delay
Private Sub delay(ByVal duration As Single)
Dim t As Single
t = Timer
Do While Timer < t + duration
DoEvents
Loop
End Sub
'event procedure: when contents of stack changes
Private Sub convh_stackChanged(ByRef stateA() As Double)
delay d
serH.XValues = col(stateA, 1)
serH.values = col(stateA, 2)
serH.ChartType = xlXYScatterLinesNoMarkers
End Sub
Das UI
Das einfache Formular gestattet dem Benutzer, den Bereich einzugeben, in dem sich die Wertetabelle mit den zu umhüllenden Punkten befindet. Es genügt dabei, wenn der Benutzer eine einzige Zelle in diesem Bereich markiert. Außerdem kann er die Dauer der Verzögerung auswählen, die zwischen die einzelnen Animationsschritte eingefügt werden soll. Mögliche Werte sind 0 bis 10.
Die Ausgabe des Diagramms bzw. der Animation erfolgt auf dem Arbeitsblatt „Graham“. Ist ein Arbeitsblatt dieses Namens noch nicht vorhanden, dann wird es angelegt.
‘--------------------------------
‘class chDiagramForm
‘--------------------------------
Option Explicit
Private ga As GrahamAnimator
Private Sub UserForm_Initialize()
Dim i As Integer
Set ga = New GrahamAnimator
For i = 0 To 10
Me.DauerCBx.AddItem i
Next i
Me.DauerCBx.Value = 1
End Sub
Private Sub AnlegenBtn_Click()
Dim p As Range 'input range
Dim pts() As Double 'points in p
Set p = Range(Me.AllesRefE.Text).CurrentRegion
pts = RangeToDoubleArray(p)
duration = CInt(Me.DauerCBx.Text)
'worksheet for output is prepared
If Not wrkshExists("Graham") Then
Worksheets.Add.Name = "Graham"
End If
Set w = Worksheets("Graham")
ga.doAnimation pts, w.Range("B2:D13"), duration
End Sub
Public Function RangeToDoubleArray(ByVal r As Range) As Double()
Dim i As Integer, j As Integer
Dim a() As Double
ReDim a(1 To r.Rows.Count, 1 To r.Columns.Count)
For i = 1 To UBound(a, 1)
For j = 1 To UBound(a, 2)
a(i, j) = CDbl(r(i, j))
Next j
Next i
RangeToDoubleArray = a
End Function
Private Function wrkshExists(ByVal wName As String) As Boolean
wrkshExists = False
Dim w As Worksheet
For Each w In Worksheets
If w.Name = wName Then
wrkshExists = True
Exit For
End If
Next w
End Function
Download
