我应该使用哪种空间索引算法？

Question

我应该使用哪种空间索引算法？

iosalgorithmmkannotationkdtreespatial-index

9

我想为我的MKAnnotations实现一种空间索引数据结构。目前，当我尝试根据距离标准（3-4k的位置）进行筛选时，它非常缓慢（目前使用简单的双重for循环...）。我想创建MKAnnotations的聚类，以确定它是否靠近另一个。此外，这些位置有一定的（创建）顺序，并且需要“上一个”/“下一个”功能来“跳转”（这不是必须的）。我已经了解了kd-tree和r-tree结构，它们似乎都可以满足快速获取距离/邻居的选项以进行过滤/聚类，但我不确定哪个对我最好，或者是否还有其他选择。我应该使用什么算法/数据结构？更新：我将这些位置存储在Core Data数据库中，它们表示路径。打开地图时，它们被提取到一个数组中，然后我只是使用该数组进行距离计算和注释创建。当用户移动/缩放地图时，我遍历它们并决定需要在地图上更改什么，因此整个过程都是静态的。据我所知，如果我使用树，我可以将位置存储在那里，当发生缩放/移动时，我只需搜索它，并获得新区域中的位置。这是真的吗？即使在动态情况下，当我可以将新位置添加到此数组时，它也只会进行单个插入，并且发生得很少。

- Templar

2个回答

0

我不是iOS开发人员，但是我查看了文档并找到了这个内容：

MKMapView.annotationsInMapRect:

返回指定地图矩形区域内的注释对象。

(NSSet *)annotationsInMapRect:(MKMapRect)mapRect

参数

mapRect：您要搜索注释的地图部分。

返回值 位于mapRect中的注释对象集合。

讨论此方法提供了一种快速检索特定地图部分中的注释对象的方法。该方法比自己线性搜索annotations属性中的对象要快得多。

这表明NKMapView已经将注释组织在空间索引结构中。这个方法是否符合您的需求？

如果没有，我会寻找现有的开源实现任何2D空间索引结构，并选择具有最佳文档、最干净的接口等方面的那个，而不必担心效率。如果您需要从头编写代码，我认为四叉树是最容易实现的。另一方面，R-tree的维基百科文章似乎比K-D Tree或Quadtree更专门针对地图制作。

- japreiss

这种方法的主要问题是，它仅用于检索，而我想在将位置添加到地图之前进行基于距离的过滤。实现不是问题，但我不想实现我不需要的东西 :) - Templar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Has QUIT--Anony-Mousse · Accepted Answer

这很大程度上取决于您的使用模式（例如，内存中或磁盘上的写入方式）以及您的数据外观（即分布方式）。R树很好，因为它们是平衡的，并且允许更新。根据我的经验，R*树明显比其他变体更好，因为它具有更好的分裂策略。好处在于它产生比其他策略更多的正方形页面，因此对于许多查询，您将需要扫描较少的页面。

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

而且，如果您的数据不经常更改，则R树的批量加载效果非常好。您可以进行“Sort-Tile-Recursive”批量加载，这基本上要求您交替对X和Y进行（部分）排序，因此构建树需要低的O（n log n）；与批量加载kd树非常相似，只是您进行多路分割而不是二进制分割。这非常受欢迎。

此外，您可以跟踪每个页面中的对象数量。当在地图上显示事物时，如果页面太小（即小于标记），则可能希望提前停止。此时，您将不会扫描该页面，而只会获取对象数量并将其显示为聚合标记，直到用户放大。

对于有限值域的二维数据，请不要忽视简单的事物。四叉树也可以很好地工作！简单性可以使优化变得更加容易。或者采用经典的网格方法。如果您的用户倾向于在一个区域中散布他们的注释（而不是将它们全部放在一个地方），则可以计算整数x，y网格坐标，然后对它们进行哈希并为每个网格单元创建列表。