Gift wrapping algorithm

Animation of the gift wrapping algorithm. With different colored lines where it shows different angles, the color changes each time when it finishes finding the optimal point.

In computational geometry, the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points.

. Also, the complete implementation must choose how to 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 p0 known to be on the convex hull, e.g., the leftmost point, and selects the point pi+1 such that all points are to the right of the line pi pi+1. This point may be found in O(n) time by comparing polar angles of all points with respect to point pi taken for the center of polar coordinates. Letting i=i+1, and repeating with until one reaches ph=p0 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.

Jarvis's march computing the convex hull. algorithm jarvis(S) is // S is the set of points // P will be the set of points which form the convex hull. Final set size is i. pointOnHull := leftmost point in S // which is guaranteed to be part of the CH(S) i := 0 repeat P[i] := pointOnHull endpoint := S[0] // initial endpoint for a candidate edge on the hull for j from 0 to |S| do // endpoint == pointOnHull is a rare case and can happen only when j == 1 and a better endpoint has not yet been set for the loop if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint) then endpoint := S[j] // found greater left turn, update endpoint i := i + 1 pointOnHull := endpoint until endpoint == P[0] // wrapped around to first hull point

The inner loop checks every point in the set S, and the outer loop repeats for each point on the hull. Hence the total run time is