Ok, now I've created an open project at bitbucket with a public issue
tracker so put any of your ideas/comments/bugs there.

https://bitbucket.org/weholt/django-locationbase

As mentioned I'll look more into this during this weekend and release
something next week if I get it working properly. The current
implementation doesn't rely on heavy math operations and seems to be
database agnostic, only using the orm. This is old code and worked
using sqlite. Not sure how well it plays against postgres or mysql.

Thanks for your attention once again.

Thomas



On Fri, Aug 12, 2011 at 12:28 PM, Thomas Weholt <thomas.weh...@gmail.com> wrote:
> Hi all,
>
> This is what I've come up with so far. Not tested, but I came across
> an old piece of code doing the same thing ( I knew I'd done it before,
> just had to look deep into my code archives ;-) ):
>
> http://dpaste.com/592639/
>
> Comments very welcome. Expect a pypi-release some time after the
> weekend. Perhaps there's more things features we could add too, like
> google maps integration, some form of widget to use in the admin etc.
> Feel free to steal the code or suggest ideas.
>
> Thomas
>
> On Fri, Aug 12, 2011 at 10:33 AM, Mike Dewhirst <mi...@dewhirst.com.au> wrote:
>> Thomas
>>
>> Don't know if this helps but one degree of latitude is sixty nautical miles
>> at the equator and slightly less at the poles. Not worth worrying about.
>>
>> OTOH, one degree of longitude shrinks from 60 NM at the equator to zero at
>> the poles - which might help you visualize the necessary math.
>>
>> I bet Google has worked all this out before..
>>
>> Good luck - and I'm interested in the result.
>>
>> Mike
>>
>> On 12/08/2011 5:51pm, Thomas Weholt wrote:
>>>
>>> Thanks for your detailed reply :-) I'll try to figure it out. So far I
>>> got a few candidates for a solution but the math functions seem to be
>>> somewhat different on the different database platforms so I need to
>>> experiment some more to find one that works on the three major ones (
>>> sqlite, postgres and mysql - I often use sqlite for development and
>>> postgres for production myself, but still want to support mysql ).
>>>
>>> About the accuracy; my app is suppose to show photos take nearby some
>>> location so it doesn't have to be dead on. But this should really be a
>>> reusable app or widget. Seems like more than just me needs this
>>> functionality. If I get something going I'll look into making it
>>> generic and reusable. Anybody interesting in helping out making this
>>> happen please let me know. My experience using math functions in SQL
>>> like this is close to zero.
>>>
>>> Thanks alot for all the replies and interest :-)
>>>
>>> Regards,
>>> Thomas
>>>
>>> On Thu, Aug 11, 2011 at 7:51 PM, Bill Freeman<ke1g...@gmail.com>  wrote:
>>>>
>>>> I've done this sort of thing in the past without the aid of geo-django,
>>>> using a
>>>> reasonably ordinary model.
>>>>
>>>> I did it as a two step process, first calculating a bounding box, which
>>>> is a
>>>> rectangle in lat/long space.  It is calculated once per search, based on
>>>> the distance and the coordinates of the distance circle's center (the
>>>> point
>>>> from which you are measuring distance).
>>>>
>>>> A pair of latitudes that are tangent to the distance circle are easy to
>>>> come
>>>> by because the point of tangency is at the same longitude as the circle's
>>>> center, and because distance in linear with latitude along such a line.
>>>>
>>>> Bounding longitudes are harder because their points of tangency are
>>>> closer to the pole than the circle's center (unless it's on the equator),
>>>> as well as distance not being linear with longitude change.  But since
>>>> a distance circle radius through the point of tangency will necessarily
>>>> intersect the bounding line of longitude at a right angle, you can use
>>>> one of the spherical right triangle formulas.  I like:
>>>>   sin(a) = sin(A) * sin(c)
>>>> where the triangle includes the pole, the point of tangency, and the
>>>> center
>>>> of the distance circle; "a" is the angle, measured as seen from the
>>>> center
>>>> of the earth, subtended by the side not involving the pole, that is of
>>>> the
>>>> distance radius (2*PI*distance/earth_radius); "c", the hypontenuse, is
>>>> the same thing for the distance between the distance circle's center and
>>>> the pole, that is, the compliment of the latitude of the distance
>>>> circle's
>>>> center; and A is the surface angle subtended at the pole, that is, the
>>>> difference in longitude (what we're looking for).  Because it would be
>>>> convenient to work in latitude, rather than compliment of latitude,
>>>> change
>>>> the formula to:
>>>>  sin(a) = sin(A) * cos(lat)
>>>> therefore:
>>>>  A = asin(sin(a)/cos(lat))
>>>> The desired bounding longitudes are then +/- A from the longitude of
>>>> the distance circle's center's longitude.  It doesn't hurt that the use
>>>> of cos(lat) has even symmetry, making it clear that you don't have to
>>>> choose a pole.
>>>>
>>>> Now you select candidate database rows satisfying the bounding limits,
>>>> and only have to calculate actual distance for them, discarding the
>>>> relatively few that are too far, but within the corners of the bounding
>>>> box.
>>>> Some databases support a "BETWEEN" operator, or something like it,
>>>> but the ORM's range lookup will work.  Be careful, though, if your circle
>>>> can include 180 degrees of longitude, since then you want longitude to
>>>> be outside the range, rather than within it, because the sign of
>>>> longitude
>>>> changes there.
>>>>
>>>> Note that if a pole is closer than your distance limit that there are no
>>>> bounding longitudes, and only that bounding latitude that's further from
>>>> that pole applies.
>>>>
>>>> In the interests of performance, note that the distance formula:
>>>>   d = 2*PI*earth_radius*acos(sin(lat1)*sin(lat2) +
>>>>              cos(lat1)*cos(lat2)*cos(long1 - long2))
>>>> only needs the sin and cos of the latitudes, not the latitudes
>>>> themselves.
>>>> So that's what I stored in the database avoiding those trig operations
>>>> on each distance calculation.  (Actually, I wound up also storing the
>>>> latitude so that the user saw the latitude he had entered, whereas,
>>>> given the non-infinite precision of float, or even double, doing
>>>> asin(sin_lat) leads to some differences in less significant digits.)
>>>>  Then
>>>> we get:
>>>>  d = 2*PI*earth_radius*acos(sin_lat1*sin_lat2 +
>>>>              cos_lat1*cos_lat2*cos(long1 - long2))
>>>> and we're down to just two trig functions per distance calculation, a cos
>>>> and an acos.
>>>>
>>>> Further, notice that for distance less than or equal to half way around
>>>> the
>>>> globe (which is as far as you can get on the globe), acos(x) is, while
>>>> not
>>>> linear, monotonic(ly decreasing) with x.  So throwing out the candidates
>>>> that are in the corners of the bounding box can be done using the
>>>> the expression inside the acos, by comparing it to:
>>>>  a = cos(d/(2*PI*earth_radius))
>>>> and discarding points where:
>>>>  a<  sin_lat1*sin_lat2 + cos_lat1*cos_lat2*cos(long1 - long2)
>>>> taking us down to one trig operation for those.  (Yes, I have the
>>>> inequality
>>>> correct: cos == 1 implies 0 distance, and cos gets smaller as you get
>>>> further until you are as far away as possible, on the other side of the
>>>> globe.)
>>>>
>>>> Note that you can even sort by the cos of the distance angle (the thing
>>>>
>>>> And, yes, "a" is the "a" from the bounding box calculation, so you only
>>>> have
>>>> to calculate it once per look up.  In fact, if you only offer a limited
>>>> set of
>>>> distances, you can calculate "a" for each of them once, at startup.
>>>> being compared to "a"), largest first to get smallest distance first.
>>>>
>>>> Most databases will support such expressions, so if you are willing to
>>>> execute SQL directly
>>>> (https://docs.djangoproject.com/en/1.3/topics/db/sql/)
>>>> you can get the database to calculate the cos of the distance angle, do
>>>> the
>>>> compare on it, and also sort by it.  The trick is to avoid doing the
>>>> calculation
>>>> for points outside the bounding box, and you will have to know your
>>>> database
>>>> well to do that (a stored procedure may be in order).  You also don't
>>>> want
>>>> to sort before you've winnowed, so there may be a sub-query (or so)
>>>> involved.
>>>>
>>>> You might even be able to do it using the "raw" model manager method,
>>>> though
>>>> having calculated the cos of the distance angle, and assuming that you
>>>> will
>>>> want to display the distance to each candidate, you would like to have it
>>>> returned, and it's not a model field.
>>>>
>>>> Python should be just as fast as the database on the trig, but decreasing
>>>> the
>>>> number of items that get passed over the database connection, and that
>>>> then
>>>> must be instantiated as model instances in django, is a performace
>>>> benefit.
>>>>
>>>> Good luck.
>>>>
>>>> On Thu, Aug 11, 2011 at 11:09 AM, Thomas Weholt<thomas.weh...@gmail.com>
>>>>  wrote:
>>>>>
>>>>> I got a model with longitude and latitude and want to be able to find
>>>>> other objects nearby a selected object. Can this be done using the
>>>>> django orm? What is the best approach to do this in a django project?
>>>>>
>>>>> I found a answer on Stackoverflow, but doesn't work with sqlite. Doing
>>>>> it in SQL is ok and probably the best solution performance wise, but
>>>>> if it has to be done in python I'll do that too.
>>>>>
>>>>> Ref question on stackoverflow:
>>>>>
>>>>> http://stackoverflow.com/questions/4610717/django-determining-if-geographic-coordinates-are-inside-of-an-circle
>>>>>
>>>>> --
>>>>> Mvh/Best regards,
>>>>> Thomas Weholt
>>>>> http://www.weholt.org
>>>>>
>>>>> --
>>>>> 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+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/django-users?hl=en.
>>>>>
>>>>>
>>>
>>>
>>
>> --
>> 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+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/django-users?hl=en.
>>
>>
>
>
>
> --
> Mvh/Best regards,
> Thomas Weholt
> http://www.weholt.org
>



-- 
Mvh/Best regards,
Thomas Weholt
http://www.weholt.org

-- 
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+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/django-users?hl=en.

Reply via email to