Overview
Convex hull algorithms wrap a point set with an outer polygon that has no inward dents.
FoundationSource checked
Convex Hull
Finds the smallest convex boundary that contains a set of points.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Intermediate
- Family
- Computational Geometry
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 21
- Code example
- Not ready
- Visualization
- Ready
- Aliases
- Convex Envelope
Core Concepts
boundary pointsorientation testextreme pointpolygon envelopegeometric calculationgeometric predicatepolygon boundarycomputational geometry
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)
When to Use
- Use it to find the outer boundary of a planar point set.
- Use it for geometric preprocessing, collision bounds, or shape summaries.
- Use robust predicates when inputs may be nearly collinear.
When Not to Use
- Avoid it when interior structure or concave boundary detail is required.
- Avoid naive floating-point orientation tests for degenerate inputs.
- Avoid assuming every boundary convention treats collinear points the same way.
What It Does
- Identifies boundary points
- Builds an enclosing convex polygon
Use Cases
- Collision bounds
- Geographic envelopes
- Shape simplification
Inputs
- Set of points
Outputs
- Convex hull vertices
Key Formulas (1)
Orientation test
orientation(a, b, c) = sign(cross(b − a, c − a))
orientation(a, b, c) = sign(cross(b - a, c - a))Determines whether three points make a left turn, right turn, or straight line.
Pseudocode
- 1.Find points on the outer boundary
- 2.Order boundary points around the shape
- 3.Remove turns that bend inward
- 4.Return the remaining boundary polygon
Canonical Example
- Input
- points = [(0,0), (1,0), (0,1), (0.2,0.2)]
- Output
- [(0,0), (1,0), (0,1)]
- Explanation
- The point (0.2,0.2) lies inside the triangle formed by the other three points.
Implementation Notes
- Sort points consistently if using monotone chain or Graham scan.
- Decide whether collinear boundary points should be included.
- Use orientation tests as the core turn predicate.
Common Pitfalls
- Mishandling duplicate or collinear points.
- Returning hull points in inconsistent clockwise or counterclockwise order.
- Using non-robust orientation predicates on nearly collinear coordinates.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow a boundary tightening around the outside of a point cloud.
Step 1 of 4: Find points on the outer boundary
point-wrapNotes
Convex hull output conventions vary, especially for collinear boundary points.
Sources (1)
What each reference supports for this entry.
Computational Geometry
BookComputational geometry reference for convex hulls, point location, triangulations, and geometric predicates.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
UsesOrientation Test
Geometry · Foundation
Convex hull algorithms use orientation tests to keep or remove candidate turns.
Compare with thisOften paired withRotating Calipers
Geometry · Extended
Rotating calipers often operates on a convex hull.
Compare with thisDependentsMinimum Bounding Rectangle
Geometry · Core
The minimum rectangle can be found from the convex hull rather than all points.
Compare with thisDependentsMinkowski Sum
Geometry · Extended
Minkowski operations often use convex polygon or polytope structure.
Compare with thisRelationships
View full relationship pageGeneralizesGraham Scan
Graham Scan is one algorithm for computing a convex hull.
GeneralizesJarvis March
Jarvis March is one algorithm for computing a convex hull.
GeneralizesQuickhull
Quickhull is one algorithm for computing a convex hull.
Often paired withRotating Calipers
Rotating calipers often operates on a convex hull.
Related Algorithms
Tags
GeometryComputational GeometryPolygons