我想为我的MKAnnotations. 目前，当我尝试根据距离标准过滤它们时，速度非常慢（3-4k 个位置，目前使用简单的双精度非常慢for......）。
我想创建MKAnnotations, 的集群来决定它是否靠近另一个。此外，这些位置在某种程度上是（创建）顺序，并且需要“上一个”/“下一个”功能来“跳转”（这不是必须的）。我已经阅读了kd-tree和r-tree结构，它们似乎都满足过滤/聚类的快速距离/邻居获取选项，但我不确定哪个最适合我，或者是否还有其他选项。我应该使用什么算法/数据结构？
更新：我将这些位置存储在核心数据数据库中，它们代表一条路径。当地图打开时，它们被提取到一个数组中，然后我只使用该数组进行距离计算和注释创建。当用户移动/缩放地图时，我会遍历它们并决定需要在地图上更改哪些内容，因此整个内容都是静态的。据我了解，如果我使用一棵树，我可以将位置存储在那里，当发生缩放/移动时，我只需搜索它并获取新区域中的位置。这是真的 ？
即使在动态情况下，当我可以向该数组添加新位置时，它也将是一次插入，并且很少发生。
这在很大程度上取决于您的使用模式（我的写入方式，例如，在内存中或在磁盘上）以及您的数据看起来如何（这就是它的分布方式）。
R-trees 很好，因为它们是平衡的，并且允许更新。根据我的经验，R*-tree 显然比其他变体更好，因为它具有拆分策略。好处是它比其他策略产生更多的方形页面，因此对于许多查询，您将需要扫描更少的页面。
如果您在内存中并且是静态的，kd-trees 就很好。更新它们非常糟糕，您需要经常重建索引。
如果您的数据不经常更改，则 R-tree 的批量加载效果非常好。您可以进行Sort-Tile-Recursive批量加载，这本质上需要（部分）交替对 X 和 Y 上的数据进行排序，因此O(n log n)构建树的成本很低；与批量加载 kd-tree 非常相似，不同之处在于您是多拆分而不是二进制拆分。这很受欢迎。
此外，您可以跟踪每个页面中的对象数量。在地图上显示内容时，当页面在屏幕上显示得太小（即小于标记）时，您可能希望尽早停止。此时，您不会扫描该页面，而只会获取对象的数量并将其显示为集群标记，直到用户放大。
对于具有有限值域的二维数据，不要忽视简单的事情。四叉树也可以很好地工作！简单性可以使优化事物变得更加容易。或经典的网格方法。如果您的用户倾向于将他们的注释分散在一个区域中（而不是将它们全部放在一个地方），您可以只计算整数 x,y 网格坐标，然后对它们进行散列并为每个网格单元制作一个列表。
我不是 iOS 开发人员，但我查看了文档并发现了这一点：
MKMapView.annotationsInMapRect：
返回位于指定地图矩形中的注释对象。
(NSSet *)annotationsInMapRect:(MKMapRect)mapRect参数
- mapRect：您要搜索注释的地图部分。
返回值 位于 mapRect 中的注释对象集。
讨论 此方法提供了一种快速检索地图特定部分中的注释对象的方法。这种方法比你自己对 annotations 属性中的对象进行线性搜索要快得多。
这表明NKMapView已经在空间索引结构中组织了注释。这种方法能满足您的需求吗？
如果没有，我会寻找任何 2D 空间索引结构的现有开源实现，并选择具有最佳文档、最干净接口等的开源实现，而不用担心效率。如果您需要从头开始编写代码，我认为四叉树将是最容易实现的。另一方面，关于 R-tree 的 Wikipedia 文章似乎比 KD Tree 或 Quadtree 更专门针对映射。