How to calculate distance between two points in Android FAST for MANY points

Question

I have around 1000 points. I'm trying to group this points base on distance. Im using the harversine formula, but it seems to be super slow. In android for 1000 points takes 4 seconds. In my local environment takes 60 ms.

I do not care about precession and the points are no more than 25 km apart.

Is there another formula I can use?

Answer 1

First, for items that close to each other, curvature of the Earth is not going to matter too much. Hence, you can treat it as flat, at which point you're looking at the Pythagorean Theorem for distance (square root of the sum of the squares of the x/y distances).

Second, if all you are doing is sorting/grouping, you can drop the square root calculation and just sort/group on the square of the distance. On devices lacking a floating point coprocessor, such as the first couple of generations of Android phones, that will do a lot of good right there.

Third, you don't indicate the coordinate system you are using for the points, but if you can do your calculations using fixed-point math, that too will boost performance, particularly on coprocessor-less devices. That's why the Google Maps add-on for Android uses GeoPoint and microdegrees rather than the Java double degrees in the Location you get back from LocationManager.