Comparing distances between geopoints fast

Question

I have a (very long) list of points that I display in a map. I need to calculate the distance from each one to a user-inputted point, and sort the list from the nearest to the farthest.

Right now I'm doing it this way:

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 actually returns the square of the actual distance between two points, because I thought that comparing the square would give the same result as comparing the actual value, and it was a lot faster since I didn't need to make that square root.

However, it's still slow (it's a LONG list) and I'd really appreciate some ideas to accelerate the process. I pre-calculate the distances before sorting so I don't calculate each distance more than once, but I can't think of any other improvement. Is there something I'm missing?

Answer 1

You can divide things up among multiple treads, e.g. use four threads and calculate the distances for the first 1/4 of the points using thread1, for the second 1/4 of the points using thread2, etc. Just be sure that SparseArray#put is thread-safe (I don't know what library you're using for this) - if you need to put a lock around the put method then the program may actually run slower if you split it among multiple threads.

Using single-precision instead of double-precision floating point computation will also speed things up a bit. If you only care about a fixed precision (e.g. two decimal points of precision) then you can use fixed point arithmetic instead, which essentially uses integer arithmetic.

Depending on what your program is doing, you may be able to delay computing the distances to the further points - for example, if you're displaying points to your user 25 at a time, then you can determine the closest 100-or-so points, and then wait to calculate the next 100-or-so points until after the user has scrolled to the 75-100 points; the user may only care about the first 25 points anyway, in which case you never have to compute the distances for the further points. To do this you'll need to index your points using a range tree or k-d tree so that you can quickly determine the closest points to the query point without having to iterate through the entire list; if your points are in a database then you can perform a range query instead. Note that in either case the tree / query is finding the closest points according to their Manhattan distances (delta-lat + delta-lon, instead of delta-lat^2 + delta-lon*2), so you'll still need to calculate their cartesian distances.