concept · minimum-area enclosing rectangle

怎么用「最小的矩形」框住一堆点？（允许旋转的外接矩形）

检测算法在图里圈出了一个倾斜的物体（一行斜排的文字、一颗倒着的螺丝、一块歪放的零件），现在要用一个矩形把它恰好框住。最省事的做法是取所有点的 x、y 极值，画一个横平竖直的框——这就是轴对齐包围盒 (AABB)。但物体一旦倾斜，AABB 就会松垮地多框进大片空白。如果允许矩形旋转，就能找到一个真正贴合物体、面积最小的框——这就是最小外接矩形 (oriented bounding box, OBB),OpenCV 里的 cv2.minAreaRect 算的正是它。下面拖动这堆点，实时对比两种框，并单步看「让矩形的一条边贴着凸包逐条边旋转」是怎么试出最小的那个。

在画布里拖动任意点改变点集。用**「下一条边 ›」让候选矩形的一条边依次贴着凸包的每条边，看面积怎么随朝向变化；「显示 AABB」叠上轴对齐包围盒作对照。右下角实时报出最小矩形面积 vs AABB 面积**，以及省下了多少。

1 · 一、为什么不直接用「上下左右的极值」(AABB)?

轴对齐包围盒便宜得不能再便宜：扫一遍点，记下 x、y 各自的最小 / 最大值， $O(n)$ 出框，还天生对齐坐标轴，做空间索引（网格、四叉树）极方便。代价是它不会转：当物体本身斜着摆，AABB 为了把斜对角的两端都框进来，会在四个角留下大片空白。

把上面的点集切到**「细长斜带」那组看得最清楚：一条 45° 左右的细长点带，AABB 几乎是个大正方形（面积里九成是空白），而允许旋转的最小矩形是一条贴着点带**的细条——右下角的「省下」能到 90%。物体越细长、越斜，两者差距越夸张；只有当物体本就横平竖直时（切到「近似正放」那组）,OBB 才退化得和 AABB 几乎一样大。

2 · 二、关键定理：最小矩形必有一条边贴着凸包

允许任意旋转，朝向是连续的无穷多种，怎么可能逐一试过？救命的是一条定理 (Freeman & Shamos, 1975):点集的最小外接矩形，必有一条边与其凸包的某一条边共线。直觉上，如果矩形哪条边都没贴着凸包，就总能把它再转一点、压一点、让面积更小——不是最小。于是无穷的朝向被收敛成有限的候选：凸包有几条边，就只有几个朝向值得试。

每个候选怎么量？ 选定一条凸包边的方向 u，连同它的法向 n 组成一对新坐标轴；把全部凸包顶点投影到 u、n 上，各取 min / max，就得到这个朝向下恰好框住所有点的矩形，边长 = 两个方向上的跨度，面积 = 二者相乘。把每条凸包边都这样量一遍，面积最小的那个就是答案。所以第一步永远是先求凸包（本页用叉积定向驱动的 Andrew's monotone chain），内部的点对结果毫无影响，只有外轮廓的边定义了候选朝向。

单步时会发现：互相平行的两条凸包边给出同一个矩形（朝向相差 180° 等价），所以候选里常出现成对重复的面积。另外别把它和「最小周长矩形」「最小外接圆」混为一谈——那是不同的目标，最小面积矩形只保证面积最小。

3 · 三、从 O(h²) 到 O(h)：旋转卡壳 (rotating calipers)

本页为了看清「面积随朝向变化」，每换一条边都把全部凸包顶点重投影一遍——凸包有 h 个顶点就是 $O(h^2)$ 。工程上有更快的做法：rotating calipers（旋转卡壳）。想象给凸包套上一对互相垂直的「卡尺」，贴着边界一点点旋转；转动时四个方向上的极值顶点只会沿凸包单调地往前挪，不必每次从头扫——整趟下来每个顶点只被经过常数次，降到 $O(h)$ 。加上求凸包的 $O(n \log n)$ ，总复杂度就是 $O(n \log n)$ 。

旋转卡壳是一类通用技巧，同一副「卡尺」转一圈，顺带还能求出凸包的直径（最远点对）、宽度（最小厚度）、两个凸多边形的最近 / 最远距离等。最小外接矩形只是它最常被提起的应用之一。

4 · 四、它用在哪里

OCR / 文本检测：一行斜排的文字，检测网络输出的是一堆前景像素，要回归出一个带角度的矩形框 (rotated bounding box) 才能正确裁切、摆正后送去识别——cv2.minAreaRect 就是干这个的。物体检测：遥感、文档、车牌等场景里的旋转框 (oriented bounding box) 比正框贴得更紧、重叠更少。碰撞检测 / 物理：给斜放的刚体配一个 OBB，比 AABB 框得紧，粗筛 (broad-phase) 的误报更少（与 sweep and prune 互补：后者快但只会出正框）。排样 / 下料 / 包装：求能裹住一个零件的最小矩形料，直接决定省不省材料。GIS：建筑轮廓的最小外接矩形 (MBR) 常用来估朝向、做近似与索引。需要快而非最优时，也有人用 PCA 沿主轴定向取框——简单，但不保证面积最小，真要最优还得回到「贴着凸包边逐条试」这条路。

5 · 🔗 相关链接

Minimum bounding box · Wikipedia — 最小外接框总览：轴对齐 (AABB) 与任意朝向 (OBB) 的区别，以及二维最小面积矩形「必有一边贴凸包」的来历。
Rotating calipers · Wikipedia — 本页第三节的优化出处：一对垂直卡尺绕凸包旋转，把逐边重投影的 $O(h^2)$ 降到 $O(h)$ ，并能顺带求直径 / 宽度。
Contour features · minAreaRect · OpenCV — 工程侧：cv2.minAreaRect 返回（中心，宽高，角度）的旋转矩形，配 boxPoints 取四角——OCR / 检测里把斜框摆正的标准一步。
Convex hull algorithms · Wikipedia — 求最小矩形的前置步骤：本页用的 Andrew's monotone chain（按 x 排序后上下两条链各扫一遍，叉积定向弹栈）, $O(n \log n)$ 。