Convex hull algorithm

Demo (JavaScript)

Random static points Random moving points Manual positioning

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:

• Left-click in a blank space to add a new point

• Left-click an existing point and drag to move it

• Right-click 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)

TypeScript / JavaScript

• convex-hull.ts / convex-hull.js (computation functions)
• convex-hull-demo.ts / convex-hull-demo.js (the demo on this page)

Python

• convexhull.py (computation functions)
• convexhull-test.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+