So I’m finally building out Stikki.me’s advertising system, and I’ve realized I might need some help with a geometric sorting algorithm.
Stikki’s advertising is geographically-based; an advertiser “sponsors” a location — most likely the real-world location of their business — with an ad, and users see that ad if they’re within a given radius of the location. The sponsor selects the radius, and pricing for the ad is based upon that radius. (The value of this sort of advertising, by the way, is that the advertiser knows that the user is within reasonable physical proximity of their business, and is therefore capable of patronizing it.)
So here’s what I have to do; when a Stikki user visits Stikki, their geolocation is passed (but not stored) to an AJAX script which returns the correct ads for that location, and that’s where my knowledge of geometric algorithms breaks down. I don’t know what the most elegant way to determine this is.
I’m currently using a two-pass approximate sorting scheme that looks something like this:
- retrieve subset of all ads where ad’s latitude/longitude is within 5 kilometers of the user’s current position (5km being a wide enough radius to contain all possible current ads),
- within this subset, calculate minimum and maximum lat/long for each ad based on ad’s lat/long +/- ad’s radius and see if user’s lat/long is within it. If so, return ad.
But I don’t know if this is the most efficient way to calculate this, especially if/when I begin to get larger numbers of ads — more than 1000, say.
This same geometric algorithm is used to determine if a user is in proximity to one of their “alert” stikkis as well.
Anybody have any practical suggestions/advice for this? I could spend the next few weeks learning about collision detection/sorting algorithms, but I’d rather get pointed in the right direction by somebody more versed in geometric algebra than I am.
OK… step one implies you already have a system for determining the distance between an ad and a customer. So if that’s true, your second step is just muddying the waters. The solution is simply
if (customerDistanceFromAd < sponsoredRadius) useThisAd()
If you don’t already have a system for determining the distance (because step one is being solved for you by some external module that keeps that information to itself) then you’ll need to calculate that distance. Using min/max latitude and longitude (as you suggest) is getting you a square box around the ad rather than the circle which is implied by ‘radius’.
If the world were two-dimensional, this would be easy. Given:
(adlong, adlat) = Sponsored ad location (custlong, custlat) = Customer’s location
The distance from between the customer and the ad* is sqrt((userlong-adlong)^2 + (userlat-adlat)^2). That gives you a distance in degrees which, presumably you need to convert into km. So, if you could depend on your customers all living on the equator, your code would look like this:
DegreesDistance = sqrt((userlong-adlong)^2 + (userlat-adlat)^2) KmDistance = DegreesDistance*111.32 if (KmDistance < sponsoredRadius) useThisAd()
Alas, degrees of longitude change size depending on your latitude. So to use our Euclidian distance formula on the non-Euclidian earth, let’s start out by transforming latitude and longitude into simple kilometers-from-Greenwich before we start. A degree of latitude is just 111.32 km, so that’s easy. The formula for the length of a degree of longitude is a bit uglier.*
usery = userlat * 111.32 userx = cos(userlat) * 111.32 ady = adlat * 111.32 adx = cos(adlat) * 111.32 KmDistance = sqrt((userx-adx)^2 + (usery-ady)^2) if (KmDistance < sponsoredRadius) useThisAd()
Even for thousands of ads, running that bit of code shouldn’t be especially expensive. Computers are good at math. If, however, for some reason it turns out that computing the real distance is too slow, then… well, to be honest, then I would use something like your second solution, only I would cache those minimum & maximum latitudes in the database so that each pass just does a fetch and a comparison and no math at all. And then I’d figure out some way to make my advertisers feel cozy about the fact that I’m displaying adds to some ‘bonus’ customers in the corners of those squares.
** I’m presuming that you are on a continent that does not intersect either the equator or the prime meridian. If you’re in the UK or Ecuador or Somalia &c. you’ll have to do something clever with the boundary conditions, or rotate the world 90 degrees to eliminate those boundaries.
*** Cribbed from this discussion, here: http://ask.metafilter.com/99539/What-equation-should-I-use-to-calculate-the-number-of-miles-in-a-degree-of-longitude-for-a-given-latitude
just break it down into grids. each square contains a link to every possible advert that could be seen in that square.
Um… sorry, the linebreaks in my post got mangled, as well as a couple of footnotes being garbled. I hope that my explanation is intelligible anyway…