Graham scan

The Graham Scan (after Ronald Graham 1972) is an efficient algorithm for computing the convex hull of a finite set of points in the plane. For points, its asymptotic running time is in . ${\displaystyle n}$ ${\displaystyle {\mathcal {O}}(n\cdot \log n)}$

description

preparation

Sorting a set of points by angle with reference point . ${\displaystyle P_{0}}$

Let be a finite set of points. The algorithm starts with a point of the set, which is guaranteed to be a corner point of the convex hull. To do this, look for the point with the smallest ordinate . If there are several, then from these points the one with the smallest abscissa is selected ( lexicographical search). This search can be carried out in steps. After the starting point has been found, the algorithm sorts the remaining points in an ascending order between → and the x-axis counterclockwise. If two points have the same angle (i.e. are on a line with, are collinear with ), then the point which is closer to is discarded. ${\displaystyle S=\{P\}}$ ${\displaystyle O(n)}$ ${\displaystyle P_{0}}$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle P_{0}}$ ${\displaystyle P}$ ${\displaystyle P_{0}}$ ${\displaystyle P_{0}}$ ${\displaystyle P_{0}}$

Auxiliary function

PAB and ABC are positively oriented triangles, BCD is negatively oriented. Or to put it another way, C is to the left of AB, D is to the right of BC. The stack is built up to [P, A, B, C], in the next step C is removed in favor of D.

In the following account has repeatedly held that if three points , , form in the plane a positively oriented triangle. Equivalent formulations for this are that the line has a bend to the left or that the point to the left of the line from to or the point to the right of the line from to lies. ${\displaystyle A=(x_{A},y_{A})}$ ${\displaystyle B=(x_{B},y_{B})}$ ${\displaystyle C=(x_{C},y_{C})}$ ${\displaystyle ABC}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle C}$

This task can be solved by determining all relevant angles or, more simply, by calculating a determinant , which delivers the desired result with less computational effort (five subtractions, two multiplications) and more precisely. The result remains for rational coordinates in the rational number range , which can be mapped in the computer without loss of accuracy. The result is calculated using the following expression. ${\displaystyle T(A,B,C)}$

${\displaystyle {\begin{aligned}T(A,B,C)&={\begin{vmatrix}1&x_{A}&y_{A}\\1&x_{B}&y_{B}\\1&x_{C}&y_{C}\end{vmatrix}}={\begin{vmatrix}1&x_{A}&y_{A}\\0&x_{B}-x_{A}&y_{B}-y_{A}\\0&x_{C}-x_{A}&y_{C}-y_{A}\end{vmatrix}}={\begin{vmatrix}x_{B}-x_{A}&y_{B}-y_{A}\\x_{C}-x_{A}&y_{C}-y_{A}\end{vmatrix}}\\&=(x_{B}-x_{A})(y_{C}-y_{A})-(x_{C}-x_{A})(y_{B}-y_{A})\\&={\begin{cases}<0,&{\text{wenn }}C{\text{ ist rechts von }}{\overrightarrow {AB}}\\=0,&{\text{wenn }}C{\text{ ist auf }}{\overrightarrow {AB}}\\>0,&{\text{wenn }}C{\text{ ist links von }}{\overrightarrow {AB}}\end{cases}}\end{aligned}}}$

calculation

Set of points sorted by angle - chosen as the starting point because it has the smallest ordinate value. falls out because it is with and collinear. ${\displaystyle P_{0}}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle P_{0}}$

${\displaystyle S}$now be the sorted set of points. Next you go through all the points in and check whether these are corner points of the convex hull. It is a stack applied (stack) on which all vertices are the convex hull for all points have already been processed. Are at the beginning and on the stack. In the -th step it is used to consider and calculate how it changes the previous convex hull. Because of the order is always the previous points outside of the envelope with . ${\displaystyle S}$ ${\displaystyle P_{0}}$ ${\displaystyle P_{1}}$ ${\displaystyle k}$ ${\displaystyle P_{k}}$ ${\displaystyle P_{k}}$ ${\displaystyle P_{i}}$ ${\displaystyle i<k}$

By adding the point, it can happen that points already on the stack no longer belong to the new convex envelope. These points must be removed from the stack using the "pop" operation. Whether a point still belongs to the convex envelope or not is determined by calculating whether it is to the left or right of the vector PT2 → PT1 (PT1 = top element of the stack, PT2 = element directly below PT1). If it is on the left, PT1 remains on the stack and is placed on the stack with "push" ; if it is on the right, PT1 is swallowed by the new convex shell, removed from the stack and the next two points above are examined. ${\displaystyle P_{k}}$ ${\displaystyle P_{k}}$ ${\displaystyle P_{k}}$ ${\displaystyle P_{k}}$

This test is carried out until the left of the vector PT2 → PT1 or only one more point is on the stack. In both cases it is then placed on the stack and the calculation continues with the next point . The following figure shows an example in which all cases of the test just described occur. ${\displaystyle P_{k}}$ ${\displaystyle P_{0}}$ ${\displaystyle P_{k}}$ ${\displaystyle P_{k+1}}$

Example - Graham Scan Algorithm

In the figure opposite, the points Pt4, Pt3, Pt2 and are first placed on the stack. At each point in time, the points on the stack form a convex polygon (dashed lines). Only when you want to add, drop and Pt2 out again, since they are not convex together with . The convex hull of this point set consists of , Pt4, Pt3 and . is at the bottom and at the top of the stack . The points of the convex polygon you are looking for can be fetched from the stack by turning clockwise with "pop". ${\displaystyle P_{k-1}}$ ${\displaystyle P_{k}}$ ${\displaystyle P_{k-1}}$ ${\displaystyle P_{k}}$ ${\displaystyle P_{0}}$ ${\displaystyle P_{k}}$ ${\displaystyle P_{0}}$ ${\displaystyle P_{k}}$

annotation

The number of "push" and "pop" operations does not exceed the upper limit of ( = number of points in the input set). So the calculation is . The sorting of the points by angle can be carried out with any sorting algorithm, e.g. B. Mergesort . This has an asymptotic running time of . This means that the running time of the algorithm is given by the sorting, since . ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n\log n)}$ ${\displaystyle {\mathcal {O}}(n)+{\mathcal {O}}(n\log n)={\mathcal {O}}(n\log n)}$

Pseudocode

Using a stack

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

Without using a stack

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

In the code is punktean array of points, from which you get punkte[i]the i-th element and which is already punkte[0]sorted according to the angle . The code changes this array by deleting the elements that do not belong to the convex hull.

Web links

• Explanations including visualization of the process
• Computational Geometry in C (Second Edition)
• Explanation and pseudocode