Jarvis march
This online calculator computes the convex hull of a given set of points using Jarvis march algorithm, aka Gift wrapping algorithm
This page exists due to the efforts of the following people:
 | Timur
|
This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/8576/. Also, please do not modify any references to the original work (if any) contained in this content.
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.
Comments