如何用 cKDTree 高效检测三维包围盒两两交集-Python教程

本文介绍一种比传统 r-tree 逐个查询更高效的三维包围盒交集检测方法：利用 `scipy.spatial.ckdtree` 加速中心点邻域搜索，再辅以精确的轴对齐包围盒（aabb）相交判断，整体性能提升可达 4 倍。

在三维空间中检测大量轴对齐包围盒（Axis-Aligned Bounding Box, AABB）的两两交集是计算几何、物理仿真和碰撞检测中的常见任务。虽然 rtree 提供了基于 R-tree 的空间索引能力，但其原生 API 在全对全交集枚举（all-pairs intersection detection）场景下存在明显瓶颈：对每个盒子调用 .intersection() 会触发独立的树遍历，无法避免重复访问与冗余比较，时间复杂度接近 O(n²)。

更高效的做法是引入分治式空间剪枝策略：先用近似但极快的 k-d 树（如 cKDTree）快速筛选出“潜在相交”的候选对（基于中心点距离），再对这些候选执行精确的 AABB 相交判定。由于真实交集通常只发生在空间邻近的盒子之间，该方法可将需验证的候选对数量大幅压缩，显著降低常数因子与实际运行时间。

以下为完整实现示例：

import numpy as np
from scipy.spatial import cKDTree

# 输入：n × 6 数组，每行格式为 (min_x, min_y, min_z, max_x, max_y, max_z)
boundingBoxes = np.array([
    (1, 1, 1, 2, 2, 2),
    (3, 3, 3, 6, 6, 6),
    (5, 5, 5, 7, 7, 7),
    (7, 7, 7, 8, 8, 8)
])

# 计算每个包围盒的几何中心（3D 点）
centers = boundingBoxes[:, :3] + 0.5 * (boundingBoxes[:, 3:] - boundingBoxes[:, :3])

# 构建 cKDTree（支持批量最近邻查询）
tree = cKDTree(centers)

# 查询每个中心点的 k=3 最近邻（含自身，故取 indices[:, 1:] 跳过自身）
distances, indices = tree.query(centers, k=3)

collisions = []
for i in range(len(indices)):
    for j in indices[i, 1:]:  # 排除自身（j != i）
        if i  boundingBoxes[j, 3] or  # x: i.min > j.max
                boundingBoxes[i, 1] > boundingBoxes[j, 4] or  # y: i.min > j.max
                boundingBoxes[i, 2] > boundingBoxes[j, 5] or  # z: i.min > j.max
                boundingBoxes[j, 0] > boundingBoxes[i, 3] or  # x: j.min > i.max
                boundingBoxes[j, 1] > boundingBoxes[i, 4] or  # y: j.min > i.max
                boundingBoxes[j, 2] > boundingBoxes[i, 5]      # z: j.min > i.max
            )
            if not disjoint:
                collisions.append((boundingBoxes[i], boundingBoxes[j]))
                print(f"Collision: {boundingBoxes[i]} ↔ {boundingBoxes[j]}")

✅ 关键优化点说明：