ios - 我应该使用什么空间索引算法？

Question

我想为我的 MKAnnotations 实现一些空间索引数据结构之王。目前，当我尝试根据距离标准过滤它们时，速度非常慢(3-4k 个位置，目前使用简单的双 for ... 非常慢)。

我想创建 MKAnnotations 集群，以确定它是否接近另一个。此外，这些位置在某种程度上(创建)顺序，并且需要“上一个”/“下一个”功能在两者之间“跳转”(这不是必须的)。我读过关于 kd-tree 和 r-tree 结构的文章，它们似乎都满足过滤/聚类的快速距离/邻居获取选项，但我不是确定哪个最适合我，或者是否还有其他选择。我应该使用什么算法/数据结构？

更新:我将这些位置存储在 Core Data 数据库中，它们代表一条路径。本地图打开时，它们被提取到一个数组中，然后我只使用该数组进行距离计算和注释创建。当用户移动/缩放 map 时，我遍历它们并决定 map 上需要更改的内容，因此整个内容有点静态。据我所知，如果我要使用一棵树，我可以将位置存储在那里，当发生缩放/移动时，我只需搜索它并获得新区域中的位置。这是真的 ？

即使在动态情况下，当我可以向这个数组添加新位置时，它也只是一次插入，而且这种情况很少发生。

Answer 1

这在很大程度上取决于您的使用模式(我的写入方式，例如，在内存中还是在磁盘上)以及您的数据看起来如何(这就是它的分布方式) .

R 树很好，因为它们平衡，并且允许更新。根据我的经验，R*-tree 明显优于其他变体，因为它具有拆分策略。好处是它比其他策略产生更多的方形页面，因此对于许多查询，您需要扫描更少的页面。

如果你在内存中并且是静态的，kd-trees 是很好的。更新它们非常糟糕，您将需要经常重建索引。

如果您的数据不经常更改，则 R 树的批量加载效果非常好。您可以执行 Sort-Tile-Recursive 批量加载，这基本上需要(部分)在 X 和 Y 上交替对数据进行排序，因此它需要很低的 O(n log n) build 树；与批量加载 kd 树非常相似，不同之处在于你是多重拆分而不是二元拆分。这很受欢迎。

此外，您可以跟踪每个页面中的对象数量。在 map 上显示内容时，您可能希望在屏幕上显示的页面太小(即小于标记)时提前停止。此时，您不会扫描该页面，而只会获取对象的数量并将其显示为聚类标记，直到用户放大为止。

对于二维数据，值域有限，不要忽视简单的东西。四叉树也可以很好地工作!简单性可以使优化事情变得容易得多。或者经典的网格方法。如果您的用户倾向于将他们的注释散布在一个区域(而不是将它们全部放在一个地方)，您可以只计算整数 x,y 网格坐标，然后对它们进行哈希处理并为每个网格单元制作一个列表。