如何基于矩形列表识别未被占用的空白区域

我需要开发一个算法，在指定尺寸的基础矩形上放置若干矩形后，找出所有未被覆盖的空白区域矩形。以下是我希望复现的算法效果示例：

• 示例图1：基础矩形上放置少量矩形后，识别出剩余空白区域
• 示例图2：多矩形交错放置场景下的空白区域识别
• 示例图3：复杂布局下的空白区域提取

核心算法思路 #

1. 初始区域拆分法 #

• 从基础矩形作为初始空白区域开始，逐个处理已放置的矩形：
  • 遍历当前所有空白区域，判断每个区域与当前放置矩形是否重叠
  • 若存在重叠，将原空白区域拆分为最多4个不重叠的子区域（分别对应原区域在放置矩形的上方、下方、左侧、右侧未被覆盖的部分）
  • 过滤掉面积为0的无效区域，更新空白区域列表
• 处理完所有已放置矩形后，剩余的列表即为所有空白区域

2. 坐标扫描线法 #

• 收集所有已放置矩形的左右边界x坐标，排序并去重，得到垂直分割线集合
• 对每两条相邻分割线形成的垂直条带，统计该条带内被已放置矩形覆盖的y轴区间
• 用条带的总y范围减去覆盖区间，得到条带内的空白y区间，每个区间对应一个空白矩形
• 合并相邻条带中y区间完全一致且x连续的空白矩形，减少结果数量

3. 网格离散化法（适合简单场景） #

• 将基础矩形划分为足够精细的网格单元
• 标记所有被已放置矩形覆盖的网格单元
• 对未标记的网格单元进行连通区域分析，将每个连通区域合并为一个最小包围矩形
• 注意：网格精度越高，结果越准确，但计算量也会随之增大

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