4

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?

Improve this question
4
  • so for each of the thousand points you need to calculate the distance to every other point? What is it that you are trying to achieve?
    – ninesided
    Commented Jan 3, 2012 at 23:20
  • See also Nick Johnson's Dijkstra post - really detailed info if that's your thing. stackoverflow.com/a/432854/1101070
    – Marvin Pinto
    Commented Jan 4, 2012 at 3:36
  • no, it's not every point to every other point. it's distance of every point to all cluster. for first(s) point(0s) cluster list is empty so creates one. Then compares distance if is less than X add it to cluster an recalculate center for cluster, if not create new cluster. for 1000 points it is not 1000^2, more like 1000*4
    – Federico
    Commented Jan 4, 2012 at 23:32
  • 1
    you can choose dijkstra algorithm. good description here stackoverflow.com/questions/39256309/…
    – Alex Filatov
    Commented Aug 31, 2016 at 21:36

4 Answers 4

Reset to default
6

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.

Improve this answer
4
  • I like this approach,but I kind of need to be able to say group everything that is closer than 5 KM. If I use pythagorean theorem, is there a way to get the result in meters, km etc. no metter curvature of the earth for accuracy. Any other way to accomplish the same?
    – Federico
    Commented Jan 5, 2012 at 16:22
  • @Federico: If your X and Y are in meters, the square root of the sum of the squares of those will be in meters. If your X and Y are in parsecs, the square root of the sum of the squares of those will be in parsecs. And so on.
    – CommonsWare
    Commented Jan 5, 2012 at 17:00
  • @Federico: If your longitude and latitude are in degrees, the square root of the sum of the squares of their differences will be in degrees. If your longitude and latitude are in microdegrees, the square root of the sum of the squares of their differences will be in microdegrees.
    – CommonsWare
    Commented Jan 5, 2012 at 19:34
  • 1
    For degrees latitude degrees are on a circumfirance of the earth scale longitude degrees are on a circumfirance based on the latitude. To combine them so you can use pythagurus to make a distance equivernel you need to scale one of them to match the other. My answer was implying you only need to work out the scaling factor once if not close to the polls.
    – Ifor
    Commented Jan 7, 2012 at 10:01
2

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.

Improve this answer
1
  • @lfor: can you explain how to scale lng/lat in order to use pythagourous?
    – Federico
    Commented Jan 7, 2012 at 13:57
2

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));
Improve this answer
1
  • Worked, remember the correct android notation to get a valid result: double distance = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
    – Pelanes
    Commented Jun 15, 2016 at 7:44
0

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.

Improve this answer
1
  • FOR some reason my link doesn't pushes, just copy it to you'r browser as it is
    – Eimantas Kasperiūnas
    Commented Jan 3, 2012 at 23:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.