ios - 组织地理引用数据的最佳方式是什么？

Question

我有几个位置，每个位置都有纬度和经度，我需要找到离给定点最近的位置。我可以使用 Core location 来查找从点到位置的距离，但我的算法效率很低(简单地枚举每个位置，计算距离并跟踪最低值)。在某些点上工作正常，但当你达到 100,000 点时，事情开始吱吱作响。

组织数据的最佳方法是什么，以便我可以快速确定离给定点最近的位置以及给定位置是否在指定矩形内？

我知道游戏玩家使用树结构进行快速碰撞测试，但我是树结构的新手，想知道如何开始？ iOS 中是否有任何合适的树结构，或者我是否必须构建自己的树结构？

提前致谢。

Answer 1

我会使用一种 Quadtree .随着像元大小的增加，在网格中组织您的 map 。如果按点查找附近，则查看具有最小单元格的网格中的相邻单元格，如果没有找到，则在下一个较粗网格中的相邻单元格中搜索。

这并不完美，因为网格总是指向 Manhatten distance但你可以获得最近点的优秀候选人。对于每个候选人，您需要计算您感兴趣的实际距离。