5

我试图从大量职位中确定如何显着缩小我的名单。

现在我有大约 3000 个位置（x，y，z），我想基本上保持彼此相距最远的位置（我不需要保持 100 个位置都在 2 码半径范围内） ）。

除了使用蛮力方法和字面上进行 3000^2 比较之外，有没有人知道如何进一步缩小这个列表？

我对如何从数学角度处理这个问题有点困惑。

4

1 回答 1

7

好吧，我不记得这个算法的名字了，但我会告诉你一个有趣的技术来处理这个问题。我假设在 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（立方体边长）的大小为 1。注意：我只是将小数/浮点数截断为确定哪个立方体。
  5. 检查该相关立方体是否已被顶点占用。检查： If MyCubes[5,8,9] == NULL then (inject my vertex) else (什么也不做，扔掉！当场拍下，伙计)

让我们节省一些内存

这将一次性为您提供一个非常简化的数据集，但代价是可能会占用大量内存。

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

我会使用一个哈希表，这样我的键就是上面示例中的 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%，这将是一个足够好的简化。但是，它会非常厚实，一些点非常接近。从好的方面来说，最多需要几分钟。我不推荐它，除非你是原型。

于 2013-02-12T00:51:41.727 回答