Gift Wrapping

From Algorithmist

Gift Wrapping is perhaps the simplest of the Convex Hull algorithms. Starting from the lowest, left-most point (this point has to be on the hull), "gift wrap" by choosing the next point such no points lie on the left of the line created by the current point and the next point. Repeat this until it wraps around back to the original point. The algorithm runs in O(nh) time, or O(n²) worst-case.

[edit] Pseudo-code

• p, current is a 2D point.
• point is an array containing the points.

p = left-most, bottom point
current = p
do {
    // Sentinel
    leftmost = 1
    for i from 2 to N
        // If line current->leftmost is to the left of current->point[i]
        if ( left( current, point[i], leftmost ) )
              leftmost = i
    // Output and move on.
    current = point[leftmost]
} while ( current != p )