求非重叠矩形集合的纯水平垂直线轮廓提取算法

问题背景 #

输入一组非重叠矩形（格式为{x1, y1, x2, y2}），需要输出仅由水平/垂直线段构成的整体轮廓点数组。凸包、凹包算法无法满足需求——它们会生成斜向边，且输出结果难以简化为规整的轴对齐轮廓。

实现思路 #

1. 提取并排序关键坐标

• 收集所有矩形的x1、x2值，去重后升序排序得到x_coords数组
• 收集所有矩形的y1、y2值，去重后升序排序得到y_coords数组
  这些坐标将平面划分为规则网格，每个网格单元是相邻x、y坐标组成的小矩形，且每个单元要么完全被矩形覆盖，要么完全未被覆盖（因输入矩形非重叠）。

2. 标记网格单元的覆盖状态

遍历每个网格单元，判断其是否被任意输入矩形覆盖：

• 取网格单元的中心坐标(cx, cy)，若存在输入矩形满足x1 ≤ cx ≤ x2且y1 ≤ cy ≤ y2，则标记该单元为已覆盖
• 也可通过判断单元的任意顶点是否在输入矩形内来实现，结果一致

3. 遍历网格提取轮廓拐点

从最左上角的未覆盖区域开始，沿网格边缘顺时针遍历，仅在方向改变（水平转垂直/垂直转水平）时记录坐标点，最终得到闭合的轮廓点序列：

• 当移动方向上的下一个网格单元从“未覆盖”变为“已覆盖”（或反之）时，记录当前拐角点
• 若矩形组包含多个独立区块，需分别提取每个区块的轮廓

示例说明 #

假设输入矩形：

[{1,1,3,3}, {2,4,5,6}, {6,2,8,5}]

处理后得到的轮廓点序列（顺时针，仅保留拐点）：

[(1,1), (3,1), (3,3), (2,3), (2,4), (5,4), (5,6), (2,6), (2,4), (1,4), (1,1), (6,1), (6,2), (8,2), (8,5), (6,5), (6,1)]

优势 #

• 输出的轮廓完全由水平/垂直线段构成，符合需求
• 自动生成最简拐点序列，无需额外简化处理
• 支持分离的多区块矩形组，能提取所有独立轮廓

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