Get next N nearest Geo-Points

Question

I have in my android application a database table with geo pointes (lat and lon are decimal degree values), about 1000 points. And I need to select 20 nearest point to some given geo point.

I've found at Stackoverflow the answer how to compute distance between two geo points and was very happy, till I tried to write my query. I've found out, that it's not possible to use trignometrical functions in built-in sqlite of android.

But then I've got an Idea. I don't really need to compute a distance. The near a point is to another one the smaller difference in their geo coordinates should be.

How could I use this fact? Would it be enough to order saved points by (lat_0 - lat_n)^2 + (lon0-lon_n)^2, where lat_0 and lon_0 are geo coordinates of a given point?

Thank you,

Mur

UPD

So, the best way to get an answer for my question was to test approach I describe above.

It works pretty well but not really exactly compared to exact distance.

So if you just need to compute a distance, this solution is ok, but in my case I also needed to order stations by distance and couldn't use this solution.

My thanks go on John at CashCommons and Philip. Thank you guys

Answer 1

If your points are separated within a city (more or less), that approximation will work fine. The approximation falls apart if you go worldwide, though.

EDIT: Based on Philip's comment below, you should scale one of the components. Germany is about 50 degrees north latitude, so multiplying the longitude by (cos 50 deg) will do better.

Answer 2

Hmm... I'm not sure how that ordering would work? Wouldn't you need a different order for each point to indicate it's neighbors.

The simplest solution is to just iterate through all the points and compute the geometrical distance between the points. For 1000 points this should happen fairly fast.

The most optimized solution (in terms of retrieval speed) is to compute the neighbors of each point when you insert them in the database. For example you can keep the list of ids as a comma separate string and insert in the database?. Then when you need someones neighbors you do directly to them. However this is going to become a pain if you need to insert new points. Basically you'll need to re-compute the neighbors.

Answer 3

Yes. :-) The actual distance is sqrt( (lat_0 - lat_n)^2 + (lon0-lon_n)^2 ) but ordering by (lat_0 - lat_n)^2 + (lon0-lon_n)^2 is sufficient.