Android how to get 10 closes geopoint from current position

Question

Let say I have my current position.

I also have 400 other geopoint.

I'd like to find out what are the 10 closest geopoint.

What I'd like to avoid is to go through all the 400 points and compare the distance between 2 geopoint.

Is there a way do get this information more efficiently? Maybe something exposed throught the mapview? or mapviewcontroller?

Answer 1

Instead of comparing distances, compare "the square of the distance".

If you are at x0, y0, get the points whose (xn - x0)² + (yn - y0)² are the lowest. This way you can obtain the nearest points avoiding squared toots (computationally expensive), and you will have to do just sums (differences) and products, which are cheap in computation terms.

If you need the distances, get the square roots only of the 10 selected nearest points.

Answer 2

excuse me, but how you determine if the 10 geopoints you choose are the closEST if you do not verify all of them?

You might detect 10 "reasonably close" points without checking them all, just fill a buffer with the first 10 points close to you in the list you fetched from the data source which are within a certain range (lets say 10 miles?)

this way you get some very close points and the speed will get a boost. Of course, when you gain from a side, you must leave from another. So it is speed vs accuracy imho.