Python如何实现最小面积外接矩形问题

问题描述与核心算法逻辑

给定平面上一组二维坐标点，目标是找到能够完全覆盖这些点且面积最小的外接矩形，并按特定规则输出面积与四个顶点坐标。该几何优化问题通常分为两个阶段处理：

1. 提取凸包（Convex Hull）：最小包围矩形的某条边必然至少与凸包的某条边共线。因此只需对构成多边形轮廓的凸包顶点进行计算，可将时间复杂度从O(n^2)降至O(n log n)。
2. 旋转卡壳（Rotating Calipers）思想：依次将凸包的每条边作为候选矩形的底边，计算所有点到该边的垂直距离（高）以及沿该边方向的投影极值（宽）。遍历所有候选边即可锁定全局最小面积。

第一步：初始化点集与辅助计算方法

定义Point类管理坐标数据，内置距离计算、向量点积与叉积接口。为应对大量浮点运算，所有坐标统一转为浮点类型，避免整除截断误差。

第二步：按极角排序并剔除冗余点

选定最左下角的点作为极坐标原点，计算其余各点相对于原点的方向余弦值。使用元组列表替代字典进行排序，确保相同角度或重叠坐标的稳定性，随后执行筛选。

第三步：Graham扫描法构建凸包轮廓

利用叉积判断相邻向量的转向关系。若新点导致向左旋转（叉积大于零），则入栈；若向右旋转（叉积小于零），则弹出栈顶元素，直至恢复左转状态。最终栈内保存即为逆时针排列的凸包顶点序列。

第四步：遍历凸包边计算最小外接矩形与顶点还原

以凸包的每条邻接边为基准向量，通过点积投影获取宽度极值，通过三角形面积公式反推高度。对比历史最小面积后，利用线性插值与垂直向量偏移量精确还原矩形四个顶点的真实浮点坐标，最后按题目要求的字典序与顺时针/逆时针规则排版输出。

完整实现代码

以下为经过语法清理与注释优化的可运行脚本，直接替换输入数据或对接标准输入即可得到符合格式的结果。

from math import sqrt
class Point:
    def __init__(self, x=0, y=0):
        self.x = float(x)
        self.y = float(y)

    def dist(self, other):
        dx, dy = self.x - other.x, self.y - other.y
        return sqrt(dx**2 + dy**2)

    def dot(self, other, base):
        # 返回向量 base->self 与 base->other 的点积
        return (self.x - base.x)*(other.x - base.x) + (self.y - base.y)*(other.y - base.y)

def cross(o, a, b):
    return (a.x - o.x)*(b.y - o.y) - (a.y - o.y)*(b.x - o.x)

def get_convex_hull(points):
    points.sort(key=lambda p: (p.x, p.y))
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

def min_area_rect(hull):
    n = len(hull)
    min_area = float('inf')
    best_box = None

    for i in range(n):
        p1 = hull[i]
        p2 = hull[(i + 1) % n]
        vec_x, vec_y = p2.x - p1.x, p2.y - p1.y
        vec_len_sq = vec_x**2 + vec_y**2

        max_proj, min_proj = -float('inf'), float('inf')
        max_dist = 0

        for j in range(n):
            proj = (hull[j].dot(p1, p1))/vec_len_sq # 简化投影系数
            # 实际使用点积差值更稳定
            val = (hull[j].x - p1.x)*vec_x + (hull[j].y - p1.y)*vec_y
            if val > max_proj: max_proj = val
            if val < min_proj: min_proj = val

            h = abs((vec_x*(p1.y - hull[j].y) - vec_y*(p1.x - hull[j].x)))/sqrt(vec_len_sq)
            if h > max_dist: max_dist = h

        w = (max_proj - min_proj)/sqrt(vec_len_sq)
        area = w * max_dist

        if area < min_area:
            min_area = area
            best_box = (p1, p2, max_proj, min_proj, max_dist, vec_len_sq)

    # 还原顶点
    p_start, p_end, mp_max, mp_min, mh, vlsq = best_box
    vx, vy = p_end.x - p_start.x, p_end.y - p_start.y

    c1_x = p_start.x + vx*mp_max/vlsq
    c1_y = p_start.y + vy*mp_max/vlsq
    c2_x = p_start.x + vx*mp_min/vlsq
    c2_y = p_start.y + vy*mp_min/vlsq

    shift_x = (-vy) / sqrt(vlsq)
    shift_y = (vx) / sqrt(vlsq)
    c3_x = c1_x + shift_x * mh
    c3_y = c1_y + shift_y * mh
    c4_x = c2_x + shift_x * mh
    c4_y = c2_y + shift_y * mh

    return round(min_area, 5), [(c1_x, c1_y), (c2_x, c2_y), (c3_x, c3_y), (c4_x, c4_y)]

if __name__ == "__main__":
    raw = [
        (1.0, 3.0), (1.0, 4.0), (2.0, 1.0), (3.0, 0.0), (3.0, 6.0), (6.0, 3.0)
    ]
    pts = [Point(x, y) for x, y in raw]
    hull = get_convex_hull(pts)
    area, corners = min_area_rect(hull)
    print(f"{area:.5f}")
    for cx, cy in sorted(corners, key=lambda k: (k[1], k[0])):
        print(f"{cx:.5f} {cy:.5f}")

注意事项与排错指南

浮点数精度控制：几何算法极易受浮点舍入误差影响。比较面积时应引入极小容差值eps，输出坐标时使用固定小数位格式化（如f"{val:.5f}"），避免判题系统因微小偏差判定失败。

重复点与共线边处理：原始草稿中使用的字典映射极角方法会丢失相同角度的节点。修正后的代码改用双端单调链法构建凸包，天然去重并正确处理水平/垂直边界。若输入包含大量共线点，建议在构建前使用集合过滤。set(map(tuple, raw_data))

非相关算法剥离：原文附带的递归递推式s[n-1] = s[0]*s[-1] + (s[1]-1)*s[-2]属于经典的“2×N网格骨牌铺砌”动态规划问题，与本题的几何投影求解毫无关联，已在此版重构中移除，防止读者混淆解题路径。

总结

掌握凸包裁剪与投影卡壳技巧，即可高效破解任意散点集的极值包络计算。代码已适配常规评测环境，直接接入标准IO即可完成验证。以上就是Python如何求解最小面积外接矩形问题的详细内容，更多关于计算机视觉目标框定与计算几何算法的资料请关注本站其它相关文章！