什么是检测多面体交点最快的算法？

Question

假设有n个三维物体（多面体），计算所有物体的交集的最快方法是O(n ^ 2)吗？

目前，我正在使用一个库，它基本上强制T(n)等于n ^ 2：

for each object: // there are n objects
    get list of intersecting objects // this takes n steps

那需要 n ^ 2 步才能完成。

我唯一想到的更快的方法仍然是 O(n ^ 2)，但 T(n) = n(n+1) / 2 或 (n*n + n) / 2。

这里是伪代码：

for(int i = 0; i < len(objects) - 1; i++)
    for(int j = i + 1; j < len(objects); j++)
        if object at i intersects object at j:
            object at i . addToIntersectList ( object at j )
            object at j . addToIntersectList ( object at i )

这样我们就不必检查两个对象是否相交两次了。我知道我正在迭代的列表中大约有3000个对象。这个算法需要4501500步，而原始算法需要近9000000步。

我有什么遗漏吗？这是我们能得到的最好结果吗？

- user3745189

---

如果你可以让GPU来计算，那么450万步骤可能并不那么糟糕！请查看http://en.wikipedia.org/wiki/Gpgpu、http://en.wikipedia.org/wiki/OpenCL或者甚至是http://en.wikipedia.org/wiki/CUDA，看看这是否适用于你的情况。以防其他优化无法满足你在性能方面的需求。 - Markus A.

也许可以使用平面扫描算法的3D变体来处理相交的多边形。 - phipsgabler

Answer 1

虽然有一些方法可以通过改变循环方式来改进O(n²)的性能，但是通过改变碰撞检测的其他方面可以取得显著的改进。

你的代码中主要的低效率之一是它依赖于完全检查每个多面体与所有其他多面体的方式，这通常并不总是必要的。如果两个形状之间相距较远，则不需要进行密集的交集测试，如果您有两个由大片空间分隔开的形状群，则也不需要对每个形状组成部分与另一个群组中的每个成员进行检查。一些执行此类优化的技术包括：

• 局部敏感哈希
• 空间划分
• 包围体积

您可以使用这些技术来大大加速碰撞搜索。

- AJMansfield

---

"在减少与实体数量相关的复杂度方面，实际上没有很好的方法可以将其降至O(n²)以下..." 不是真的，Hoey-Shamos算法的时间复杂度为O(nLog(n))。 - RBarryYoung

@RBarryYoung，你能提供一个链接吗？我不知道这个技术，我很想学习一下它的工作原理。 - AJMansfield

很难在专业期刊之外找到相关资料，但这是我能找到的最开放的在线链接：https://en.wikipedia.org/wiki/Sweep_line_algorithm。 - RBarryYoung

@RBarryYoung 哇，谢谢。我甚至没有意识到你可以这样做。我会编辑我的答案，以包含一些关于此的信息。 - AJMansfield

Answer 2

信不信由你，我已经在StackOverflow上回答了这个问题，链接在此：https://dev59.com/2HXZa4cB1Zd3GeqPAv5o#19172550。虽然那个问题和答案是关于多边形（2D）的，但同样适用于多面体（3D）。

那里的问题还提到了被认为是最快的算法——Hoey Shamos扫描线技术，其时间复杂度为O(n log n)。你可以去研究和实现它，但它相当复杂。

我在我的答案中演示的简单得多的算法的性能高度依赖于形状和它们的位置的“良好程度”。形状越复杂、重叠越密集，它的性能就越差。然而，在形状良好（即凸形或大部分如此）且交点很少、堆积不太密集的情况下，我发现它的表现比O(n sqrt(n))更好。那里的代码和讨论主要是关于两个多边形内的线，但这也适用于多边形本身。

我方法的一个重要优势是，它可以独立于你用来检测两个多边形重叠的函数而应用。它只是用一系列更复杂的预测试来替换你的双重嵌套循环。

- RBarryYoung

Answer 3

你可以将所有对象放在一个三维树结构中。然后，你只需要检查在某种意义上“接近”彼此的成对对象。

这是一种典型的存储空间信息的方式。例如，neo4j空间在底层使用k树来存储位置并执行“接近”类型的查询。

- phil_20686