比较一个基础坐标与 n 个坐标列表并确定最接近的 m 个坐标的最佳算法是什么？

Question

我现在有一些代码。它可以处理小到中等大小的列表，但是当列表的大小n > 5000时，我的算法在移动设备上运行几乎需要1分钟。基本上，我正在将Java中的Coordinate对象与Coordinate对象的列表（Vector）进行比较。

以下是我的基本算法：

- 遍历列表nx中的每个元素 - 如果“10个最接近”的列表中少于10个项目，则将nx添加到该列表中并继续下一个元素 - 如果“10个最接近”的列表已经有10个项目，则计算nx和基本坐标之间的距离 - 如果距离小于“10个最接近列表”中最远的距离，则从该列表中删除最远的项目并用nx替换它

我一直在看这个问题，并试图找到更有效的方法。这有点像排序算法问题，因此必须有更好的方法。

以下是我的距离计算方法：

public static double distance(double lat1, double lon1, double lat2, double lon2, char unit) {

  double theta = lon1 - lon2;

  double dist = Math.sin(deg2rad(lat1)) * Math.sin(deg2rad(lat2)) + Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * Math.cos(deg2rad(theta));

  dist = acos(dist);

  dist = rad2deg(dist);

  dist = dist * 60 * 1.1515;

  if (unit == 'K') {

    dist = dist * 1.609344;

  } else if (unit == 'N') {

    dist = dist * 0.8684;

    }

  return (dist);

}

- Steve C

---

@Steve C - 如果你的算法实现正确，即使N = 100000，它也应该非常快。 - Petar Minchev

@Petar Minchev 请注意，这是在嵌入式设备上运行的，可能比个人电脑慢得多。 - starblue

这更像是一个使用 GPS 的程序，从数据库中拉取 5000 家酒吧的列表，并计算出最近的 10 家酒吧的位置。 - Steve C

嗯，如果可以的话，您能否提供调用此方法并迭代列表的代码？ - thejh

这5000家酒吧所在区域的大致尺寸是多少？您预计该程序使用的实际最大和最小纬度是多少？ - Maciej Hehl

Answer 1

您可以将您的坐标存储在一些空间划分树中。

或者，采用更简单的方法，您可以使用一个二维桶数组，并首先检查最近的桶，直到找到足够的最近邻。 如果坐标均匀分布，则此方法效果很好。 编辑： 为了比较距离，您可以预先计算球上的三维坐标，并在比较中使用欧几里得距离的平方：

dx * dx + dy * dy + dz * dz

- starblue

---

这是我的距离计算算法。它非常精确，但我在想，当只计算列表中最接近的10个时，我可能不需要那么高的精度： - Steve C

public static double distance(double lat1, double lon1, double lat2, double lon2, char unit) { double theta = lon1 - lon2; double dist = Math.sin(deg2rad(lat1)) * Math.sin(deg2rad(lat2)) + Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * Math.cos(deg2rad(theta)); dist = acos(dist); dist = rad2deg(dist); dist = dist * 60 * 1.1515; if (unit == 'K') { dist = dist * 1.609344; } else if (unit == 'N') { dist = dist * 0.8684; } return (dist); } - Steve C

哦，可怜的嵌入式设备。你一定应该考虑简化它。最好将其编辑到问题中，以便更易读。 - starblue

Answer 2

也许使用数组会更快。而且你可以比较距离的平方而不是距离本身，这意味着你不必处理平方根。

最好提供实际的代码。

- thejh

Answer 3

你可以尝试使用类似这个网站的方法来限制需要计算距离的点的数量。

该网站展示了如何计算一个点和给定距离的纬度、经度边界坐标。虽然这不是你所面临的完全相同的问题，但它可以作为一个过滤器。在你的情况下，你显然正在尝试找到离给定点最近的10个（或n个）点。你可以应用以下算法来找到最近的10个（或n个）点：

对于前n个点，您可以通过完整的距离计算来保存每个点的距离。保存最长的距离。按照上面网站中所示的方式计算纬度和经度边界框。继续处理其余的点。如果任何一个点在纬度和经度边界框之外，则它不能比当前10个最近点中的任何一个更接近。如果它在边界框内，则计算距离。丢弃先前10个“最近”点中最远的点。根据新的最远点重新计算纬度和经度边界框。重复此过程，直到处理完所有点。

这种方法的好处是，您可能能够避免大量计算大量点的情况。根据您的点的分布情况，您仍然可能会遇到性能不佳的问题，例如如果点的顺序使它们按距离从远到近排序（point [0]是最远的，point [N]是最近的）。

- wageoghe