我正在开发一个项目,给定一组坐标(纬度和经度)需要找到比给定距离(以公里为单位)更近的所有点。
我有工作实现迭代每个点,每个点迭代所有其他点。这是 O(n^2)。我想知道我可以采用什么方法来改进这一点,考虑到我不想要最近的点,而是那些比 x Km 更近的点(我也希望能够做相反的事情,找到所有比 x 公里更远的点)。
如果能提供一些思路和算法就好了。代码示例也很好,特别是在 Scala 中(我正在开发这个项目 Scala)。
最佳答案
对于这个问题,我会使用 java 库(这在 Scala 中是可能的)。 计算地球上的距离比你想象的要困难得多。例如,地球不是一个完美的球体。 在 Java 中执行“地理信息”的主要库是 JTS:http://tsusiatsoftware.net/jts/main.html 您还可以查看 Geotools 或什至可能是像 PostGIS(基于 Postgresql 构建)这样的 GIS 数据库,但这对您的项目来说可能有点矫枉过正
关于algorithm - 计算比给定距离更近的点数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13476965/