高效检测三维包围盒两两相交的优化方法-Python教程

本文介绍如何利用 `ckdtree` 替代传统 r-tree 逐框查询，将三维包围盒两两相交检测速度提升约 4 倍，核心在于以中心点空间索引预筛选候选对，再精确判断轴对齐包围盒（aabb）重叠。

在三维几何处理、物理仿真或碰撞检测等场景中，快速找出所有两两相交的轴对齐包围盒（Axis-Aligned Bounding Box, AABB）是常见但易成性能瓶颈的任务。原始方案使用 rtree 构建三维空间索引后，对每个盒子调用 .intersection() 并手动过滤下标（i

更高效的策略是分两阶段优化：

1. 粗筛（Coarse Filtering）：将每个 AABB 的几何中心作为三维点，构建 scipy.spatial.cKDTree；利用其 query(…, k=m) 快速获取每个中心的最近 m 个邻居（含自身），大幅缩小潜在相交候选集；
2. 精判（Precise Checking）：仅对粗筛输出的候选对，执行标准 AABB 重叠判断——即检查在 x、y、z 三个维度上投影区间是否均存在交集。

以下是完整可运行的优化实现：

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：计算各包围盒中心点（向量化）
mins = boundingBoxes[:, :3]   # shape: (n, 3)
maxs = boundingBoxes[:, 3:]   # shape: (n, 3)
centers = mins + 0.5 * (maxs - mins)  # 中心 = min + 0.5 * size

# 步骤2：构建 cKDTree 并查询近邻（k 取略大于平均密度的值，如 3~10）
tree = cKDTree(centers)
# distances[i, j] 和 indices[i, j] 分别表示第 i 个点到其第 j 近邻的距离与索引
# k=3 确保至少包含自身 + 2 个潜在邻居
distances, indices = tree.query(centers, k=3)

# 步骤3：遍历并精确判断 AABB 相交
collisions = []
for i in range(len(indices)):
    for j_idx in range(1, indices.shape[1]):  # 跳过自身（j=0）
        j = indices[i, j_idx]
        if i >= j:  # 保证每对只记录一次（i < j）
            continue
        # AABB 相交条件：所有维度投影均重叠
        # 即：box_i.min = box_j.min（逐维）
        overlap = not (
            np.any(mins[i] > maxs[j]) or   # i 在 j 的某维左侧/下方/外侧
            np.any(maxs[i] < mins[j])      # i 在 j 的某维右侧/上方/内侧
        )
        if overlap:
            collisions.append((boundingBoxes[i], boundingBoxes[j]))
            print(f"Collision: {boundingBoxes[i]} ↔ {boundingBoxes[j]}")

print(f"\nTotal collisions found: {len(collisions)}")

✅ 关键优势说明：