Geo-indexing: efficient latitude / longitude proximity calculation

Question

My simple web application (WSGI, Python) supports text queries to search for items in a database. Now I would like to expand this to allow queries such as "find all items within 1 mile of {lat, long}".

Of course, hard work if efficiency is a problem, so I am thinking of a dedicated external module that does indexing for geo-coordinates - sort of like Lucene for text.

I assume that such a common component already exists, but have not found anything yet. Any help would be greatly appreciated.

Answer 1

You checked mongo db, they have geoinformation indexing function. http://www.mongodb.org/display/DOCS/Geospatial+Indexing

Answer 2

I could only think of an attack with semi-brute force if you plan to implement it directly with Python, which I already did for similar purposes:

#!/usr/bin/python from math import * def distance(p1,p2): # uses the haversine function and an ellipsoid model lat1, long1 = p1; lat2, long2 = p2 lat1=radians(lat1); long1=radians(long1); lat2=radians(lat2); long2=radians(long2) maior=6378.137; menor=6356.7523142 R=(maior*menor)/sqrt((maior*cos(lat1))**2 + (menor*sin(lat1))**2) d_lat = lat2 - lat1; d_long = long2 - long1 a = sin(d_lat/2)**2 + cos(lat1) * cos(lat2) * sin(d_long/2)**2 c = 2 * atan2(sqrt(a), sqrt(1-a)) length = R * c x = sin(d_long) * cos(lat2) y = cos(lat2) * sin(lat1) - sin(lat2) * cos (lat1) * cos(d_long) bearing = 90-(degrees(atan2(y, -x))) return length, bearing 

To screen points for distance, you can first find candidate points whose x and y coordinates are inside the square located in the center of your test position (much faster), and just check the actual distance to the geodesic.

Hope this helps!