Graham Scan Tutorial: Convex Hull of a Set of 2D Points

Рет қаралды 9,415

Күн бұрын

Let's talk about the Convex Hull! interactive online code at demonstrations....
In geometry, the convex hull of a set of points is the smallest convex set that contains them. You can also define the convex hull as the intersection of all convex sets containing a given subset of a Euclidean space.
An equivalent definition is the set of all convex combinations of points in the subset. I like to visualize the convex hull as the shape enclosed by a rubber band stretched around the set.
In 1972 Ronald Graham published a delightful paper "An Efficient Algorithm for Determining the Convex Hull of a finite planar set". The paper is just one and half pages long, but it gives an algorithm with time complexity O(n log n) for n points. www.math.ucsd.e...
The first step is to find the point with the lowest y coordinate. This is the starting point of the convex hull. (If more than one point has this y coordinate, the rightmost one is used). Second, all the remaining points are sorted by polar angle to the starting point. This can be accomplished without trigonometry by using the reciprocal of the slope (-run/rise), and using negative infinity if the points have the same y coordinate. Call this list sortedPoints.
The algorithm then considers each sorted point in sequence, which can be animated by moving the slider step. We maintain a stack called the convexHullPts that is initialized with the starting point and the first sorted point. For every additional point in sortedPoints, we calculate if connecting to this point from the convexHullPts required a left turn or a right turn. If a right turn was required, we pop points off the stack convexHullPts until connecting to the current point in sortedPoints requires a left turn (the removed lines from convexHullPts are drawn as dashed red lines). We then add this point to convexHullPts, and repeat until we have stepped through all the points in sortedPoints.
The code is pleasantly simple, and you can see the stack operations for stepping through the sorted points here.
The function isLeftTurn[] returns the signed area of triangle defined by the points p, q, r. If this area is positive, then going from pq to qr is a left turn. If the area is negative, it is a right turn. The area computation is the determinant of a 3x3 matrix, and so requires no trigonometric functions.
Photo of Ronald Graham (1935--2020) by Cheryl Graham, CC BY 3.0 creativecommon..., via Wikimedia Commons
Full Playlist "Intro to Robotics": • Intro2Robotics Lecture...