Project Nayuki


Convex hull algorithm

Demo (JavaScript)

This JavaScript program computes the smallest convex polygon that encloses an arbitrary set of points in the plane. Points defining the convex hull are colored red; points in the interior are colored gray. Instructions for manual positioning mode:


Description

This library computes the convex hull polygon that encloses a collection of points on the plane. Andrew’s monotone chain algorithm is used, which runs in Θ(n log n) time in general, or Θ(n) time if the input is already sorted.

The code of the algorithm is available in multiple languages. The JavaScript version has a live demo that is shown at the top of the page.

Source code

Java (SE 7+)
JavaScript
Python (compatible with 2 and 3)
C++ (C++11 and above)
C# (.NET 4.0+)

License: GNU Lesser General Public License v3.0+