查找面积最大、无交叉且不在排除区域内的bounding box轮廓

核心思路 #

该问题属于经典的「最大空轴对齐矩形」求解场景，核心逻辑为：所有合法的最大矩形的边界必然与现有排除框的边界、原始图像边界对齐，我们只需枚举所有可能的边界组合，校验合法性后取面积最大的结果即可。

基础工具函数实现 #

# 将四点格式的bbox转换为xmin/ymin/xmax/ymax格式，方便计算
def bbox_to_xyxy(bbox):
    xs = [p[0] for p in bbox]
    ys = [p[1] for p in bbox]
    return min(xs), min(ys), max(xs), max(ys)

# 判断两个框是否相交
def is_intersect(box1, box2):
    x1_min, y1_min, x1_max, y1_max = box1
    x2_min, y2_min, x2_max, y2_max = box2
    if x1_max <= x2_min or x1_min >= x2_max:
        return False
    if y1_max <= y2_min or y1_min >= y2_max:
        return False
    return True

# 判断候选框是否完全在排除框内部
def is_inside(candidate_box, exclude_box):
    c_xmin, c_ymin, c_xmax, c_ymax = candidate_box
    e_xmin, e_ymin, e_xmax, e_ymax = exclude_box
    return c_xmin >= e_xmin and c_ymin >= e_ymin and c_xmax <= e_xmax and c_ymax <= e_ymax

核心求解代码 #

def find_max_valid_bbox(exclude_bboxes, img_w, img_h):
    # 入参说明：
    # exclude_bboxes：所有排除框的列表，每个元素为[[x,y],[x,y],[x,y],[x,y]]的四点格式
    # img_w、img_h：原始图像的宽、高
    exclude_xyxy = [bbox_to_xyxy(box) for box in exclude_bboxes]
    
    # 收集所有可能的边界坐标：图像边界+所有排除框的上下左右边界
    x_coords = {0, img_w}
    y_coords = {0, img_h}
    for box in exclude_xyxy:
        x_coords.add(box[0])
        x_coords.add(box[2])
        y_coords.add(box[1])
        y_coords.add(box[3])
    
    x_list = sorted(x_coords)
    y_list = sorted(y_coords)
    
    max_area = 0
    best_box = None

    # 枚举所有左右边界组合
    for i in range(len(x_list)):
        x1 = x_list[i]
        for j in range(i+1, len(x_list)):
            x2 = x_list[j]
            width = x2 - x1
            # 剪枝：当前宽度下最大可能面积小于已找到的最大面积，直接跳过
            if width * img_h <= max_area:
                continue
            # 枚举所有上下边界组合
            for k in range(len(y_list)):
                y1 = y_list[k]
                for l in range(k+1, len(y_list)):
                    y2 = y_list[l]
                    height = y2 - y1
                    area = width * height
                    if area <= max_area:
                        continue
                    candidate = (x1, y1, x2, y2)
                    # 合法性校验：不与任何排除框相交、不在任何排除框内部
                    valid = True
                    for e_box in exclude_xyxy:
                        if is_intersect(candidate, e_box) or is_inside(candidate, e_box):
                            valid = False
                            break
                    if valid:
                        max_area = area
                        best_box = candidate
    
    # 转换回四点格式输出
    if best_box:
        xmin, ymin, xmax, ymax = best_box
        return [[xmin, ymin], [xmax, ymin], [xmax, ymax], [xmin, ymax]]
    return None

调用示例 #

# 示例：排除顶部左右两个小框，图像分辨率1920*1080
exclude_boxes = [
    [[10,10], [100,10], [100,200], [10,200]],
    [[1800,10], [1910,10], [1910,200], [1800,200]]
]
max_valid_box = find_max_valid_bbox(exclude_boxes, 1920, 1080)
print(max_valid_box)

优化建议 #

如果排除框数量较多（大于100个），上述四层循环的枚举方式效率较低，可以替换为扫描线优化版本的最大空矩形算法：按x坐标顺序扫描，维护每个x位置的有效高度区间，直接求解每个竖条内的最大矩形，时间复杂度可优化至O(n²)，适合大规模数据场景。

内容的提问来源于stack exchange，提问作者Damian Grzanka