CODEWITHSUNDEEP
javaandroidandroid-mapview
Federico
Federico

Reputation: 5778

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

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?

Upvotes: 4

Views: 3762

Answers (4)

wurde
wurde

Reputation: 2617

Perhaps remove the calculation of the curvature of the earth..? If the functionality of your app permits this, do so.

This format always holds true. Given two points, you can always plot them, draw the right triangle, and then find the length of the hypotenuse. The length of the hypotenuse is the distance between the two points. Since this format always works, it can be turned into a formula:

Distance = sqrt( (x2 - x1)^2 + (y2 - y1)^2 )

Update with correct notation:

double distance = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));

Upvotes: 2

Ifor
Ifor

Reputation: 2835

So long as you don't need to cope with near the polls and an aproximation is OK which for grouping it should be. Then you can work out the relative scaling between the lattitude degrees and the longitude degrees just the once and use it for every straight X squared + y squared calculation, for relative distances you can skip the square root.

If your working with degrees to scale them to be the same relative distance for lattitude and longitude you use cos of the lattitude. I would scale the latitude to the longitude then each degrees map to a good knowen distance the calculation will will be something like.

(lattitude diference for two points) * 1/cos(latitude)

You work out the 1/cos(latitude) just the once for all points assuming the latitude is not changeing much over your sample set.

Upvotes: 2

Eimantas Kasperiūnas
Eimantas Kasperiūnas

Reputation: 318

As far as I know, best way to do this is to use Graph Theory, and it has Dikstra's algorithm , it's the fastest algorthm in my knowledge for this kind of task.

Really worth learning, optimizes work very well.

Upvotes: 0

CommonsWare
CommonsWare

Reputation: 1006869

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.

Upvotes: 6

Related Questions