查找二维画布内所有最大未占用矩形空间的高效算法

你描述的「边界触碰到画布边缘或已放置矩形、无法再向任意方向扩展的空白矩形」，在计算几何领域被定义为最大空矩形（Maximal Empty Rectangle, 简称MER），目前已有非常成熟、经过工业场景验证的高效算法可以实现该需求，完全可以适配你给出的画布场景。

主流可落地算法 #

• 扫描线MER枚举算法
  这是静态场景（已放置矩形固定、一次性计算所有空位）下的最优选择，时间复杂度为O(n log n)，n为已放置矩形的数量。核心逻辑是先提取所有已放置矩形的垂直边界x坐标并排序，沿x轴逐段扫描，同步维护当前扫描区间内被已放置矩形占据的y轴分段，每一段连续的未被占据y区间，即可和当前x扫描段组合为候选矩形，最后过滤掉可继续扩展的非最大矩形即可。
  该算法无需对画布做栅格化处理，哪怕画布尺寸极大、已放置矩形数量较少时性能优势非常明显，你给出的965*606尺寸、仅5个已放置块的场景，计算耗时在微秒级。
• 栅格扩展算法
  如果你的画布尺寸固定、整体分辨率不高（例如前端UI编辑器画布、像素类游戏地图），可以先将画布转换为二值栅格：被占用的格子标记为1，空白格子标记为0。遍历所有空白格子作为种子点，分别向上下左右四个方向扩展，直到碰到占用格或画布边缘后记录生成的矩形，最后对重复结果做去重即可。
  这个算法实现门槛极低，逻辑简单易调试，缺点是画布分辨率极高时内存和计算开销会明显上升，仅适合中小尺寸固定画布场景。
• 动态分割维护算法
  如果你需要做动态交互场景（持续往画布上添加、删除矩形，需要实时更新空位列表），可以选择BSP二叉空间分割算法或者Guillotine切割算法：每次放置新矩形时，将它占据的原有大空位切割为若干个剩余的小矩形空位，全程维护这个空位列表即可。列表内存储的所有矩形天然就是符合要求的最大空矩形，不需要每次全量重算，目前广泛应用在自动排版引擎、2D纹理打包工具中。

示例场景适配说明 #

你给出的测试场景中，已放置矩形集合如下：

[
    {"x": 50, "y": 25, "width": 150, "height": 200},
    {"x": 250, "y": 50, "width": 75, "height": 100},
    {"x": 110, "y": 510, "width": 750, "height": 35},
    {"x": 330, "y": 200, "width": 500, "height": 100},
    {"x": 500, "y": 0, "width": 150, "height": 90}
]

针对965×606尺寸的画布，使用上述任意一种算法都可以快速输出所有符合要求的最大空白矩形，和你参考的计算效果完全匹配。

注意：符合定义的最大空矩形之间允许存在重叠区域，这是正常特性——只要单个矩形无法再向任意方向扩展就满足要求，不需要强制做互不重叠的分割。如果你的业务场景需要无重叠的空白区域划分，只需要在MER枚举结果基础上增加一步切割去重逻辑即可。

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