用于在给定距离内查找所有地理点的Android算法

Question

在我幼稚的开始Android头脑中，我认为做到这一点的方法是循环检查每个对象是否接近X范围内，如果包含对象。这是通过Google Maps和GeoPoints完成的。

这就是说，我知道这可能是最慢的方式。我搜索了Android Proxmity算法，并没有真正得到很多。我所寻找的是与此相关的最佳选择，效率更高。

有没有我找不到的图书馆？

如果不是，我应该将这些位置对象加载到SQL中，然后从那里去或将它们保存在JSONArray中？

一旦我建立了我的最佳数据结构，他最好的方法是找到所有位于X英里用户的位置？

我不是要求剪切和粘贴代码，而是最有效的方法。然后，我可以绊倒代码:)

我的第一个直觉是按地区对地点进行分组，但我不确定如何执行此操作。

我可能有数以万计的数据点。

任何帮助只是在正确的方向前进非常感谢。

作为一个便笺，我发现我使用的一个远程API是.. well ..只是PLAIN WRONG并忽略了我的邻近搜索中的数据点。我也意识到，如果只是放在手机上的数据点上，那么我可以允许用户在没有互联网连接的情况下运行应用程序，只有GPS，这将是一个巨大的优势。所以，所有的挫折都是机会！

Answer 1

答案取决于GeoPoints的表示：如果这些没有排序，您需要扫描所有这些（这是在线性时间内完成的，排序wrt。distance或clustering会更加昂贵）。使用Location.distanceTo(Location)或Location.distanceBetween(float, float, float, float, float[])来计算距离。

如果GeoPoints被排序了wrt。距离你的位置这个任务可以更有效地完成，但由于供应商不知道你的位置，我认为这是不可能完成的。

如果GeoPoints是聚类的，即如果您有一组具有某个中心和半径的聚类，请选择每个聚类，其中您的位置到聚类中心的距离在极限和半径之内。对于这些群集，您需要检查群集中包含的每个GeoPoint（其中一些可能距离您的位置远远超出限制允许的范围）。或者，您可能会接受该错误并包括集群的所有点（如果半径相对较小，我会推荐这一点）。