AIOJ

This page mainly introduces rotating calipers.

Introduction

The Rotating Calipers algorithm, also called “rotating calipers”, builds on the convex-hull algorithm. By enumerating an edge of the convex hull while maintaining other required points, it solves convex-hull problems such as the diameter of a convex hull and the minimum enclosing rectangle in linear time.

Chinese Name

The common Chinese name for this algorithm is “rotating calipers”. The idea is that, for the edge being enumerated, one can draw a line parallel or perpendicular to it through each maintained point. To preserve optimality for the current edge, these lines must clamp the convex hull exactly. Since edges are usually enumerated in the order of rotation in one direction, the whole process consists of rotating the edge while clamping the hull.

The literal translation of “rotating calipers” into Chinese is “rotating measuring calipers”; “calipers” means a pair of calipers. The paper that first introduced the term¹ described using dynamically adjustable calipers to clamp the convex hull and “rotate” the calipers around it.

Finding the Diameter of a Convex Hull

Example 1: Luogu P1452 Beauty Contest G

Given $n$ points in the plane, find the maximum distance between any pair of points. ( $2\leq n \leq 50000,|x|,|y| \leq 10^4$ )

Process

First compute the convex hull of all given points using any convex-hull algorithm. A pair with maximum distance must lie on the convex hull. Because of the shape of a convex hull, when traversing its edges counterclockwise and finding the farthest point from each edge, the corresponding farthest point also rotates counterclockwise as the edge rotates; it never reverses direction. Thus, while enumerating the hull edges counterclockwise, maintain the current farthest point and continually compute and update the answer.

The resulting convex-hull array is naturally ordered counterclockwise. Remember to append the leftmost-bottom point to the end of the array so that, when enumerating edges $(i,i+1)$ one by one, every edge is included.

During enumeration, for each edge, check whether the distance from $j+1$ to edge $(i,i+1)$ is greater than the distance from $j$ . If so, increment $j$ ; otherwise, $j$ is the optimal point for this edge. The distances from a point to an edge can be compared directly by using cross products to compute the areas of two triangles with the same base, as shown by the yellow and blue triangles in the figure.

Implementation

Core Code

C++

int sta[N], top;  // stack of convex-hull vertex numbers; first and last numbers are equal

ll pf(ll x) { return x * x; }

ll dis(int p, int q) { return pf(a[p].x - a[q].x) + pf(a[p].y - a[q].y); }

ll sqr(int p, int q, int y) { return abs((a[q] - a[p]) * (a[y] - a[q])); }

ll mx;

void get_longest() {  // find the diameter of the convex hull
  int j = 3;
  if (top < 4) {
    mx = dis(sta[1], sta[2]);
    return;
  }
  for (int i = 1; i < top; ++i) {
    while (sqr(sta[i], sta[i + 1], sta[j]) <=
           sqr(sta[i], sta[i + 1], sta[j % top + 1]))
      j = j % top + 1;
    mx = max(mx, max(dis(sta[i + 1], sta[j]), dis(sta[i], sta[j])));
  }
}

Python

sta = [0] * N
top = 0  # stack of convex-hull vertex numbers; first and last numbers are equal


def pf(x):
    return x * x


def dis(p, q):
    return pf(a[p].x - a[q].x) + pf(a[p].y - a[q].y)


def sqr(p, q, y):
    return abs((a[q] - a[p]) * (a[y] - a[q]))


def get_longest():  # find the diameter of the convex hull
    j = 3
    if top < 4:
        mx = dis(sta[1], sta[2])
        return
    for i in range(1, top):
        while sqr(sta[i], sta[i + 1], sta[j]) <= sqr(
            sta[i], sta[i + 1], sta[j % top + 1]
        ):
            j = j % top + 1
        mx = max(mx, max(dis(sta[i + 1], sta[j]), dis(sta[i], sta[j])))

Finding the Minimum Enclosing Rectangle

Luogu P3187 Minimum Enclosing Rectangle

Given the coordinates of several points, find the minimum-area rectangle covering all of them. ( $3\leq n \leq 50000$ )

Process

As in the previous problem, the natural idea is still to use rotating calipers. This time we need area. Maintaining only one optimal point finds only a pair of closest parallel lines; we must also determine the left and right boundaries. Maintain three points: one opposite the enumerated line, and two on opposite sides. The opposite point is optimized by comparing cross-product areas; this compares one side length of the rectangle. The side points are optimized with dot products, which compare projection lengths; the sum of the two projections represents the other side length. The two side lengths are optimized independently, so the positions of the three optimal points determine the minimum-area rectangle covering all points when the current line is one of its sides.

When computing the final answer, if the four vertices are not required, a clever combination of cross products and dot products gives the area directly. Let twice the purple area be $S$ . The final area is

S\times (|\overrightarrow{AD}\cdot \overrightarrow{AB}|+|\overrightarrow{BC}\cdot \overrightarrow{BA}|-|\overrightarrow{AB}\cdot \overrightarrow{BA}|)/|\overrightarrow{AB}\cdot \overrightarrow{BA}|

Implementation

The necessary convex-hull construction is omitted; the core code is:

Core Code

C++

void get_biggest() {
  int j = 3, l = 2, r = 2;
  double t1, t2, t3, ans = 2e10;
  for (int i = 1; i < top; ++i) {
    while (sqr(sta[i], sta[i + 1], sta[j]) <=
           sqr(sta[i], sta[i + 1], sta[j % top + 1]))
      j = j % top + 1;
    while (dot(sta[i + 1], sta[r % top + 1], sta[i]) >=
           dot(sta[i + 1], sta[r], sta[i]))
      r = r % top + 1;
    if (i == 1) l = r;
    while (dot(sta[i + 1], sta[l % top + 1], sta[i]) <=
           dot(sta[i + 1], sta[l], sta[i]))
      l = l % top + 1;
    t1 = sqr(sta[i], sta[i + 1], sta[j]);
    t2 = dot(sta[i + 1], sta[r], sta[i]) + dot(sta[i + 1], sta[l], sta[i]);
    t3 = dot(sta[i + 1], sta[i + 1], sta[i]);
    ans = min(ans, t1 * t2 / t3);
  }
}

Python

def get_biggest():
    j = 3
    l = 2
    r = 2
    ans = 2e10
    for i in range(1, top):
        while sqr(sta[i], sta[i + 1], sta[j]) <= sqr(
            sta[i], sta[i + 1], sta[j % top + 1]
        ):
            j = j % top + 1
        while dot(sta[i + 1], sta[r % top + 1], sta[i]) >= dot(
            sta[i + 1], sta[r], sta[i]
        ):
            r = r % top + 1
        if i == 1:
            l = r
        while dot(sta[i + 1], sta[l % top + 1], sta[i]) <= dot(
            sta[i + 1], sta[l], sta[i]
        ):
            l = l % top + 1
        t1 = sqr(sta[i], sta[i + 1], sta[j])
        t2 = dot(sta[i + 1], sta[r], sta[i]) + dot(sta[i + 1], sta[l], sta[i])
        t3 = dot(sta[i + 1], sta[i + 1], sta[i])
        ans = min(ans, t1 * t2 / t3)

Exercises

References and notes

https://en.wikipedia.org/wiki/Rotating_calipers
http://www-cgrl.cs.mcgill.ca/~godfried/research/calipers.html
Shamos, Michael (1978). "Computational Geometry" (PDF). Yale University. pp. 76–81.

Footnotes

Toussaint, Godfried T. (1983). "Solving geometric problems with the rotating calipers". Proc. MELECON '83, Athens. CiteSeerX 10.1.1.155.5671 ↩