如何用分治算法在Python中计算矩形并集？合并步骤求解

问题描述 #

计算矩形的并集（Union），每个矩形由左上角（top_left）和右下角（bottom_right）点定义。需将给定的矩形集合转换为另一组无重叠的矩形，且覆盖面积与原集合相等。

分治思路与当前问题 #

采用分治（divide-and-conquer）算法：递归将矩形集合拆分为两个子集，直到子集仅含一个矩形（类似归并排序），但目前缺少左右子集的合并逻辑。

合并逻辑实现 #

分治的核心是合并两个无重叠矩形集合，思路为：将右侧集合的每个矩形，与左侧集合的所有矩形做差集运算，保留右侧矩形中未被左侧覆盖的部分，再与左侧集合合并，最终得到无重叠的并集。

辅助函数：矩形差集计算 #

先实现矩形A减去矩形B的函数，返回A中不与B重叠的部分（可能是0到4个矩形）：

def subtract_rect(a, b):
    """
    计算矩形a减去矩形b后剩余的矩形列表
    每个矩形格式：((top_x, top_y), (bottom_x, bottom_y))
    """
    a_tl, a_br = a
    a_tx, a_ty = a_tl
    a_bx, a_by = a_br
    b_tl, b_br = b
    b_tx, b_ty = b_tl
    b_bx, b_by = b_br

    # 完全不重叠时直接返回原矩形
    if a_bx <= b_tx or a_tx >= b_bx or a_by >= b_ty or a_ty <= b_by:
        return [a]
    
    remaining = []
    # 处理上方未重叠区域
    if a_ty > b_ty:
        remaining.append(((a_tx, a_ty), (a_bx, b_ty)))
    # 处理下方未重叠区域
    if a_by < b_by:
        remaining.append(((a_tx, b_by), (a_bx, a_by)))
    # 处理左侧中间未重叠区域
    if a_tx < b_tx:
        remaining.append(((a_tx, min(a_ty, b_ty)), (b_tx, max(a_by, b_by))))
    # 处理右侧中间未重叠区域
    if a_bx > b_bx:
        remaining.append(((b_bx, min(a_ty, b_ty)), (a_bx, max(a_by, b_by))))
    
    return remaining

完整分治合并函数 #

修改原分治函数，加入合并逻辑：

def merge_rectangles(rects: list):
    assert len(rects) > 0, "rects should not be empty"
    if len(rects) == 1:
        # 单个矩形返回列表形式，方便后续合并操作
        return [rects[0]]
    else:
        mid = len(rects) // 2
        left_union = merge_rectangles(rects[:mid])
        right_union = merge_rectangles(rects[mid:])
        
        # 合并左右两个无重叠矩形集合
        merged = left_union.copy()
        for right_rect in right_union:
            current = [right_rect]
            # 用左侧每个矩形切割当前右侧矩形，保留未重叠部分
            for left_rect in left_union:
                new_current = []
                for rect in current:
                    new_current.extend(subtract_rect(rect, left_rect))
                current = new_current
                if not current:
                    break  # 矩形已被完全覆盖，无需继续切割
            # 将剩余未重叠部分加入合并结果
            merged.extend(current)
        
        return merged

注意事项 #

• 需保证所有矩形的坐标定义一致：比如左上角(top_x, top_y)的x轴递增方向、y轴递增方向，需在subtract_rect中统一逻辑
• 该算法通过分治减少重复计算，合并时仅处理无重叠矩形集合，效率优于暴力合并所有矩形的方案

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