Tem*_*lar 8 algorithm kdtree spatial-index mkannotation ios
我想为我实现一些空间索引数据结构之王MKAnnotations.目前,当我尝试根据距离标准过滤它们时非常慢(3-4k的位置,目前非常慢,只有一个简单的双for...).
我想创建群集MKAnnotations,以确定它是否接近另一个群集.此外,这些位置处于某种(创建)顺序,并且需要"先前"/"下一步"功能来"跳跃"(这不是必须的).我已经阅读了有关kd-tree和r-tree结构的信息,它们似乎都满足了过滤/聚类的快速距离/邻居获取选项,但我不确定哪种选择最适合我,或者是否还有其他选项.我应该使用什么算法/数据结构？
更新:我将这些位置存储在Core Data数据库中,它们代表一个路径.打开地图时,它们被提取到一个数组中,然后我只使用该数组进行距离计算和注释创建.当用户移动/缩放地图时,我会遍历它们并确定需要在地图上更改的内容,因此整个内容都是静态的.据我所知,如果我要使用树,我可以在那里存储位置,当发生缩放/移动时,我只搜索它并获得新区域中的那些.这是真的 ？
即使在动态情况下,当我可以向此数组添加新位置时,它也只是一次插入而且很少发生.
这在很大程度上取决于您的使用模式(我的写入方式,例如内存中或磁盘上)以及数据的外观(就是它的分布方式).
R树很好,因为它们是平衡的,并且允许更新.我的经验中的R*-tree明显优于其他变体,因为它具有分裂策略.好处是它产生比其他策略更多的方形页面,因此对于许多查询,您将需要扫描更少的页面.
如果你在内存和静态,kd树是好的.更新它们非常糟糕,您需要经常重建索引.
如果您的数据不经常更改,则R树的批量加载可以很好地工作.您可以进行Sort-Tile-Recursive批量加载,这实际上需要(部分)对X和Y上的数据进行交替排序,因此O(n log n)构建树时需要较低的值; 非常类似于批量加载kd树,除了你多次拆分而不是二进制拆分.这很受欢迎.
此外,您可以跟踪每个页面中的对象数量.在地图上显示内容时,您可能希望在页面上显示的页面太小(即小于标记)时提前停止.此时,您不会扫描该页面,而只会获取对象的数量并将其显示为聚簇标记,直到用户放大为止.
对于具有有限值域的2D数据,不要忽略简单的事物.Quadtrees也可以很好地工作!简单性可以使优化事物变得更加容易.或者是经典的网格方法.如果您的用户倾向于在一个区域中传播他们的注释(而不是将它们全部放在一个地方),您可以只计算整数x,y网格坐标,然后哈希它们并为每个网格单元格创建一个列表.