如何获取一堆点的最小面积外接矩形？

发布时间: 2026-07-28 所属分类: 文章标签:

当前位置：

最近做点云范围提取时候，小编遇到一个问题，给一堆离散点，怎么求包住它们的最小面积矩形？小编大约翻了一下网上成熟的实现，总结了一下实现的方法，有兴趣的小伙伴可以参考。

什么是最小面积外接矩形

最小面积外接矩形，英文常叫 Minimum Area Rectangle、Minimum Bounding Rectangle，缩写 MAR 或 MBR。和常见最小外接矩形不同，它允许矩形旋转任意角度，但要求面积最小。如下图：

算法原理

最容易想到的做法是先求凸包，把多边形绕质心每次转 1°，每次算一遍轴对齐外接矩形面积，转满 360° 后取最小值。这个方法虽然可行，但这种方法比较耗费计算，且最后的精准度与步长有关。

在 polygon generalisation 领域这个问题叫 “smallest surrounding rectangle”。关键性质是：最小面积外接矩形的朝向，必然与凸包某一条边的方向一致。因此不必按固定角度步长穷举，只要遍历凸包每条边，把该边当作矩形的一条边方向，在这个朝向下求外接矩形面积，取最小即可。

具体步骤如下。

对点集求凸包
遍历凸包每条边，计算边的方向角或单位方向向量。
以该边方向为基准，把凸包顶点投影到“沿边方向”和“垂直边方向”两个轴上，分别取 min/max，得到该朝向下面积最小的外接矩形。
比较所有边的结果，取面积最小。

凸包顶点数通常远小于原始点数，边数也就是 O(h)，h 为凸包顶点数，整体效率比“每 1° 转一次”高得多。3D 情形思路类似，但要测试凸包各个面的朝向，比 2D 更复杂一些。

Python实现

按这个思路，小编用 NumPy 和 SciPy 写了一个 Python 版本，返回矩形四个角点坐标：

import numpy as np
from scipy.spatial import ConvexHull

def minimum_bounding_rectangle(points):
    """求点集的最小面积外接矩形，返回 4x2 角点坐标。"""
    pts = np.asarray(points, dtype=float)
    hull = ConvexHull(pts)
    vertices = pts[hull.vertices]
    n = len(vertices)

    min_area = np.inf
    best_corners = None

    for i in range(n):
        p1 = vertices[i]
        p2 = vertices[(i + 1) % n]
        edge = p2 - p1
        length = np.linalg.norm(edge)
        if length == 0:
            continue

        v = edge / length
        w = np.array([-v[1], v[0]])

        proj_v = vertices @ v
        proj_w = vertices @ w
        min_v, max_v = proj_v.min(), proj_v.max()
        min_w, max_w = proj_w.min(), proj_w.max()
        area = (max_v - min_v) * (max_w - min_w)

        if area < min_area:
            min_area = area
            local = np.array([
                [max_v, min_w],
                [min_v, min_w],
                [min_v, max_w],
                [max_v, max_w],
            ])
            best_corners = local @ np.vstack([v, w])

    return best_corners

需要注意的是，如果绘图时 x、y 轴比例不一致，矩形在屏幕里可能看起来像平行四边形，那是显示比例问题。

其他实现方式

如果不想自己写代码，也有一些现成工具，比如：

OpenCV 提供 minAreaRect，输入 2D 点集即可返回旋转矩形
PostGIS 从 2.5.0 起提供 ST_OrientedEnvelope，底层调用 GEOS 的 GEOSMinimumRotatedRectangle；Shapely 对应 oriented_envelope()，别名 minimum_rotated_rectangle()，GeoPandas 里也可写 geometry.minimum_rotated_rectangle。

总结

虽然了解了原理，也找到了一个基础版本，但小编最后还是使用了 GeoPandas来实现了业务功能，原理归原理，实现归实现，毕竟这么大的开源软件写的一定比我好～

参考

Finding minimum-area-rectangle for given points?：https://gis.stackexchange.com/questions/22895/finding-minimum-area-rectangle-for-given-points
Whitebox GAT：https://www.whiteboxgeo.com/
OpenCV minAreaRect 教程：https://docs.opencv.org/4.x/de/d62/tutorial_bounding_rotated_ellipses.html