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.