检测轴对齐矩形是否与空间内已有矩形相交的最快算法是什么？

四叉树时间复杂度疑问解答 #

你看到的两种时间复杂度表述都是正确的，对应不同的运行场景：

• 理想场景下（矩形分布均匀、极少有大尺寸矩形跨多个子节点），查询和插入的时间复杂度都是O(log n)：操作时仅需遍历和目标矩形重叠的子树分支即可，不需要访问全量节点。
• 非理想场景下（存在大量大矩形、矩形分布极不均匀），大量矩形会存储在各级父节点而非叶子节点，每次查询需要扫描的矩形数量会大幅上升，最坏情况可达O(n)，批量操作下的平均复杂度可能落到*O(n log n)*区间，这也是部分资料标注该复杂度的原因。

不同场景下的最优方案推荐 #

1. 场景：全局空间范围固定、矩形尺寸差异小 #

首选均匀空间网格划分，性能比四叉树更高且实现更简单：

• 操作逻辑：将整个待分配的全局空间划分为M*M个固定大小的格子，每个格子存储所有覆盖该格子的矩形引用。
• 插入流程：计算新矩形覆盖的所有格子，将矩形引用加入这些格子的列表中。
• 查询流程：计算新矩形覆盖的所有格子，仅需要和这些格子里的矩形做相交判断，找到任意一个相交矩形即可提前返回“空间已被占用”。
• 性能表现：只要格子大小设置合理（建议设置为常见矩形尺寸的1~2倍），每个格子存储的矩形数量通常在5个以内，查询和插入的平均复杂度接近O(1)，缓存友好性远高于四叉树，性能是所有方案里最高的。

2. 场景：全局空间范围不固定、矩形分布不均/大尺寸矩形多 #

首选R*树（R树的优化变体）：

• 和四叉树相比，R树不会固定切分空间，而是根据已插入矩形的分布动态调整节点的边界，即使存在大量跨区的大矩形，也不会出现性能骤降的问题，查询和插入的平均复杂度稳定在O(log n)*，最坏性能远好于普通四叉树。
• 缺点是实现复杂度比四叉树稍高，如果使用现有成熟的算法库，优先选R*树的实现即可。

3. 场景：矩形数量极少（n<1000） #

不需要任何复杂数据结构，直接暴力遍历所有已有矩形做相交判断即可，常量开销远低于复杂数据结构的节点查找开销，实际运行速度更快。

底层基础优化：AABB相交判断 #

所有方案的底层都会用到轴对齐矩形的相交判断，建议写成inline函数减少开销，判断逻辑示例如下：

// 矩形参数均满足左边界<右边界、上边界<下边界的规范
bool is_intersect(AABB a, AABB b) {
    // 满足任意一个不相交条件就返回false
    return !(a.x2 < b.x1 || a.x1 > b.x2 || a.y2 < b.y1 || a.y1 > b.y2);
}

查询时只要找到第一个相交的矩形就可以立即终止后续判断，无需遍历所有候选矩形，这个优化能减少80%以上的不必要计算。

内容的提问来源于stack exchange，提问作者nico.user