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:
Leftclick in a blank space to add a new point
Leftclick an existing point and drag to move it
Rightclick an existing point to delete it
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+)

 ConvexHull.java (computation functions)
 ConvexHullTest.java (JUnit test suite)
 JavaScript

 convexhull.js (computation functions)
 convexhulldemo.js (the demo on this page)
 TypeScript

 convexhull.ts (computation functions)
The public API is identical to the handwritten JavaScript version.
 convexhull.ts (computation functions)
 Python (compatible with 2 and 3)

 convexhull.py (computation functions)
 convexhulltest.py (test suite)
 C++ (C++11 and above)

 ConvexHull.cpp (computation functions)
 ConvexHull.hpp (header file)
 ConvexHullTest.cpp (test suite)
 C# (.NET 4.0+)

 ConvexHull.cs (computation functions)
 ConvexHullTest.cs (test suite)
License: GNU Lesser General Public License v3.0+