所以我试图解决一个问题。我有一个可以作为玩家的点，我周围有几个物体，有些更远，有些靠近呃。例如，我想排除所有较远的点并包括较近的使用距离。如何对对象进行聚类或过滤。我正在考虑空间分区。对象位于地理坐标中。对象的数量可以是 10.000
问问题
103 次
1 回答
0
如果允许每一个点移动，更新对于 kd-trees 或类似的自适应结构可能会变得昂贵。我想我会采用静态分区方法，例如将空间划分为一组单元格（二次或矩形），并为每个单元格存储对所包含点的引用以及所包含点集的最大和最小坐标。当点移动时，您可以简单地计算它们所在的当前单元格。在计算距离时，您只需确定相关单元格，然后使用线性时间计算到它们所包含点的距离。
我看到了这种方法的三个基本优势：
通过查看每个单元格当前包含的最小和最大坐标，您可以轻松确定其是否为空，如果不是，则整个包含点集与您的玩家当前位置相关。
您可以将静态单元组织成具有完美平衡的树结构（例如四叉树）。对于树的每个内部节点，您存储并更新其子节点的组合最小和最大坐标。请注意，更新非常便宜，因为树的结构根本不受影响。
您不需要对您的观点进行排序（因为其他结构或特定实现需要这样做）。如果对象快速移动，这可以为您节省大量性能。
构建和维护数据结构很简单。你不必用奇异的测试用例和复杂的结构更新来破坏你的大脑。
当然，选择非自适应数据结构有一些缺点，因为它是非自适应的。例如，您高度依赖网格单元的大小。如果你选择的太小（最坏的情况：每个单元格一个点），树的深度就会膨胀并且遍历变得昂贵。另一方面，如果您选择的太大（最坏的情况：在某些时候，所有点都在同一个单元格中），您将执行许多不需要且可能很昂贵的距离计算。
总而言之，这实际上取决于您拥有的数据类型。我给你的建议应该会产生相当好的结果，但可能有更有效的方法来做到这一点。如果您有足够的时间，请同时实施自适应和静态分区方法，提出一些具有代表性的测试并将它们相互比较。
希望这可以帮助 ;）
于 2017-01-05T12:38:14.937 回答