Thursday, July 29, 2010

Re: Best way to find near people

On 07/29/10 16:58, Alexandre González wrote:
> Hi!
> I'm searching near people in my app. I'm doing it a this way:
> 37 people = Person.objects.all().exclude(user=request.user)
> 38
> 39 near_people = list()
> 40 for person in people:
> 41 if self.is_near(me.coordinates, person.coordinates):
> near_people.append(person)
> Now, I'm getting all the the Person objects. This is a inefficient way.

You might be able to use F() objects and limit by the square of
the difference...but I can't figure out how to annotate an object
with a F()something like this (untested)

THRESHOLD = 10 # miles
((F('coordinates__x') - me.coordinates.x) *
(F('coordinates__x') - me.coordinates.x)) +
((F('coordinates__y') - me.coordinates.y) *
(F('coordinates__y') - me.coordinates.y))

However, it could be done with a .extra() call something like
(using "coord" instead of "coordinates" because I'm lazy)

x = float(user.coords.x) # or int() or whatever
y = float(user.coords.y)
people = Person.objects.exclude(user=user)
annotated_people = people.extra(select={
'distance': """
((coord.x - %s) * (coord.x - %s)) +
((coord.y - %s) * (coord.y - %s))
""" % (x, x, y, y),
near_people = annotated_people.filter(

It's using raw Python string interpolation which should be safe
with float() or int() for the user.coordinates and not open to a
SQL injection as a string would.

The normal distance calculation is sqrt(dx*dx + dy*dy) but you
can remove the often-expensive sqrt() calculation by simply
squaring the threshold (THRESHOLD**2) and comparing it to the sum
of the squares of the differences. (a little algebra/geometry there).

Alternatively, you could .order('-distance') and then slice those
results, taking the top 10 nearest or paginate them by distance
putting the nearest people at the front.


You received this message because you are subscribed to the Google Groups "Django users" group.
To post to this group, send email to
To unsubscribe from this group, send email to
For more options, visit this group at

No comments:

Post a Comment