Jarvis convex hull in the plane

The Jarvis march is one of the nicest to animate since it proceeds by wrapping a string around the point set. Running time is O(nh) if the input size is n and output size is h. See R. A. Jarvis, "On the identification of the convex hull of a finite set of points in the plane" Inform. Process. Lett., 2, 1973, 18--21.
( Graham & Yao's algorithm is faster, and easy if you have a sort routine.)

A variant deletes points found to be inside the convex hull so far. The extra test for containment means the improvement is not significant.

Code by Jack Snoeyink, University of British Columbia Back to Jack's Computational Geometry Demo page.