Melkman 1987

Best algorithm

Melkman's algorithm [19] is considered to be the best convex hull algorithm for simple polygons. What distinguishes it from all the rest is that it is actually an on-line algorithm. It computes the hull as points are being entered (notice that all other algorithms require finding an extreme point first). This means that the ordering of vertices (CW or CCW) does not need to be known either. The algorithm is only a few lines long, and his entire article is printed on two sides of a single page. Melkman uses the same logic as Lee, Graham and Yao (and others), i.e. he partitions the plane into regions that the next vertex could be. The difference is that he allows vertices to be removed on both sides of the forming chain. Melkman acknowledges that a similar approach to his was taken independently by Tor and Middleditch [22], who were working on the convex decomposition of a simple polygon.

Very informally, here's what the algorithm does:

It takes the first three vertices (starting anywhere) and sets up the current convex hull, i.e. the triangle formed. In the picture below, they happen to form a right turn (clockwise). Vertices are stored in a double ended queue (deque) : (bottom) 3-1-2-3 (top). Notice that if we take the last three vertices of the bottom in the order 2,1,3 we get a couterclockwise turn. If we take the last three vertices from the top, in the order 1,2,3 we get a clockwise turn. This is a property that we with to maintain.

Now the next vertex, V, could be in the red/green/blue/yellow regions.

If yellow, ignore V and all following vertices until one emerges into the other regions. If not yellow, we plan to add V to the deque. So we must ensure that we preserve our clockwise/counterclockwise property if this is to be done:

If red, backtrack/delete vertices from the top of the deque (i.e. 3, then maybe 2, etc), until a clockwise turn is encountered.

If green, backtrack/delete vertices from the bottom of the deque (i.e. 3, then maybe 1, etc), until a counterclockwise turn is encountered.

If blue, follow the instructions for red and green.

Insert V on both sides of the deque.

Now get another point and repeat.

The figure below shows these regions in a more general case. Vertices on the hull have circles on them. (N) is the last vertex added. The next vertex could be anywhere in the colored regions.

Check out Pierre Lang's project (including an applet) on Melkman's algorithm. To enter a simple polygon in his applet, make sure that the line between the yellow dot and the mouse tip does not intersect any of the lines already drawn, except the line segment between the yellow and orange dots. In other words, imagine that this segment doesn't exist.