java - 快速比较地理点之间的距离

Question

我有一个(很长)在 map 中显示的点列表。我需要计算每个点到用户输入点的距离，并从最近到最远对列表进行排序。

现在我正在这样做:

private List<Point> sortedPointList(LatLng ll, List<Point> pointList)
    SparseArray<Double> distances = new SparseArray<Double>();
    for (Point ll : pointList){
        double distance = calcDistance(ll.getLatLng(), point);
        distances.put(ll.getId(), distance);
    }
    Collections.sort(pointList, new Comparator<Point>(){

        @Override
        public int compare(final Tramo lhs, final Tramo rhs) {
            return distances.get(lhs.getId()).compareTo(distances.get(rhs.getId()));
        }
    });
    return pointList
}


private double calcDistance(LatLng ll1, LatLng ll2){
    final double lat1 = ll1.latitude;
    final double lon1 = ll1.longitude;
    final double lat2 = ll2.latitude;
    final double lon2 = ll2.longitude;
    final double lat = lat2-lat1;
    final double lon = lon2-lon1;
    final double squareLat = lat*lat;
    final double squareLon = lon*lon;
    final double squareDistance = squareLat+squareLon;
    return squareDistance;
}

calcDistance 实际上返回两点之间实际距离的平方，因为我认为比较平方会得到与比较实际值相同的结果，而且速度要快得多，因为我不需要求平方根。

但是，它仍然很慢(这是一个很长的列表)，我真的很感激一些加速这个过程的想法。我在排序之前预先计算距离，因此我不会多次计算每个距离，但我想不出任何其他改进。我有什么遗漏的吗？

Answer 1

您可以将事情分成多个步骤，例如使用四个线程并使用 thread1 计算前 1/4 点的距离，使用 thread2 计算后 1/4 点的距离，等等。只要确保 SparseArray#put 是线程安全的(我不知道您使用什么库) - 如果您需要在 put 方法周围加锁，那么如果您将其拆分到多个线程中，程序实际上可能会运行得更慢。

使用单精度而不是 double 浮点计算也会加快速度。如果您只关心固定精度(例如两位小数精度)，那么您可以使用 fixed point arithmetic相反，它本质上使用整数运算。

根据您的程序正在执行的操作，您可能能够延迟计算到更远的点的距离 - 例如，如果您一次向用户显示 25 个点，那么您可以确定最近的 100 个左右的点，然后等待计算接下来的 100 个左右的点，直到用户滚动到 75-100 个点；无论如何，用户可能只关心前 25 个点，在这种情况下，您永远不必计算后面的点的距离。为此，您需要使用 range tree 对您的点进行索引。或k-d tree这样就可以快速确定距离查询点最近的点，而不必迭代整个列表；如果您的点位于数据库中，那么您可以执行范围查询。请注意，在任何一种情况下，树/查询都会根据曼哈顿距离(delta-lat + delta-lon，而不是 delta-lat^2 + delta-lon*2)查找最近的点，因此您仍然需要计算它们的笛卡尔距离。