Jarvis march

This online calculator implements the 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 the complexity of , 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 and , 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 the previous point taken for the center of polar coordinates. The point with minimum angle wins. The process continues until it returns to the starting point in h steps. The process is similar to 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 a semicolon. The calculator builds a convex hull, displays it as a set of points, and plots it.

Jarvis march

1.1;1.2 -2;4 -3;12 4;-16 12;8

Set of 2D points (one point per line, x and y separated by semicolon)

Calculate

Convex hull

 

 Link  Save  Widget