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 Werte­tabelle 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

Animation des Graham Scan (incl. Punktegenerator)
Benutzen Sie zum Starten der Programme die Schaltflächen auf dem Arbeitsblatt Start. Schließen Sie den Punktegenerator, bevor Sie das Animationsprogramm starten.
CH_anim3.zip
Komprimiertes Archiv im ZIP Format 55.9 KB