java - java：从给定的GPS位置查找最近的GPS位置

Question

我需要编写一个 java 程序来从给定的 GPS 位置中查找P，最近的一组（2 个位置）GPS 位置（来自一组 GPS 位置）是 GPS 位置。情况如图所示 这里所有标记的位置都是GPS位置。从给定的位置P，我想找到最接近的点集P，在这种情况下(B,C)。

如果有人可以分享与此相关的算法或代码片段，那将非常有帮助。

Answer 1

您必须计算 P 和所有其他点之间的距离，然后取最小值。这是显而易见的部分。

困难的部分是计算两个 gps 坐标之间的距离。GPS 使用 WGS84 测地线系统来表示地球上的点。还有不同的方法来计算~sphere 上的距离（loxodromic 距离和大圆距离是主要的）。欧几里得距离在球体上总是错误的（甚至不是很近），因为在非零纬度，1°Lat < 1°Lon...
请参阅使用 WGS84 椭球的距离进行自己的计算，或者如果您接受一个库，请参阅 GDAL会为你做的。

您可以使用 GDAL 转换其他测地线系统中的点表示。例如，您可以在平面测地线系统上投影点，然后使用 (x,y,z) 坐标，然后计算距离（或更好：平方距离 = x²+y²+z²）。

我认为 google map api 为 gps 坐标提供了一种易于使用的距离方法，如果您碰巧已经在使用它的话。

Answer 2

将点存储到列表中，然后找到相邻点或最小距离点。

这篇文章可能对你有帮助。

Answer 3

如果您正在寻找算法实现，请查看 R-Trees。它们可能是寻找点或边界框类型搜索的好方法。

有一个很棒的库我已经使用了一段时间，它对我来说很好，它实现了 R-Tree 算法。查看 JSI，Java 空间索引 ( http://jsi.sourceforge.net/ )。

我将把 API 的探索留给你。祝你好运！

Answer 4

您可能会考虑使用数据制作四叉树。这是一种表示二维空间数据的方法，可以轻松地在 log(n) 时间内进行最近邻查找。树的构造是 nlog(n) 但是，如果您需要考虑构造和最近邻居，那么您将具有 nlog(n) 复杂性。

为四叉树（它只是 kd 树的二维版本）找到最近邻算法应该不难。Wiki在这里对其进行了总体概述

如需进一步阅读，如果您需要将此扩展到任何其他数量的维度，您应该阅读KD Trees。

编辑：这让我很震惊，如果你需要构建四叉树，那么循环遍历所有其他点会更快，找到距离并跟踪最小的 2。如果你不确定找到距离回想三角形和勾股定理。