Overview
The convex hull of a set of points is the smallest convex set containing every point in that collection. In two-dimensional computational geometry, it is usually represented as a polygon whose vertices are selected from the input points. Points inside the hull are not required to appear as hull vertices.
How it works
Collect all input points.; Sort or select an initial extreme point, depending on the chosen algorithm.; Use orientation tests to determine whether candidate points belong on the outer boundary.; Remove points that would create an inward or incorrect turn.; Continue until the complete outer boundary is constructed.; Return the hull vertices in a consistent order.
Key concepts
Convex sets; Hull boundary; Extreme points; Orientation test; Cross product; Counterclockwise traversal
Time complexity
algorithm: Graham Scan; complexity: O(n log n); algorithm: Monotonic Chain; complexity: O(n log n); algorithm: Jarvis March; complexity: O(nh), where h is the number of hull vertices
Space complexity
O(n) for common implementations that store sorted points and the hull boundary.
Example
points: 0; 0; 2; 0; description: The points form a collection containing several boundary and interior points. The convex hull surrounds the entire collection while excluding interior points from its vertex list.; hullVertices: 0; 0; 4; 0
Applications
Computer graphics; Geographic data analysis; Collision detection; Pattern recognition; Robotics; Shape analysis