4

我正在使用 Javascript。我有一个在 3d 空间中有点的数组，我希望这些点不要非常靠近数组中的其他点。我的意思是，我希望点之间的距离大于x. 现在我正在做的是有一个双循环比较距离并将点在 Z 维度上移动得更远，比如

while(there_are_objects_that_are_close){
    for(all_the_objects){
        for (all_the_objects){
            if (distance_between_them < 100){
                object[i].z += 150;      
            }
        }
     }
}

问题是我讨厌这个算法，它看起来很慢，我正在寻找更好的解决方案。如果您有一个解决方案，它也是具有文学背景的“有名字的算法”，我会更感激它，因为这是我们学校项目的一部分。

4

2 回答 2

4

将每个点与每个点进行比较确实是最简单的，因此您的算法是一个好的开始。

这样做的缺点是，当点的数量变得巨大时，算法将开始表现得很糟糕，因为它必须将每个点与所有点进行比较，而大多数点并不接近。在这种情况下，您可能希望以仅检查可能足够接近的点的方式拆分点。

对于静态点（那些不移动的点），制作一棵树是微不足道的，这样您只需遍历几个父节点并检查其子节点（距离较近的子节点距离更近）。这也称为 R 树，也存在其他选项。

这也适用于 3D。

两张图片均来自维基百科。

从视觉上你可以看到它变得更加简单，你只需选中你半径内的框，你最终会做更少的工作。

对于动态点（那些移动的点），保持如此详细的 R 树存在可能是不可行的。因此，我们将不得不降低细节级别，并在您的方法和 R 树之间寻找一些东西，例如，制作稍大的框是一种方法。

其他方法包括使用四边形（每次将一个立方体分成 4 个较小的立方体，只要它包含一个点）和一个网格（创建许多大小相同的立方体）。您可以在此处阅读有关 R 树和其他结构的更多信息，它可以很好地作为对它们的介绍。

例如，它的派生是将地球分割成三角形的测地线网格，尽管这可能不适用于 3D（除非您将三角形与地球中间的顶点连接起来）。

图片来自维基百科。

于 2012-11-19T22:49:53.310 回答
0

需要找到一种方法将点分成更小的区域进行比较。

由于您只能通过更改 Z 维度来移动点，所以我的第一个想法是按 Z 维度值对点进行排序，并且只比较 Z 维度上接近的点。但是我仍然不知道如何划分区域。

于 2012-11-20T03:47:23.847 回答