Demo of Andrew's Convex Hull Algorithm

Part 1: User Interface

To clear canvas, click on "reset everything"
To add a vertex, left click on canvas.
To delete a vertex, right click on it.
To drag a vertex, left click on it, hold, and drag.
To restrict vertical/horizontal displacement, hold on SHIFT key while dragging a vertex.

Part 2: Polygon Creation Mode

To toggle polygon creation mode, click on "polygon mode". Note its status indicated in the status bar.
To close the polygon, click on "close polygon". Click on "polygon mode" to turn off the polygon again.
Vertices may be dragged and the polygon is updated in real time.

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:

Enable the "polygon mode" or "close mode" buttons to verify the shape of the polygon you're about to create.
Create a SIMPLE polygon (i.e. polygon without crossover edges) by creating vertices on the canvas in the CLOCKWISE direction. The algorithm currently assumes CLOCKWISE polygon representation. You can fail the algorithm by creating a polygon in the counterclockwise direction. Try it!
Click on "reset algorithm".
Toggle the "algorithm" button until "LINEAR" mode shows up in the status bar.
Choose whether you want to enable animation by toggling the "animate" button.
Click on "execute" or "suspend" to animate or step through the algorithm. You may disable animation mode any time.
Click on "reset algorithm" to run again.

Part 4: Demo of Andrew's Convex Hull Algorithm

Create desired vertices on the canvas in any order.
Click on "reset algorithm".
Toggle the "algorithm" button until "ANDREW" mode shows up in the status bar.
Choose whether you want to enable animation by toggling the "animate" button.
Click on "execute" or "suspend" to animate or step through the algorithm. You may disable animation mode any time.
Click on "reset algorithm" to run again.

Gzipped tar source code download