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. >> >> > -- 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.
