Dissecting Elevators Part 6: GeoDjango? We don’t need no stinkin’ GeoDjango

Being able to locate the nearest elevator was a must have feature for me. Being able to deploy using the free tier on Heroku was a nice to have feature. Luckily, I managed to find a way to do both: do the calculations client side in JavaScript.

Lucky for me, I found a post, Calculate distance, bearing and more between Latitude/Longitude points, with some JavaScript algorithms on how to get distances between two lat/long points. There’s no such thing as perfect distance algorithm, but if you start making assumptions about the shape of the Earth, you can get a pretty good guess. I implemented four different ways to calculating distance; each a tradeoff between accuracy and speed. The four ways being: the Haversine formula, the spherical law of cosines, the equirectangular projection (Pythagorean), and rectilinear (Taxicab) distance. For my own reference, I’m putting a copy of the JavaScript algorithms here:

// distance approximators
/** Converts numeric degrees to radians */
if (!Number.prototype.toRad){
  Number.prototype.toRad = function(){
    return this * Math.PI / 180;
  };
}

var distance = {
  R: 6371,  // kilometers
  haversine: function(lat1, lng1, lat2, lng2){
    var dLat = (lat2-lat1).toRad();
    var dLon = (lng2-lng1).toRad();
    lat1 = lat1.toRad();
    lat2 = lat2.toRad();

    var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
      Math.sin(dLon/2) * Math.sin(dLon/2) * Math.cos(lat1) * Math.cos(lat2);
    var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
    return distance.R * c;
  },
  spherical: function(lat1, lng1, lat2, lng2){
    lat1 = lat1.toRad();
    lat2 = lat2.toRad();
    lng1 = lng1.toRad();
    lng2 = lng2.toRad();
    return Math.acos(Math.sin(lat1)*Math.sin(lat2) +
      Math.cos(lat1) * Math.cos(lat2) *
      Math.cos(lng2 - lng1)) * distance.R;
  },
  pythagorean: function(lat1, lng1, lat2, lng2){
    lat1 = lat1.toRad();
    lng1 = lng1.toRad();
    lat2 = lat2.toRad();
    lng2 = lng2.toRad();
    var x = (lng2 - lng1) * Math.cos((lat1 + lat2) / 2),
        y = lat2 - lat1;
    return Math.sqrt(x * x + y * y) * distance.R;
  },
  taxicab: function(lat1, lng1, lat2, lng2){
    lat1 = lat1.toRad();
    lng1 = lng1.toRad();
    lat2 = lat2.toRad();
    lng2 = lng2.toRad();
    return (Math.abs(lat1 - lat2) + Math.abs(lng1 - lng2)) * distance.R;
  }
};

For more information about the first three distance metrics, you should check out the original post. You can see that the computational complexity for each algorithm decreases dramatically, from using trigonometry and a square root, to pure trig, to a simple trig and a square root, to basic arithmetic. The code for getting the ten closest buildings turned out pretty simple. Here, _data is a global array of all the buildings:

// Get the closest `Building`s to `lat` and `lng`.
//
// Modifies the global `_data` by storing the distance and also sorts it.
var closestBuildings = function(lat, lng){
  var metric = distance.spherical, x;
  for (var i = 0; i < _data.length; i++){
    x = _data[i];
    x.distance = metric(lat, lng, x.latitude, x.longitude);
  }
  // go ahead and sort in place.
  _data.sort(function(a, b){ return a.distance - b.distance; });
  return _data.slice(0, 10);
};

Evaluating the different distance metrics

Just to see what the difference was between the four different distance metrics, I compared the result of the same search. I picked an arbitrary point where there weren’t too many elevators so it would have to go out a long ways before getting 10 elevators. I like BBQ, so I picked a place in Lockhart, TX. To my surprise, not only did the Haversine, spherical law of cosines, and equirectangular projection give the same results in the same order, but they also gave the same distances to 4 significant digits (your results on the live site may look different from mine because of differences between the data on my local machine and the live site):

The results of the search using the taxicab metric were very not bad either. You can see that the taxicab metric punishes going diagonally:

They were even better (obviously) over shorter distances, as you can see in this comparison for downtown Austin:

You can see I got the same results in a slightly different order.

Trickery!

If you’re wondering how I got the map pins to go from A to J and match the labels on the legend, wonder no more. The answer is: I cheated. I created the map pins using the old Google charts API in my mapping code:

"http://chart.apis.google.com/chart?chst=d_map_pin_letter&chld=" +
        String.fromCharCode(65 + i) + "|" + pinColor,

If you vary i from 0 to 9, you get the letters A to J. The legend is an ordered list with the css: list-style: upper-alpha, which handles going from A to J on the map legend. Since both are built from the same source in the same order, they match up.

Conclusion

And there you have it. Basic closest point searches done client side. The nearly fully geocoded dataset with 23,205 buildings takes a megabyte to transfer, but it could be optimized. At launch, I only had a fraction of the buildings geocoded, so it was less than 150 kilobytes then. I may change the default distance metric from spherical to Pythagorean to get some more speed. It would be an interesting exercise to convert to GeoDjango and compare the distance results again.