Graham scan
From Wikipedia, the free encyclopedia
The Graham scan is a method of computing the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972[1]. The algorithm finds all vertices of the convex hull ordered along its boundary. It may also be easily modified to report all input points that lie on the boundary of their convex hull.
Contents |
[edit] Algorithm
The first step in this algorithm is to find the point with the lowest y-coordinate. If there is a tie, the point with the lowest x-coordinate out of the tie breaking candidates should be chosen. Call this point P. This step takes O(n), where n is the number of points in question.
Next, the set of points must be sorted in increasing order of the angle they and the point P make with the x-axis. Any general-purpose sorting algorithm is appropriate for this, for example heapsort (which is O(n log n)). In order to speed up the calculations, it is not actually necessary to calculate the actual angle these points make with the x-axis; instead, it suffices to calculate the cotangent of this angle: it is a monotonically decreasing function in the domain in question (which is 0 to 180 degrees, due to the first step) and may be calculated with simple arithmetic.
The algorithm proceeds by considering each of the points in the sorted array in sequence. For each point, it is determined whether moving from the two previously considered points to this point is a "left turn" or a "right turn". If it is a "right turn", this means that the second-to-last point is not part of the convex hull and should be removed from consideration. This process is continued for as long as the set of the last three points is a "right turn". As soon as a "left turn" is encountered, the algorithm moves on to the next point in the sorted array. (If at any stage the three points are collinear, one may opt either to discard or to report it, since in some applications it is required to find all points on the boundary of the convex hull.)
Again, determining whether three points constitute a "left turn" or a "right turn" does not require computing the actual angle between the two line segments, and can actually be achieved with simple arithmetic only. For three points (x1,y1), (x2,y2) and (x3,y3), simply compute the direction of the cross product of the two vectors defined by points (x1,y1), (x2,y2) and (x1,y1), (x3,y3), characterized by the sign of the expression (x2 − x1)(y3 − y1) − (y2 − y1)(x3 − x1). If the result is 0, the points are collinear; if it is positive, the three points constitute a "left turn", otherwise a "right turn".
This process will eventually return to the point at which it started, at which point the algorithm is completed and the stack now contains the points on the convex hull in counterclockwise order.
[edit] Time complexity
Sorting the points has time complexity O(n log n). While it may seem that the time complexity of the loop is O(n2), because for each point it goes back to check if any of the previous points make a "right turn", it is actually O(n), because each point is considered only once. Each point considered either terminates the inner loop, or it is removed from the array and thus never considered again. The overall time complexity is therefore O(n log n), since the time to sort dominates the time to actually compute the convex hull.
[edit] Pseudocode
The result will be stored on Stack.
Find pivot P;
Sort Points by angle (with points with equal angle further sorted by distance from P);
# Points[1] is the pivot
Stack.push(Points[1]);
Stack.push(Points[2]);
FOR i = 3 TO Points.length
WHILE (Stack.length >= 2) and (Cross_product(Stack.second, Stack.top, Points[i]) <= 0)
Stack.pop;
ENDWHILE
Stack.push(Points[i]);
NEXT i
FUNCTION Cross_product(p1, p2, p3)
RETURN (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);
ENDFUNCTION
Note 1: it may be necessary to check whether the last point added to the stack (stack.Top) does not fall inside the hull by comparing it to the next-to-last point (stack.Second) and to the point at the bottom of the stack.
Note 2: to handle the degenerate case of resulting hulls that have less than three points, only one point should be pushed onto the stack to start and if the stack ever has less than two (it will always have at least one) points on it then top should also be popped if the new point is equal to it. In other words the while condition should be
Stack.length >= 2 ? Cross_Product(Stack.second, Stack.top, Points[i]) <= 0 : Stack.top == Points[i]
[edit] Notes
The same basic idea works also if the input is sorted on x-coordinate instead of angle, and the hull is computed in two steps producing the upper and the lower parts of the hull respectively.
The stack technique used in the Graham scan algorithm is very similar to that for the all nearest smaller values problem, and parallel algorithms for all nearest smaller values may also be used (like the Graham scan) to compute convex hulls of sorted sequences of points efficiently.[2]
[edit] References
- ^ Graham, R.L. (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133
- ^ Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), "Optimal double logarithmic parallel algorithms based on finding all nearest smaller values", Journal of Algorithms 14 (3): 344–370, doi:.
- Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001) [1990]. "33.3: Finding the convex hull". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. pp. 949–955. ISBN 0-262-03293-7.
