CODEWITHSUNDEEP
geolocation
AnC
AnC

Reputation: 4211

geo-indexing: efficiently calculating proximity based on latitude/longitude

My simple web app (WSGI, Python) supports text queries to find items in the database. Now I'd like to extend this to allow for queries like "find all items within 1 mile of {lat,long}".

Of course that's a complex job if efficiency is a concern, so I'm thinking of a dedicated external module that does indexing for geo-coordinates - sort of like Lucene would for text.

I assume a generic component like this already exists, but haven't been able to find anything so far. Any help would be greatly appreciated.

Upvotes: 4

Views: 1372

Answers (2)

heltonbiker
heltonbiker

Reputation: 27615

I could only think of a semi-brute-force attack if you plan to implement it directly with Python, which I already did with 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

For the screening of points for distance, you can first find candidate points whose "x" and "y" coordinates are inside a square centered on your testing position (much faster) and just then test for actual geodesic distance.

Hope it helps!

Upvotes: 1

user781192
user781192

Reputation: 36

Have you checked out mongo db, they have a geo indexing feature. http://www.mongodb.org/display/DOCS/Geospatial+Indexing

Upvotes: 2

Related Questions