binary-tree - 可以使用距离函数平衡未排序的二叉树吗？

Question

我有以下理论问题：
我在 3 维空间中有 n 个长方体。它们与坐标系对齐，因此可以通过点 (x,y,z) 和尺寸 (dimX,dimY,dimZ) 来描述一个长方体。我想以一种能够检查新插入的长方体是否与现有长方体（碰撞检测）相交的方式组织这些长方体。为此，我决定使用分层边界框。所以总而言之，我有一个边界体积的二叉树结构。然后通过递归确定到两个孩子的距离（=两个长方体的两个中心之间的距离）并插入距离最小的路径来完成插入。碰撞检测的工作原理类似，但我们采用与给定长方体相交的子路径中的所有边界体积。
棘手的部分是，如果一些长方体彼此非常接近而其他长方体相距很远，如何平衡这棵树以获得更好的性能。到目前为止，我还没有找到使用例如 AVL-tree 的方法，因为这样我就必须能够以某种方式比较两个长方体，而不会破坏碰撞检测所依赖的条件。
PS：我知道有库可以做到这一点，但我想详细了解碰撞检测的原理，例如在游戏中，因此想自己实现。

Answer 1

我现在尝试使用空间分区而不是对象分区。这并不是我想要做的，但我发现了更多有用的信息，例如：https
://en.wikipedia.org/wiki/Kd-tree 有了这些信息，应该可以实现它。