geometry.rotating_calipers

Rotating Calipers Algorithm for Convex Polygon Diameter.

References: - https://en.wikipedia.org/wiki/Rotating_calipers - https://cp-algorithms.com/geometry/convex-hull-kernel.html - Toussaint, G. T. (1983). “Solving geometric problems with the rotating calipers”.

Proceedings of IEEE MELECON ‘83, Athens, Greece.

The rotating calipers paradigm allows computing the diameter (the maximum Euclidean distance between any pair of points) of a set of 2D points in O(n log n) time (O(n log n) for the convex hull and O(n) for the calipers sweep).

Classes

Point

A 2D point with real-valued coordinates.

Functions

convex_hull(→ list[Point])

Compute the convex hull of a set of 2D points in counter-clockwise order

cross_product(→ float)

Compute the 2D cross product of vectors (origin -> point_a) and (origin -> point_b).

distance_squared(→ float)

Compute the squared Euclidean distance between point_a and point_b.

rotating_calipers(→ tuple[float, tuple[Point, Point]])

Find the maximum Euclidean distance (polygon diameter) and an antipodal pair

Module Contents

class geometry.rotating_calipers.Point

Bases: NamedTuple

A 2D point with real-valued coordinates.

>>> Point(0.0, 0.0)
Point(x=0.0, y=0.0)
>>> Point(1.5, -2.0)
Point(x=1.5, y=-2.0)
x: float
y: float
geometry.rotating_calipers.convex_hull(points: list[Point]) → list[Point]

Compute the convex hull of a set of 2D points in counter-clockwise order using Andrew’s monotone chain algorithm.

Time Complexity: O(n log n) where n is the number of points. Space Complexity: O(n)

>>> convex_hull([Point(0.0, 0.0), Point(1.0, 1.0)])
[Point(x=0.0, y=0.0), Point(x=1.0, y=1.0)]
>>> convex_hull([
...     Point(0.0, 0.0),
...     Point(3.0, 0.0),
...     Point(3.0, 3.0),
...     Point(0.0, 3.0),
...     Point(1.0, 1.0),
... ])
[Point(x=0.0, y=0.0), Point(x=3.0, y=0.0), Point(x=3.0, y=3.0), Point(x=0.0, y=3.0)]
>>> convex_hull([Point(0.0, 0.0), Point(1.0, 1.0), Point(2.0, 2.0)])
[Point(x=0.0, y=0.0), Point(x=2.0, y=2.0)]
>>> convex_hull([Point(1.0, 1.0)])
[Point(x=1.0, y=1.0)]
geometry.rotating_calipers.cross_product(origin: Point, point_a: Point, point_b: Point) → float

Compute the 2D cross product of vectors (origin -> point_a) and (origin -> point_b).

The return value represents twice the signed area of triangle (origin, point_a, point_b):

> 0 : Counter-clockwise turn (left turn) < 0 : Clockwise turn (right turn) = 0 : Collinear points

>>> cross_product(Point(0.0, 0.0), Point(1.0, 0.0), Point(1.0, 1.0))
1.0
>>> cross_product(Point(0.0, 0.0), Point(1.0, 1.0), Point(1.0, 0.0))
-1.0
>>> cross_product(Point(0.0, 0.0), Point(1.0, 1.0), Point(2.0, 2.0))
0.0
geometry.rotating_calipers.distance_squared(point_a: Point, point_b: Point) → float

Compute the squared Euclidean distance between point_a and point_b.

>>> distance_squared(Point(0.0, 0.0), Point(3.0, 4.0))
25.0
>>> distance_squared(Point(1.0, 1.0), Point(1.0, 1.0))
0.0
>>> distance_squared(Point(-1.0, -1.0), Point(2.0, 3.0))
25.0
geometry.rotating_calipers.rotating_calipers(points: list[Point]) → tuple[float, tuple[Point, Point]]

Find the maximum Euclidean distance (polygon diameter) and an antipodal pair of points for a given set of 2D points using the rotating calipers algorithm.

Time Complexity: O(n log n) for convex hull construction

  • O(n) for the calipers sweep.

Space Complexity: O(n) for the convex hull.

Raises:

ValueError: If fewer than 2 points are provided.

>>> points = [
...     Point(0.0, 0.0),
...     Point(3.0, 0.0),
...     Point(3.0, 4.0),
...     Point(0.0, 4.0),
... ]
>>> max_dist, pair = rotating_calipers(points)
>>> max_dist
5.0
>>> pair in [
...     (Point(0.0, 0.0), Point(3.0, 4.0)),
...     (Point(3.0, 4.0), Point(0.0, 0.0)),
...     (Point(3.0, 0.0), Point(0.0, 4.0)),
...     (Point(0.0, 4.0), Point(3.0, 0.0)),
... ]
True
>>> rotating_calipers([Point(0.0, 0.0), Point(0.0, 5.0)])
(5.0, (Point(x=0.0, y=0.0), Point(x=0.0, y=5.0)))
>>> rotating_calipers([Point(1.0, 1.0), Point(1.0, 1.0)])
(0.0, (Point(x=1.0, y=1.0), Point(x=1.0, y=1.0)))
>>> rotating_calipers([
...     Point(0.0, 0.0),
...     Point(1.0, 1.0),
...     Point(2.0, 2.0),
...     Point(3.0, 3.0),
... ])[0]
4.242640687119285
>>> rotating_calipers([Point(1.0, 1.0)])
Traceback (most recent call last):
    ...
ValueError: At least 2 points are required to compute polygon diameter.