4

假设有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 步。

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

4

3 回答 3

3

信不信由你，我已经在 StackOVerflow 上有效地回答了这个问题，这里：https ://stackoverflow.com/a/19172550/109122 。问题和答案适用于多边形（2D），但它应该同样适用于多面体（3D）。

那里的问题还提到了被认为是最快的算法，即 Hoey Shamos 扫描线技术，即 O(n Log n)。您可以研究并实施它，但它非常复杂。

我在回答中演示的更简单的算法具有高度依赖于形状及其位置的“行为良好”的性能。形状越狂野，它们的包装/重叠越密集，它的性能就越差。但是，对于表现良好的形状（即凸形或大多数形状），交叉点很少且包装不太密集，我发现它的性能优于 O(n sqrt(n))。那里的代码和讨论主要是关于两个多边形内的线，但这也适用于多边形本身。

除了相对简单之外，我的方法对您的情况的最大优势在于，它可以独立于您用来检测两个多边形之间重叠的任何函数而应用。它只是用更复杂的一系列预测试取代了你的双重嵌套循环。

于 2014-06-27T21:36:20.827 回答
3

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

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

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

于 2014-06-27T19:39:32.150 回答
0

您可以将所有对象放在 3D 树结构中。然后你只需要检查在某种意义上彼此“接近”的对。

这是存储空间信息的典型方式。例如，neo4j 空间在引擎盖下有 ak 树，用于存储位置和执行“接近”类型查询。

于 2014-06-27T22:16:09.403 回答