跳转至

旋轉卡殼

本頁面將主要介紹旋轉卡殼。

引入

旋轉卡殼（Rotating Calipers，也稱「旋轉卡尺」）算法，在凸包算法的基礎上，通過枚舉凸包上某一條邊的同時維護其他需要的點，能夠在線性時間內求解如凸包直徑、最小矩形覆蓋等和凸包性質相關的問題。

算法中文名稱

該算法比較常見的中文名是「旋轉卡殼」。可以理解為：根據我們枚舉的邊，可以從每個維護的點畫出一條或平行或垂直的直線，為了確保對於當前枚舉的邊的最優性，我們的任務就是使這些直線能將凸包正好卡住。而邊通常是按照向某一方向旋轉的順序來枚舉，所以整個過程就是在邊「旋轉」，邊「卡殼」。

其英文名「rotating calipers」的直譯應為「旋轉卡尺」，其中「calipers」的意思是「卡尺」。第一次提出該術語的論文1原意為：使用一個可動態調整的「卡尺」夾住凸包後，繞凸包「旋轉」該「卡尺」。

求凸包直徑

例題 1 :Luogu P1452 Beauty Contest G

給定平面上 \(n\) 個點，求所有點對之間的最長距離。（\(2\leq n \leq 50000,|x|,|y| \leq 10^4\)）

過程

首先使用任何一種凸包算法求出給定所有點的凸包，有着最長距離的點對一定在凸包上。而由於凸包的形狀，我們發現，逆時針地遍歷凸包上的邊，對於每條邊都找到離這條邊最遠的點，那麼這時隨着邊的轉動，對應的最遠點也在逆時針旋轉，不會有反向的情況，這意味着我們可以在逆時針枚舉凸包上的邊時，記錄並維護一個當前最遠點，並不斷計算、更新答案。

求出凸包後的數組自然地是按照逆時針旋轉的順序排列，不過要記得提前將最左下角的 1 節點補到數組最後，這樣在挨個枚舉邊 \((i,i+1)\) 時，才能把所有邊都枚舉到。

枚舉過程中，對於每條邊，都檢查 \(j+1\) 和邊 \((i,i+1)\) 的距離是不是比 \(j\) 更大，如果是就將 \(j\) 加一，否則説明 \(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
int sta[N], top;  // 將凸包上的節點編號存在棧裏，第一個和最後一個節點編號相同
bool is[N];

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() {  // 求凸包直徑
  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
sta = [0] * N; top = 0 # 將凸包上的節點編號存在棧裏，第一個和最後一個節點編號相同
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(): # 求凸包直徑
    j = 3
    if top < 4:
        mx = dis(sta[1], sta[2])
        return
    for i in range(1, top + 1):
        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])))

求最小矩形覆蓋

Luogu P3187 最小矩形覆蓋

給定一些點的座標，求能夠覆蓋所有點的最小面積的矩形。（\(3\leq n \leq 50000\)）

過程

有了上一道題做鋪墊，這道題比較直觀的想法仍然是使用旋轉卡殼法，不過這次要求的是面積，像上一題一樣只維護一個最優點就只能找到一對距離最小的平行線，我們還需要確定矩形的左右邊界。所以這次我們需要維護三個點：一個在所枚舉的直線對面的點、兩個在不同側面的點。對面的最優點仍然是用叉積算面積來比較，此時比較面積就是在比較這個矩形的一個邊長。側面的最優點則是用點積來比較，因為比較點積就是比較投影的長度，左右兩個投影長度相加可以代表這個矩形的另一個邊長。這兩個邊長的最優性相互獨立，因此找到三個最優點的位置就能夠確定以當前邊所在直線為矩陣的一條邊時，能覆蓋所有點的矩形最小面積。

最後統計答案時，如果題目沒有要求將四個頂點都求出來，其實有一種較為巧妙的利用叉積和點積的方式直接算出矩陣的面積。設紫色部分面積的兩倍為 \(S\)，最後的面積就是

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

實現

必要的求凸包過程略去，這裏貼出本題核心代碼：

核心代碼 
 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
def get_biggest():
    j = 3; l = 2; r = 2
    ans = 2e10
    for i in range(1, top + 1):
        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. 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 协议之条款下提供，附加条款亦可能应用