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

Question

假设有 n 个 3 维对象(多面体)。最快的方法是计算所有对象的交集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 步。

我错过了什么吗？这是我们能得到的最好的吗？

Answer 1

虽然有几种方法可以通过更改循环内容来提高 O(n²) 性能，但可以通过更改有关碰撞检查方式的其他内容来进行重大改进。

您的代码中的一个主要低效率是它依赖于针对每个其他多面体完全检查每个多面体的方式，这通常并不总是必要的。如果两个形状甚至不靠得很近，则不需要进行密集的相交测试，并且如果有两个形状簇被广阔的空间隔开，则不需要检查两个簇的每个成员另一个集群的每个成员。执行此类优化的一些技术包括:

• Locality-Sensitive Hashing
• Space Partitioning
• Bounding Volumes

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