快速椭球相交算法

Question

假设我有一百万个任意形状、任意定向的N维椭球体随机分布在N维空间中。给定一个子集的椭球体，我想要“快速”确定第一组椭球体与哪些椭球体相交。

肯定有一个算法可解决这个问题。它是什么？它的“O”复杂度是多少？

- JnBrymn

---

为什么？没有为什么，这听起来像是“帮我做作业”。 - spender

@spender - 太好了！这意味着答案很容易得出。之所以这样做，是因为我想使用球族来限定任意概率分布。确定哪些球族重叠将使我能够首先解决广义似然问题。- 不，这不是一道作业题。 - JnBrymn

@Oli 是的！让我们假设这样。我试图重新表述问题，以便我可以使用kd树，但是我失败了。具体来说，我想将3D球描述为4D空间中的一个点：（x，y，z，半径）。但我立即意识到您不能使用普通的欧几里得距离度量。 - JnBrymn

@Pedery - 我希望最终目标如我在上面的帖子中所描述的那样 - 然而，如何最好地达到这个最终目标，我不确定。如果解决两个子问题有助于解决问题，那么我们应该这样做。 - JnBrymn

这可能会根据您的参数而起作用或不起作用。使用类似于这个的东西，快速计算凸包的交点，仅当它们相交时，才计算椭球体的交点。 - Dr. belisarius

Answer 1

"O"复杂度在处理N维数据时会受到“维数灾难”的影响。（有关此问题的更多信息，请参见此维基百科文章）。我建议从物理模拟中借鉴，将此问题分为“广域”和“窄域”两个阶段：

• 广域阶段保守地找到潜在重叠椭圆对的大量较小集合。
• 窄域阶段将潜在重叠椭圆对的集合修剪为实际重叠的那些椭圆对。

窄域阶段是一个简单的计算几何问题，测试任意椭圆之间是否相交。对于广域阶段，您需要使用空间结构，例如空间哈希、空间树（R树、Kd树、X树、UB树等）、或者根据您正在加载的数据的特殊属性给出的临时结构（例如不平衡的树或哈希）。

当前流行的方法是Kd树。有很多文档和已经编码好的Kd树版本可以轻松配置，所以我建议您在网上查找（谷歌是您的好朋友）。使用大多数树结构的优点是，如果您要查找的集合相对紧凑，则可以仅搜索一次树，并在不必执行多个树遍历的情况下找到交点。这将有助于缓存（无论是来自主内存还是磁盘）访问模式。同样的算法可以处理异类查询成员。然而，您正在进行的工作很可能会受益于紧凑的查询集属性。

Kd树并不能解决所有椭圆体的问题——例如，如果您有一个维度为N的椭球体，其主轴从（0,0,0,0,...）到（1,1,1,1,...），但副轴较小或不重要（因此不会相交），仍需要在覆盖所有N个维度的[0,1]节点中。如果您的椭圆体落在[0,1]^n中，则每个椭圆体都会测试与上述不方便的椭圆体的相交。但是，使用真实世界数据（甚至大多数合成数据，除非您确实努力使Kd树变慢），Kd树方法应该是胜利的选择。

如果您预计Kd树对千维椭圆体会成功，那么最好使用暴力搜索。（前面提到的维数灾难。）然而...

如果您有一个经过优化的实现，那么一百万个条目并不算太糟糕，但如果您要进行大量查询（数百万次），它将非常缓慢（约为10秒或更长）。然而，我已经看到一些出色的数字，这些数字来自于经过优化的矢量化代码。 （甚至使用了这种策略的产品。）通过正确的高速缓存一致性，暴力搜索最多只需要几毫秒。这意味着在C/C++中使用ASM或矢量内在函数。"

对于大多数数据而言，O(n)时间复杂度（不考虑维度灾难）对于查询（一旦树被构建）应该是摊销的O(m log n)，其中m是查询集中椭圆的数量，n是数据集中椭圆的数量。构建数据本身不应该超过O(n log n)。将所有内容乘以Exp(d)，其中d是维数 - 这就是这种类型的方法。

- Kaganar

---

太棒了！感谢您的输入。我的理解是，如果我能对椭球体的最大尺寸做出一些假设，那么我就可以使用Kd树来快速削减空间大小，以便更容易地解决计算几何问题。 - JnBrymn

基本上是的。如果由于空间限制而真正需要这样做，您可以从磁盘中进行，因为树遍历比暴力搜索更少依赖带宽。但是，一个经过良好优化的暴力搜索解决方案（如果由于我在这里不知道的要求而必须采用）仍然可以工作。实际上，我曾经发布过一些类似问题的游戏，每帧只需几毫秒的暴力搜索，但那需要很多仔细的优化。 - Kaganar

如果你不想使用预先制作好的Kd-tree实现，而是想使用自己的结构，如果椭球体具有相当一致的大小，那么空间哈希结构更容易实现，并且根据数据本身可以具有更高的性能。 Kd树通常对数据不太敏感，但具有更复杂的操作，从而使其速度变慢。 两者都对维数非常敏感。 - Kaganar