java - 将基坐标与 n 坐标列表进行比较并确定最接近的 m 坐标的最佳算法？

Question

我现在有一些代码可以执行此操作。它适用于中小型列表，但当我有一个大小为 n > 5000 的列表时，我的算法在移动设备上可能需要将近 1 分钟才能运行。我主要是将 Java 中的 Coordinate 对象与 Coordinate 对象列表(Vector)进行比较。

这是我的基本算法:

• 遍历列表nx中的每个元素
• 如果“10 个最接近”列表中的项目少于 10 个，则将 nx 添加到列表中 并转到下一个元素
• 如果“10 closest”列表已经有 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);

}

Answer 1

您可以将您的坐标存储在一些 space partitioning tree 中.

或者，对于更简单的方法，您可以使用二维桶数组，并首先检查最近的桶，直到找到足够多的最近邻居。这仅在坐标分布均匀时才有效。

编辑:要比较距离，您可以预先计算球体上的 3D 坐标并在比较中使用欧氏距离的平方:

dx * dx + dy * dy + dz * dz