homechevron_rightLifechevron_rightDate and Time

Jarvis march

This online calculator computes the convex hull of a given set of points using Jarvis march algorithm, aka Gift wrapping algorithm

This online calculator implements Jarvis march algorithm, introduced by R. A. Jarvis in 1973 (also known as gift wrapping algorithm), to compute the convex hull of a given set of 2d points. It has complexity of O ( n h ), where n is the number of points and h is the number of hull vertices, so, it is output-sensitive algorithm. There are other algorithms with complexity of O ( n \log n ) and O ( n \log h ), but Jarvis march is very simple to implement.

The algorithm begins with a point known to be on the convex hull, f.e., the leftmost point, and selects the next point by comparing polar angles of all points with respect to previous point taken for the center of polar coordinates. The point with minimum angle wins. The process continues until it returns back to starting point in h steps. The process is similar to the winding a string (or wrapping paper) around the set of points, hence the name gift wrapping algorithm.

Enter the set of points into the calculator below - one point per line, with x and y coordinates separated by semicolon. The calculator builds convex hull, displays it as set of points and also plots it on the chart.

PLANETCALC, Jarvis march

Jarvis march

Convex hull
 

Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Jarvis march

Comments