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.

• Detail toggles the vertex numbers and some of the edge weights.
• Animate toggles some animation of partial computation
• Update is the button you push when the input is ready; If comparing times, click twice because the first time may include loading or swapping time.
• Random generates 50 random points
• Clear All and Delete Last give minimalist editing.

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