Skip to content

Rotating Calipers

This page will primarily introduce the Rotating Calipers algorithm.

Introduction

The Rotating Calipers algorithm builds upon convex hull algorithms. By enumerating one edge of the convex hull while maintaining other necessary points, it can solve problems related to convex hull properties—such as the diameter of the convex hull and the minimum area rectangle covering—in linear time.

Chinese Name of the Algorithm

The most common Chinese name for this algorithm is "旋转卡壳" (Rotating Calipers). It can be understood as: based on the edge we enumerate, we can draw lines from each maintained point that are either parallel or perpendicular to that edge. To ensure optimality for the current edge, our task is to make these lines just "clamp" the convex hull. Since edges are usually enumerated in order of rotation in a certain direction, the whole process involves "rotating" the edges while "clamping" the hull.

The literal translation of its English name "rotating calipers" should be "旋转卡尺", where "calipers" means "卡尺". The original meaning in the first paper proposing this term1 was: using a dynamically adjustable "caliper" to clamp the convex hull, then "rotating" this "caliper" around the convex hull.

Finding the Diameter of a Convex Hull

Example 1 :Luogu P1452 Beauty Contest G

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

Process

First, use any convex hull algorithm to compute the convex hull of all given points. The pair of points with the maximum distance must lie on the convex hull. Due to the shape of the convex hull, we observe that when traversing the edges of the convex hull counterclockwise, for each edge, if we find the point farthest from that edge, then as the edge rotates, the corresponding farthest point also rotates counterclockwise without reversing direction. This means that while enumerating the edges of the convex hull counterclockwise, we can record and maintain a current farthest point, continuously computing and updating the answer.

After computing the convex hull, the array naturally follows a counterclockwise order. However, remember to append the leftmost-bottommost point (node 1) to the end of the array in advance. This ensures that when enumerating edges \((i,i+1)\) one by one, all edges are covered.

During enumeration, for each edge, check whether the distance from \(j+1\) to edge \((i,i+1)\) is greater than that from \(j\). If so, increment \(j\) by one; otherwise, \(j\) is the optimal point for this edge. When comparing distances from a point to an edge, we can use the cross product to compute the areas of two triangles (as shown in the figure, the yellow and blue triangles sharing the same base) and compare them directly.

Implementation

Core Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int sta[N], top;  // Store the indices of convex hull vertices on a stack; the first and last indices are the same

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() {  // Compute 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])));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
sta = [0] * N
top = 0  # Store the indices of convex hull vertices on a stack; the first and last indices are the same


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():  # Compute 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 Area Rectangle Covering

Luogu P3187 Minimum Rectangle Covering

Given the coordinates of some points, find the rectangle with the minimum area that can cover all points. (\(3\leq n \leq 50000\))

Process

Building on the previous problem, an intuitive approach for this problem is still to use the Rotating Calipers method. However, this time we are dealing with area. Maintaining only one optimal point as in the previous problem would only find a pair of parallel lines with the minimum distance; we also need to determine the left and right boundaries of the rectangle. Therefore, this time we need to maintain three points: one point opposite the enumerated line, and two points on different sides. The optimal opposite point is still compared using the cross product to compute area; comparing areas here is equivalent to comparing one side length of the rectangle. The optimal side points are compared using the dot product, because comparing dot products compares the projection lengths. The sum of the left and right projection lengths represents the other side length of the rectangle. The optimality of these two side lengths is independent, so finding the positions of the three optimal points determines the minimum area rectangle that can cover all points when the current edge is used as one side of the rectangle.

When finally computing the answer, if the problem does not require outputting all four vertices, there is a clever way to directly compute the rectangle's area using cross and dot products. Let twice the area of the purple region 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 computation is omitted here. Below is the core code for this problem:

Core Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)

Practice Problems

References and Notes

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

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用