Back

2d Convex Hull

Reset Mouse Mode: Drag Create Erase Movement Type: Frozen Slow Free Elastic Regenerate Hull

Given some set of points, a convex hull is the smallest convex polygon that contains all the points. In 2d, it is also known as the Gift wrapping/minimum enclosing fence problem. This program demonstrates an algorithm that finds the convex hull for n points in O(n log n) time. Click regenerate hull while in frozen mode to see it in action.

You can also add, remove, or drag points, and give then a random velocity. In Elastic mode, the hull tries to contract, applying a force like a real rubber band. This makes for some fun physics simulations involving pressure and temperature.