无重叠随机矩形高效放置算法优化方案咨询

1. 降低碰撞检测复杂度 #

• 采用网格分区/四叉树空间索引：将1000x1000的画布划分为固定大小的网格（比如50x50，和最大矩形尺寸一致），每个网格存储所有落入该网格的已放置矩形。生成候选矩形后，仅需检测它所覆盖的3-4个网格内的矩形即可，无需遍历所有已生成的矩形，碰撞检测次数可以降低一个数量级。

2. 放弃纯随机候选生成逻辑，从有效空白区域采样 #

• 维护全局可用空白区域列表：每次成功放置一个矩形后，将被它覆盖的原有空白区域拆分为上下左右最多4块新的空白区域，更新列表。后续生成候选矩形时，直接从空白区域列表中随机选一块，再在该区域范围内随机生成符合尺寸要求的矩形，从根源上避免重叠，完全不需要额外做碰撞检测。
• 优先放置大尺寸矩形：先生成所有宽高偏大的矩形放置完成后，再生成小尺寸矩形填充空隙，避免后期剩余空间碎片化后，大尺寸矩形反复尝试无法放置的问题。

3. 低侵入性小优化 #

• 连续失败超过阈值后，停止纯随机坐标生成：改为遍历已放置矩形的边缘空隙，扫描符合当前候选矩形尺寸的可用位置，比盲目的随机采样命中率高很多。
• 提前缓存所有已放置矩形的边界坐标值，避免每次碰撞检测时重复读取计算属性，进一步降低单轮检测耗时。

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