3D数学 - 仅保持一定数量的码数

Question

我试图从一大堆职位中确定如何缩小我的名单.

现在我有大约3000个位置(x,y,z),我想基本上保持彼此相距最远的位置(我不需要保持100个位置,彼此相距2码半径).

除了做蛮力方法和字面上做3000 ^ 2比较,有没有人有任何想法如何我可以进一步缩小这个列表？

我对如何从数学角度处理这个问题感到困惑.

Answer 1

好吧,我不记得这个算法的名称,但我会告诉你一个有趣的技术来处理这个.我假设在3D环境中存在点的半随机散射.

简单版本:分而治之

1. 将您的空间划分为立方体的3D网格.每个立方体的每边都是X码.
2. 声明一个多维数组[x,y,z],使得网格中的每个多维数据集都有一个元素.
3. 数组的每个元素应该是顶点或对顶点(x,y,z)结构的引用,并且每个元素应该默认为NULL
4. 遍历数据集中的每个顶点,确定顶点所在的多维数据集.
   • 怎么样？好吧,你可以假设(5.5,8.2,9.1)顶点属于MyCubes [5,8,9],假设X(cube-side-length)大小为1.注意:我只是将小数/浮点数截断为确定哪个立方体.
5. 检查顶点是否已经采用了相关的立方体.检查:如果MyCubes [5,8,9] == NULL然后(注入我的顶点)别的(什么都不做,扔掉它!现场拍摄,好友)

让我们节省一些内存

这将在一次通过中为您提供一个非常简化的数据集,但代价是可能存在大量内存.

那么,如何在不使用太多内存的情况下做到这一点？

我在上面的示例中使用哈希表使得我的键是Grid-Cube坐标(5,8,9).

 If MyHashTable.contains({5,8,9}) then DoNothing else InsertCurrentVertex(...)

现在,您将拥有一个具有最小内存使用量的一次性解决方案(没有可能有大量空方块的巨大阵列.成本是多少？嗯,设置结构/类的编程时间,以便您可以执行.包含HashTable(或您的语言等效)中的操作

嘿,我的结果很粗壮!

这是对的,因为我们采用了适合任何立方体的第一个结果.平均而言,我们将实现顶点之间的X分离,但是正如您现在可以弄清楚的那样,一些顶点仍将彼此靠近(在立方体的边缘处).

那么,我们该如何处理呢？好吧,让我们回到顶部的数组方法(内存密集型!).

而不是仅检查顶点是否已存在于多维数据集中,而是执行此其他检查:

 If Not ThisCubeIsTaken()
    For each SurroundingCube
      If not Is_Your_Vertex_Sufficiently_Far_Away_From_Me()
         exit_loop_and_outer_if_statement()
      end if
    Next
    //Ok, we got here, we can add the vertex to the current cube because the cube is not only available, but the neighbors are far enough away from me
 End If

我想你可能会看到它的美丽,因为如果你有一个3D阵列,很容易得到相邻的立方体.

如果你像这样进行一些平滑处理,你可以强制执行'不要添加,如果它是0.25X'政策或其他东西.您不必太严格,无法获得明显的平滑效果.

还是太矮胖了,我想要它顺利

在此变体中,我们将更改允许顶点是否在多维数据集中驻留的限定操作.

 If TheCube is empty OR if ThisVertex is closer to the center of TheCube than the Cube's current vertex
    InsertVertex (overwrite any existing vertex in the cube
 End If

注意,我们不必为此执行邻居检测.我们只是优化每个立方体的中心.

如果您愿意,可以将此变体与之前的变体合并.

作弊模式

对于这种情况下的某些人,您可以简单地随机选择10%的数据集,这将是一个很好的简化.然而,它会非常厚实,有些点非常接近.从好的方面来说,最多需要几分钟.除非你是原型,否则我不推荐它.