Gift Wrapping Algorithm - Algorithm

Algorithm

For the sake of simplicity, the description below assumes that the points are in general position, i.e., no three points are collinear. The algorithm may be easily modified to deal with collinearity, including the choice whether it should report only extreme points (vertices of the convex hull) or all points that lie on the convex hull. Also, the complete implementation must deal with degenerate cases when the convex hull has only 1 or 2 vertices, as well as with the issues of limited arithmetic precision, both of computer computations and input data.

The gift wrapping algorithm begins with i=0 and a point p₀ known to be on the convex hull, e.g., the leftmost point, and selects the point p_i+1 such that all points are to the right of the line p_i p_i+1. This point may be found in O(n) time by comparing polar angles of all points with respect to point p_i taken for the center of polar coordinates. Letting i=i+1, and repeating with until one reaches p_h=p₀ again yields the convex hull in h steps. In two dimensions, the gift wrapping algorithm is similar to the process of winding a string (or wrapping paper) around the set of points.

The approach can be extended to higher dimensions.