1

我有一个（非常长的）我在地图中显示的点列表。我需要计算每个点到用户输入点的距离，并从最近到最远对列表进行排序。

现在我正在这样做：

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实际上返回两点之间实际距离的平方，因为我认为比较平方会得到与比较实际值相同的结果，而且它要快得多，因为我不需要平方根。

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

4

1 回答 1

1

您可以在多个踏板之间划分，例如使用四个线程并使用线程1计算前1/4点的距离，使用线程2计算第二个1/4点的距离，等等。只要确保这SparseArray#put是线程-安全（我不知道您为此使用的是什么库）-如果您需要在put方法周围加锁，那么如果您将其拆分为多个线程，程序实际上可能运行得更慢。

使用单精度而不是双精度浮点计算也会加快速度。如果您只关心固定精度（例如两个小数点精度），那么您可以改用定点算术，它本质上使用整数算术。

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

于 2013-05-30T14:31:15.863 回答