查找具有类似值的数组

我使用Javascript。我有一个三维空间点的数组，我希望点不要非常接近数组中的其他点。我的意思是，我希望点之间的距离大于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;  
      } 
     } 
    } 
}

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

来源

2012-11-19 Dimitris

该算法的输入是什么，以及期望的输出是什么？从你的问题规范你可以完全重新分配一些预先定义的稀疏集，但我不认为这是你想要的。 –

http://en.wikipedia.org/wiki/Collision_detection –

输入是三维空间中的点，我想保留它们的X，Y坐标，并且只在必要时才将它们移动到Z维中。 – Dimitris

针对每个点每个点相比确实是最简单的，所以你的算法是一个良好的开端。

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

对于静态点（那些不移动的），制作一棵树使得您只需走几个父节点并检查其子节点（距离较近的子节点）就很简单。这也被称为R树，其他选项也存在。

这也适用于3D为好。

_{两个图像都来自维基百科。}

从视觉上你可以看到它变得更加简单了，你只需检查你的半径内的方框，你最终以这种方式做很少的工作。

对于动态点（移动的点），保留这样一个详细的R树可能是不可行的。因此，我们必须逐步降低细节水平，并在你的方法和R树之间寻找一些东西，例如制作稍大的盒子就是一种方法。

其他方法涉及使用四边形（每次将一个立方体划分为4个较小的立方体，只要它包含一个点）和一个网格（您可以创建大量相同大小的立方体）。你可以阅读更多关于R树和其他结构here，它可以很好地作为对它们的介绍。

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

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

来源

2012-11-19 22:49:53

感谢您的快速回答，这些维基百科页面是从哪个页面中获取的？ – Dimitris

R树和测地网格。 –

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

由于您只能通过更改Z尺寸来移动点，我首先想到的是按Z尺寸值对点进行排序，并且只比较在Z尺寸上接近的点。但我仍然不知道如何划分区域。

来源

2012-11-20 03:47:23 Richard

查找具有类似值的数组

回答

相关问题