如何从坐标列表中计算给定点最近的坐标。

Question

基本上，我有用户的当前位置。然后我有一组坐标列表。

我应该如何计算最接近用户当前位置的一组坐标？我的应用程序是为 Android 平台编写的 Java 语言。

- molleman

---

你大概知道你的集合中会有多少个坐标吗？这可能会影响到是否可以使用暴力方法或者它是否会太慢。 - chillysapien

你好，有200个坐标需要测试当前位置。 - molleman

针对200个坐标，不必过于担心。只需测试它们所有，很可能比你所能优化的任何方法都更快更简单。 - LiKao

Answer 1

如果列表中的点在该区域内分布均匀，那么应该可以使用以下方法：

将该区域划分为一定大小的象限。保留并更新每个象限内的点的列表。

给定坐标x，找到它所属的象限，仅计算同一象限内的点的距离（如果没有，则将相邻象限中的点添加到该象限中，直到成功），选择k个最近的点p_i。

检查圆c（中心为x，半径为max(p_i-x)）是否穿过尚未检查的任何象限，如果是，则计算与那些象限中的点的距离。返回所有最接近的k个点的集合。

而不是选择圆c中的所有象限，您可能希望检查包含点的c中最接近的象限，直到找到k个最接近的点p_i，使得c(x，max(p_i-x)) 中的所有象限为空或已检查。

将最近象限搜索从O(n)加速到O(log n)：您需要实现类似树状结构的东西：四个象限的象限，等等，以跟踪每个象限中的点数。当点移动时，更新它（O(log)）。无论如何，对于200个点来说，这可能是过度杀伤性的。

编辑：不要使用“树形结构”，而是使用哈希表和简单的哈希函数，例如：（x除以10^p，y除以10^p）

- macieksk

Answer 2

http://developer.android.com/reference/android/location/Location.html

Location location = new Location("");
location.setLatitude(lat);
location.setLongitude(lon);

检查是否存在distanceTo或distanceBetween方法。

或者您可以手动计算坐标之间的距离，并找到最小距离进行计算。有关计算距离的信息，请参考以下链接http://www.zipcodeworld.com/samples/distance.java.html

- ingsaurabh

Answer 3

有一种分治算法可以在O(nlogn)的时间复杂度内找到最接近的点对。虽然它可能对于你的数据集大小有些过头了。此处有更多信息

- Kakira