Overview
Rotating Calipers uses antipodal points on a convex hull to compute widths, diameters, and bounding rectangles efficiently.
ExtendedSource checked
Rotating Calipers
Solves convex polygon measurements by rotating supporting lines around the hull.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Advanced
- Family
- Convex Geometry
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 7
- Code example
- Ready
- Visualization
- Ready
Core Concepts
convex hullsupport lineantipodal pairangle sweep
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)
When to Use
- Use when an extremal measurement on a convex polygon is needed in linear time.
- Use when polygon diameter is a central requirement.
When Not to Use
- Avoid when the input is not convex and no hull has been computed.
- Avoid when floating-point precision or degenerate geometry cannot be handled robustly.
What It Does
- Works on a convex polygon
- Tracks antipodal points
- Rotates support directions
Use Cases
- Polygon diameter
- Minimum bounding rectangle
- Shape analysis
Inputs
- Convex polygon vertices in order
Outputs
- Extremal distances or bounding rectangle
Key Formulas (1)
Projected width
width(axis) = max(dot(point, axis)) − min(dot(point, axis))
width(axis) = max(dot(point, axis)) - min(dot(point, axis))Measures polygon extent along a caliper direction.
Pseudocode
- 1.Start with a convex polygon
- 2.Find an initial antipodal pair
- 3.Rotate support lines to the next polygon edge angle
- 4.Update antipodal points as needed
- 5.Record the best measurement
Canonical Example
- Input
- convex rectangle points
- Output
- minimum rectangle = same rectangle
- Explanation
- Calipers align with each edge and test candidate bounding boxes.
Implementation Notes
- Normalize the hull representation before running calipers.
- Use robust predicates or tolerances when near-degenerate inputs are expected.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Duplicate or collinear hull points can make angle advances ambiguous.
- Collinear, overlapping, and duplicate points need explicit tie-breaking rules.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow parallel caliper lines rotating around a convex hull and touching support points.
Step 1 of 5: Start with a convex polygon
geometry-diagramNotes
The input must already be a convex hull in cyclic order.
Sources (2)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookTextbook support for Rotating Calipers's computational geometry problem family, predicates, structures, or geometric construction.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Rotating Calipers in the computational geometry benchmark area.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byMinimum Bounding Rectangle
Geometry · Core
Minimum bounding rectangle algorithms often use rotating calipers.
Compare with thisDepends onConvex Hull
Geometry · Foundation
Rotating calipers commonly assumes a convex polygon or hull as input.
Compare with thisConceptual neighborsRotating Calipers Diameter
Geometry · Core
Both use rotating calipers ideas for related polygon diameter problems.
Compare with thisRelationships
View full relationship pageDepends onConvex Hull
Rotating calipers commonly assumes a convex polygon or hull as input.
Used byMinimum Bounding Rectangle
Minimum bounding rectangle algorithms often use rotating calipers.
Related Algorithms
Tags
GeometryComputational GeometryPolygons