Gift wrapping algorithm
From Wikipedia, the free encyclopedia
The gift wrapping algorithm is a simple algorithm for computing the convex hull of a given set of points.
Contents |
[edit] Planar case
In the two-dimensional case the algorithm is also known as Jarvis march, after R. A. Jarvis, who published it in 1973; it has O(nh) time complexity, where n is the number of points and h is the number of points on the convex hull. Its real-life performance compared with other convex hull algorithms is favorable when n is small or h is expected to be very small with respect to n. In general cases the algorithm is outperformed by many others.
[edit] 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 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 on O(n) time by comparing polar angles of all points with respect to point p0 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. The gift wrapping algorithm is exactly analogous to the process of winding a string (or wrapping paper) around the set of points.
def jarvis(P)
i = 0
p[0] = leftmost point of P
do
p[i+1] = point such that all other points in P are to the
right of the line p[i]p[i+1]
i = i + 1
while p[i] != p[0]
return p
The approach is extendable to higher dimensions.
[edit] References
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 955–956 of section 33.3: Finding the convex hull.
- Jarvis, R. A. (1973). "On the identification of the convex hull of a finite set of points in the plane". Information Processing Letters 2: 18–21.
