Filter zipcodes by proximity in Django with the Spherical Law of Cosines

Question

I'm trying to handle proximity search for a basic store locater in Django. Rather than haul PostGIS around with my app just so I can use GeoDjango's distance filter, I'd like to use the Spherical Law of Cosines distance formula in a model query. I'd like all of the calculations to be done in the database in one query, for efficiency.

An example MySQL query from The Internet implementing the Spherical Law of Cosines like this:

SELECT id, ( 
    3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * 
    cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * 
    sin( radians( lat ) ) ) 
) 
AS distance FROM stores HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;

The query needs to reference the Zipcode ForeignKey for each store's lat/lng values. How can I make all of this work in a Django model query?

Answer 1

It's possible the execute raw SQL queries in Django.

My suggestion is, write the query to pull a list of IDs (which it looks like you're doing now), then use the IDs to pull the associated models (in a regular, non-raw-SQL Django query). Try to keep your SQL as dialect-independent as possible, so that you won't have to worry about one more thing if you ever have to switch databases.

To clarify, here's an example of how to do it:

def get_models_within_25 (self):
    from django.db import connection, transaction
    cursor = connection.cursor()

    cursor.execute("SELECT id, ( 
        3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * 
        cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * 
        sin( radians( lat ) ) ) )
        AS distance FROM stores HAVING distance < 25
        ORDER BY distance LIMIT 0 , 20;")
    ids = [row[0] for row in cursor.fetchall()]

    return MyModel.filter(id__in=ids)

As a disclaimer, I can't vouch for this code, as it's been a few months since I've written any Django, but it should be along the right lines.

Answer 2

Just to follow up on jboxer's answer, here's the whole thing as part of a custom manager with some of the hard-coded stuff turned into variables:

class LocationManager(models.Manager):
    def nearby_locations(self, latitude, longitude, radius, max_results=100, use_miles=True):
        if use_miles:
            distance_unit = 3959
        else:
            distance_unit = 6371

        from django.db import connection, transaction
        cursor = connection.cursor()

        sql = """SELECT id, (%f * acos( cos( radians(%f) ) * cos( radians( latitude ) ) *
        cos( radians( longitude ) - radians(%f) ) + sin( radians(%f) ) * sin( radians( latitude ) ) ) )
        AS distance FROM locations_location HAVING distance < %d
        ORDER BY distance LIMIT 0 , %d;""" % (distance_unit, latitude, longitude, latitude, int(radius), max_results)
        cursor.execute(sql)
        ids = [row[0] for row in cursor.fetchall()]

        return self.filter(id__in=ids)

Answer 3

Following jboxer's response

def find_cars_within_miles_from_postcode(request, miles, postcode=0):

    # create cursor for RAW query
    cursor = connection.cursor()

    # Get lat and lon from google
    lat, lon = getLonLatFromPostcode(postcode)

    # Gen query
    query = "SELECT id, ((ACOS(SIN("+lat+" * PI() / 180) * SIN(lat * PI() / 180) + COS("+lat+" * PI() / 180) * COS(lat * PI() / 180) * COS(("+lon+" - lon) * PI() / 180)) * 180 / PI()) * 60 * 1.1515) AS distance FROM app_car HAVING distance<='"+miles+"' ORDER BY distance ASC"

    # execute the query
    cursor.execute(query)

    # grab all the IDS form the sql result
    ids = [row[0] for row in cursor.fetchall()]

    # find cars from ids
    cars = Car.objects.filter(id__in=ids)

    # return the Cars with these IDS
    return HttpResponse( cars )

This returns my cars from x amount of miles, this works well. However the raw query returned how far they were from a certain location, i think the fieldname was 'distance'.

How can i return this field 'distance' with my car objects?

Answer 4

To follow up on Tom's answer, it won't work in SQLite by default because of SQLite's lack of math functions by default. No problem, it's pretty simple to add:

class LocationManager(models.Manager):
    def nearby_locations(self, latitude, longitude, radius, max_results=100, use_miles=True):
        if use_miles:
            distance_unit = 3959
        else:
            distance_unit = 6371

        from django.db import connection, transaction
        from mysite import settings
        cursor = connection.cursor()
        if settings.DATABASE_ENGINE == 'sqlite3':
            connection.connection.create_function('acos', 1, math.acos)
            connection.connection.create_function('cos', 1, math.cos)
            connection.connection.create_function('radians', 1, math.radians)
            connection.connection.create_function('sin', 1, math.sin)

        sql = """SELECT id, (%f * acos( cos( radians(%f) ) * cos( radians( latitude ) ) *
        cos( radians( longitude ) - radians(%f) ) + sin( radians(%f) ) * sin( radians( latitude ) ) ) )
        AS distance FROM location_location WHERE distance < %d
        ORDER BY distance LIMIT 0 , %d;""" % (distance_unit, latitude, longitude, latitude, int(radius), max_results)
        cursor.execute(sql)
        ids = [row[0] for row in cursor.fetchall()]

        return self.filter(id__in=ids)