我正试图从一大组位置中确定如何大幅缩小我的列表。
现在我有大约3000个位置（x，y，z），我想基本上保持彼此相距最远的位置（我不需要保持100个位置，它们都在2码半径内）。
除了用蛮力法和3000^2的比较外，有人知道我该如何进一步缩小这个列表吗？
从数学的角度来看，我有点困惑。
好吧，我记不起这个算法的名字了，但我会告诉你一个处理这个问题的有趣技巧。我假设在三维环境中存在点的半随机散射。
简单版本：分而治之
- 将您的空间划分为立方体的三维网格。每个立方体的每侧都有X码
- 声明一个多维数组[x，y，z]，以便为网格中的每个多维数据集都有一个元素
- 数组的每个元素都应该是顶点或对顶点（x，y，z）结构的引用，并且每个元素都默认为NULL
- 遍历数据集中的每个顶点，确定顶点位于哪个立方体中。
- 如何？好吧，你可以假设（5.5，8.2，9.1）顶点属于MyCubes[5，8，9]，假设X（立方体边长）的大小为1。注意：我只是截断了小数/浮点数来确定哪个多维数据集
- 检查相关多维数据集是否已被顶点占用。检查：如果MyCubes[5,8,9]==NULL，则（注入我的顶点）其他（什么都不做，扔出去！当场得分，伙计）
让我们节省一些内存
这将一次性为您提供一个非常简化的数据集，但代价可能是大量内存。
那么，如何在不占用太多内存的情况下做到这一点呢？
我会使用一个哈希表，这样我的键就是上面示例中的网格立方体坐标（5,8,9）。
If MyHashTable.contains({5,8,9}) then DoNothing else InsertCurrentVertex(...)
现在，您将有一个内存使用率最低的一次性解决方案（没有可能有大量空多维数据集的巨大数组。成本是多少？好吧，设置结构/类的编程时间，这样您就可以在HashTable（或等效语言）中执行.contains操作
嘿，我的成绩太棒了
没错，因为我们得到了第一个适合任何立方体的结果。平均而言，我们将实现顶点之间的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%的随机选择，这将是一个足够好的简化。然而，它会很粗，有些点靠得很近。从好的方面来说，它最多需要几分钟。除非你正在制作原型，否则我不建议你这样做。