Saturday, January 7, 2012

Mysql fastest distance lookup given latitude/longitude


Recently I have developed an Android application, which is an LBS(location-based services) application. This application is in Chinese, but the name in English is "Hong Kong chain store" (香港連鎖店). I have got a list of branch in my database, and the app can help user to find out all branch nearby.

The question is, how to retrieve the distance between user location and branch location in the most fastest way. I think most of people just store the latitude and longitude of the location in database. And the code loop through the whole database and calculate the distance record by record. But running the code by this method is very time consuming. We need a much more faster way.

I have google around and got the answer in stackoverflow. However, I found that there is some typo in the answer, and it is not a complete answer. So right now I make a summary to tackle this question.

I assumed that you have got the latitude(lat) and longitude(lng) point of your locations in database. But this is not enough, you should open one more field that store a geo point of the location(latlng) and create a spatial index on it. Here is the SQL statement to make this field when you create the table,
CREATE TABLE geom (latlng GEOMETRY NOT NULL, SPATIAL INDEX(latlng)) ENGINE=MyISAM;
Please note that the field [latlng] should be in GEOMETRY type. If you have already create the field, you can use ALERT command to create spatial index.
CREATE SPATIAL INDEX sp_index ON geom (latlng);
Then, run the following SQL to update [latlng] field.
UPDATE geom SET latlng = POINT(lat, lng)
OK, that is all the things for database. Here is the PHP script in your code. Assume that you have to find all locations not more then 0.5km distance.
$orglng = $_GET["user_lng"];
$orglat = $_GET["user_lat"];
$distance = 0.5;

$pt1 = $orglat + $distance / ( 111.1 / cos($orglat));
$pt2 = $orglng + $distance / 111.1;
$pt3 = $orglat - $distance / ( 111.1 / cos($orglat));
$pt4 = $orglng - $distance / 111.1;

$qry = "SELECT  * ";
$qry .= "FROM geom ";
$qry .= "WHERE MBRContains(GeomFromText('LineString(".$pt1." ".$pt2.", ".$pt3." ".$pt4.")'), latlng)";
Here is what you need! Test it yourself now.

Happy coding!

Book you may feel interested:
Related Posts Plugin for WordPress, Blogger...