直角多边形的最少矩形划分方案求助（Python实现）

给定一个由顶点列表定义的直角多边形（所有内角为90°），目标是用尽可能少的矩形完成表面划分，以下是针对示例的具体思路与实现：

示例顶点列表 #

corners = [[91570, 49055],
           [91570, 48870],
           [91570, 48778],
           [91690, 48778],
           [91815, 48778],
           [91815, 48892],
           [91695, 48892],
           [91695, 48930],
           [92245, 48930],
           [92245, 48892],
           [92137, 48892],
           [92137, 48778],
           [92370, 48778],
           [92370, 49055]]

该多边形为顶部水平、左右垂直的轮廓，底部存在多处直角凹凸结构，按要求可划分为5个矩形。

核心解法：凹点递归分解 #

直角多边形的最少矩形划分依赖于凹点识别与定向拆分：每个270°的凹点对应一个可拆分的矩形区域，通过递归拆分凹点所在区域，最终将所有子区域转化为矩形。

步骤1：识别凹点 #

通过向量叉积判断顶点类型：

• 取顶点P[i]及其前后顶点P[i-1]、P[i+1]（首尾相连）
• 叉积为负时，该顶点为270°凹点；为正时为90°凸点

步骤2：定向拆分多边形 #

针对每个凹点，沿垂直/水平方向延伸边至与多边形边界相交，拆分出一个矩形和一个新的直角多边形，重复此过程直到所有子区域均为矩形。

Python实现代码 #

1. 凹点判断函数 #

def is_concave(p_prev, p_curr, p_next):
    # 计算相邻边的向量
    v1 = (p_curr[0] - p_prev[0], p_curr[1] - p_prev[1])
    v2 = (p_next[0] - p_curr[0], p_next[1] - p_curr[1])
    # 叉积计算，负数值对应凹点
    cross = v1[0] * v2[1] - v1[1] * v2[0]
    return cross < 0

2. 多边形拆分函数 #

def split_polygon(polygon):
    rectangles = []
    n = len(polygon)
    # 识别所有凹点
    concave_points = []
    for i in range(n):
        prev = polygon[(i-1) % n]
        curr = polygon[i]
        next_p = polygon[(i+1) % n]
        if is_concave(prev, curr, next_p):
            concave_points.append((i, curr))
    
    # 无凹点则当前为矩形
    if not concave_points:
        x_coords = [p[0] for p in polygon]
        y_coords = [p[1] for p in polygon]
        rect = (min(x_coords), min(y_coords), max(x_coords), max(y_coords))
        rectangles.append(rect)
        return rectangles
    
    # 取第一个凹点进行拆分（可优化选择最优凹点减少拆分次数）
    i, p = concave_points[0]
    prev = polygon[(i-1) % n]
    next_p = polygon[(i+1) % n]

    # 根据凹点相邻边方向选择拆分方向
    if prev[0] == p[0]:  # 前边为垂直方向，水平拆分
        split_y = p[1]
        # 寻找拆分线与多边形的交点
        for j in range(n):
            q_prev = polygon[(j-1) % n]
            q_curr = polygon[j]
            if q_prev[1] == split_y and q_curr[1] == split_y:
                continue
            if (q_prev[1] - split_y) * (q_curr[1] - split_y) <= 0:
                intersect_x = q_prev[0] if q_prev[1] == split_y else q_curr[0]
                intersect_point = (intersect_x, split_y)
                # 记录拆分出的矩形
                rect = (min(p[0], intersect_x), split_y, max(p[0], intersect_x), max(prev[1], next_p[1]))
                rectangles.append(rect)
                # 构建子多边形并递归处理
                sub_polygon = polygon[i+1:] + [intersect_point] + polygon[:i]
                rectangles.extend(split_polygon(sub_polygon))
                break
    else:  # 前边为水平方向，垂直拆分
        split_x = p[0]
        for j in range(n):
            q_prev = polygon[(j-1) % n]
            q_curr = polygon[j]
            if q_prev[0] == split_x and q_curr[0] == split_x:
                continue
            if (q_prev[0] - split_x) * (q_curr[0] - split_x) <= 0:
                intersect_y = q_prev[1] if q_prev[0] == split_x else q_curr[1]
                intersect_point = (split_x, intersect_y)
                rect = (split_x, min(p[1], intersect_y), max(prev[0], next_p[0]), max(p[1], intersect_y))
                rectangles.append(rect)
                sub_polygon = polygon[i+1:] + [intersect_point] + polygon[:i]
                rectangles.extend(split_polygon(sub_polygon))
                break
    return rectangles

3. 调用示例 #

# 转换顶点为元组便于处理
polygon = [tuple(p) for p in corners]
result_rectangles = split_polygon(polygon)

print(f"划分得到的矩形数量：{len(result_rectangles)}")
for idx, rect in enumerate(result_rectangles, 1):
    print(f"矩形{idx}：x范围[{rect[0]}, {rect[2]}]，y范围[{rect[1]}, {rect[3]}]")

优化方向 #

• 可通过选择最优凹点（拆分后能减少最多剩余凹点的顶点）进一步确保得到最少矩形数量
• 对拆分结果可增加矩形合并逻辑，避免因拆分顺序导致的冗余矩形

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