Goodfoot is an app that shows you what’s good around you. It’s a collaboration between myself) and Dave Rupert, Reagan Ray, & Trent Walton of Paravel.

As the greatest things in life go, it all started over a plate of Mexican food.

Dave and I had gone out for some celebratory enchiladas at Chuy’s, after a pretty epic hack session working on Regggionals. (This was a few months back, of course)

“Yo, I have some questions about the Gowalla Spot search API”, Dave mentioned, his glasses glinting the reflection of the surrounding Elvis memorabilia.

“Hurghmgmeugmhmg”, I mumbled through a mouth full of refried beans. “Oh really? What are you trying to do?”

And that’s when he whipped out his iPhone and changed my world. For you see, that was my first Glimpse of Goodfoot (it was a jQTouch web app back then). “Walk, Bike, Drive”. It was genius. Dave is a genius with ideas like that. “We gotta get that on the app store, give it the native treatment”, said I.

And with that, we started on a journey that would take us over several months, a couple thousand lines of code, and more than 10k pixels of yeti images, which finally led us to this: the day of Goodfoot’s App Store release.

Goodfoot is pretty freaking cool, if you ask me. I’ve had the pleasure of using it during development, and it’s become an essential part of my day. Break my everyday routine; discover something new–I’ve loved using it, and I hope you will too.

A lot of y’all have asked how exactly Goodfoot works. Although I can’t show all of my cards, I thought you’d get a kick out of how we tackled one of the central features of the app: Walk, Bike, Drive.

Walk, Bike, Drive using Inverse Apollonian Gaskets

Central to Goodfoot is finding Spots within walking distance, biking distance, and driving distance, which can be visualized as concentric rings about the centroid, your current location.

We want to find the most popular spots around you, so set the order parameter to checkins+desc. Unfortunately, one of the constraints of the Gowalla API is that we can only request spots within a circle (passing a radius parameter) or a bounding box (passing se & nw parameters), but not rings (circle with a small, inner circle removed from it), which is what we want.

Alright, so let’s just ask for the outermost radius–simply ask for the entire geometry, take the results, and segment them according to their distance. Well, if your city is anything like Austin, you’re results will be pretty much like this:

The Spots we get back are clustered around downtown, with no love going out to farther-out Spots in driving distance. Paging through this query doesn’t do much better. We’d have to get a few hundred spots in this way to even begin filling out all of the sections. No dice.

What we’re shooting is an even spread, without one region. Something like this:

Barring a major overhaul to the Gowalla API (though possible for me, it would’ve been way too much hassle (and besides, isn’t that cheating, in a way?)), we’re going to have to bust out some clever geometry. We need a way to divide up the region in a way that won’t overly favor a single region.

There is a whole genre of geometric proofs and algorithms that fill shapes with circles, a process called packing. This is cool and all, but these algorithms work pack by starting with the largest fitting circle and recursively filling in the spaces with progressively smaller ones. Our situation has radii that grow as they extend to the boundaries.

What I came up with was an admittedly half-baked, non-optimal solution, but it worked pretty well in practice. Think of it as an endearing idiosyncrasy; a kernel of humanity to an octet stream.

Basically, we start with a single circle in the center. Next, we double the radius and spread 4 of those circles around the first circle such that intersections and empty spaces are minimized (favoring overlap over holes). Shift the period by π/2 radians, set the radius to triple the original again and do the same with 4 more circles. Rinse & Repeat.

Depending on the order of the function, we can divide up a circle evenly in this way across 1, 5, 9, 13, etc. circles, where each circle represents a separate API call. For Goodfoot, 9 was the magic number, offering the best balance of granularity, performance, and kindness to the Gowalla API.

From there, we chunk our results into their respective distances, filter out the lame stuff, and voila! – cool things around you, no matter where you are!