高效查找三维包围盒间全部交集的优化方法-Python教程

本文介绍如何利用 `scipy.spatial.ckdtree` 替代传统 r-tree 逐盒查询，显著提升三维包围盒两两交集检测效率，兼顾精度与性能。

在三维空间分析（如碰撞检测、体素合并、几何布尔运算）中，快速识别大量轴对齐包围盒（AABB）之间的所有交集对是常见且关键的计算任务。原方案使用 rtree 构建三维索引后，对每个盒子调用 intersection() 并手动过滤下标（i 性能瓶颈明显。

更高效的策略是分层剪枝：先用空间索引快速缩小潜在交集范围，再对候选对做精确 AABB 相交判断。scipy.spatial.cKDTree 在此场景中表现优异——它基于 k-d 树构建中心点索引，支持批量近邻查询（query(…, k=k)），能以 O(n log n) 预处理 + O(nk) 查询的复杂度，大幅减少需精检的候选对数量。

以下为优化后的完整实现：

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)
])

# 步骤1：计算每个包围盒的几何中心（用于空间索引）
centers = boundingBoxes[:, :3] + 0.5 * (boundingBoxes[:, 3:] - boundingBoxes[:, :3])

# 步骤2：构建 cKDTree（自动优化高维距离计算）
tree = cKDTree(centers)

# 步骤3：对每个中心，查询其最近的 k 个中心（含自身），k 取略大于平均密度的值
# 这里 k=3 是经验起点；实际应用中建议根据数据密度动态设定（如 k = min(10, len(boundingBoxes)//2)）
distances, indices = tree.query(centers, k=min(3, len(boundingBoxes)))

# 步骤4：遍历候选对，执行精确 AABB 相交判断
collisions = []
for i in range(len(indices)):
    for j in indices[i]:
        if i < j:  # 避免重复和自交
            # AABB 相交条件：两个盒子在所有三个轴上投影均重叠
            # 即：box_i.min = box_j.min（逐轴）
            overlap = not (
                np.any(boundingBoxes[i, :3] > boundingBoxes[j, 3:]) or
                np.any(boundingBoxes[i, 3:] < boundingBoxes[j, :3])
            )
            if overlap:
                collisions.append((boundingBoxes[i], boundingBoxes[j]))

print(f"检测到 {len(collisions)} 对交集：{collisions}")

✅ 关键优化点说明：