javascript - 在数组中查找具有相似值的数字

Question

我在 Javascript 工作。我有一个在 3d 空间中包含点的数组，我希望这些点不要非常靠近数组中的其他点。我的意思是，我希望点之间的距离大于 x。现在我正在做的是有一个 double for 循环比较距离和移动 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;      
            }
        }
     }
}

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

Answer 1

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

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

对于静态点(那些不移动的点)，制作一棵树很简单，您只需遍历几个父节点并检查其子节点(距离越近的子节点越近)。这也称为 R 树，还存在其他选项。

这也适用于 3D。

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

从视觉上您可以看到它变得更加简单，您只需选中您半径范围内的框，这样您最终可以少做很多工作。

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

其他方法涉及使用四边形(每次将一个立方体分成 4 个较小的立方体，前提是它包含一个点)和网格(您创建许多大小相同的立方体)。您可以阅读更多关于 R 树和其他结构的信息 here , 它很好地介绍了它们。

例如，它的一个衍生物是将地球分成三 Angular 形的测地线网格，尽管这可能不适用于 3D(除非您将三 Angular 形与地球中间的顶点连接)。

_{图片来自维基百科。}