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
Person.objects.filter(THRESHOLD_gt=
((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),
}
THRESHOLD = 10
near_people = annotated_people.filter(
distance__lt=THRESHOLD**2
)

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.

-tim

--
You received this message because you are subscribed to the Google Groups "Django users" group.
To post to this group, send email to django-users@googlegroups.com.
To unsubscribe from this group, send email to django-users+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/django-users?hl=en.