如何使用rtree更高效地查找所有3D包围盒的交集？

我有一个3D包围盒列表，想要找出所有包围盒之间的交集，目前用rtree实现但效率较低。以下是我当前的低效代码，请问有没有无需遍历每个盒子就能返回所有交集的更高效方法？

import rtree

# 包围盒列表
boundingBoxes = [(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 R树索引
p = rtree.index.Property()
p.dimension = 3
idx3d = rtree.index.Index(properties=p)
for index, bb in enumerate(boundingBoxes):
    idx3d.insert(index, bb)

# 当前方法：遍历每个盒子，检查与其他盒子的交集，效率较低
collisions = []
for i in range(len(boundingBoxes)):
    intersecting = list(idx3d.intersection(boundingBoxes[i]))
    for j in range(i+1, len(boundingBoxes)):
        if i < j and j in intersecting:
            collision = (boundingBoxes[i], boundingBoxes[j])
            collisions.append(collision)
            print(collision)

高效解决方案：使用R树内置的query_pairs方法 #

你完全不需要手动遍历每个盒子，rtree的Index对象提供了query_pairs方法，专门用于快速找出所有相交的空间对象对，并且自动返回不重复的结果（仅保留i < j的对，避免重复记录(A,B)和(B,A)）。

优化后的代码：

import rtree

# 包围盒列表
boundingBoxes = [(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 R树索引
p = rtree.index.Property()
p.dimension = 3
idx3d = rtree.index.Index(properties=p)
for index, bb in enumerate(boundingBoxes):
    idx3d.insert(index, bb)

# 直接获取所有相交对，无需手动遍历
collisions = []
for i, j in idx3d.query_pairs():
    collision = (boundingBoxes[i], boundingBoxes[j])
    collisions.append(collision)
    print(collision)

效率提升的原因： #

• 减少查询次数：原代码需要对每个包围盒执行一次intersection查询（共n次），而query_pairs仅需一次内部计算即可得到所有结果。
• 避免冗余筛选：原代码在得到相交索引后还要二次遍历筛选j，query_pairs直接返回符合i < j的相交对，省去了额外的判断逻辑。
• 内部优化实现：query_pairs是rtree库内部优化过的算法，基于空间索引的特性减少了不必要的空间比较，比手动遍历的效率高得多。

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