Demo of Andrew's Convex Hull Algorithm

Part 1: User Interface

Part 2: Polygon Creation Mode

Part 3: Linear Convex Hull Algorithm for Simple Polygons

A linear time convex hull algorithm for simple polygons exists because the data representation of a polygon already imposes a certain ordering of the vertices. That is, the polygon is given as either a clockwise or counter-clockwise chain of vertices.

Given this observation, we can pretty much apply Andrew's sweeping algorithm. We scan the vertex list as in Andrew's algorithm, using the order given by the polygon chain. Then apply the "RightOf()" or "LeftOf()" test, depending if the polygon is clockwise or a counter-clockwise, to the last three vertices in the chain. When the RightOf() (or LeftOf()) test fails, then we keep popping the second last vertex until the test succeeds again. When the last vertex is reached, join it with the first vertex.

Because we skipped the sorting step, the algorithm runs in linear time. Note that the RightOf() (or LeftOf()) test is exactly the same as the one used in Andrew's algorithm. That is, we do the cross product of the two vectors; one extending from the 3rd last vertex to the 2nd last vertex, and the other extending from the 2nd last vertex to the last vertex. The collinear case is handled the same as Andrew's algorithm would. That is, it may include a near collinear vertex that makes the resulting convex hull polygon concave.

Intuitively, this algorithm works because the RightOf() (or LeftOf()) tests maintain the convexity of the convex hull chain. The other case to worry about is that the chain is loop-free. For example, a right-turning loop would statisfy the RightOf() test from the beginning to the end of the algorithm. But this can only happen when the algorithm visits a vertex out of (clockwise or counter-clockwise) order.

To test this on the applet, please do the following:

Part 4: Demo of Andrew's Convex Hull Algorithm

Gzipped tar source code download