Adaptive Synergy

At NabeWise, maps are a major part of what we do. Earlier in the year we switched our preview maps from Google Static Maps to our own system that draws them on a canvas element. The results are very good and help provide better context at a glance. Recently we tweaked our algorithm to make these maps more attractive. In this blog post, I will cover how to do this with all the gory code and math to match. This is a very math heavy process, but I am probably worse at math than the average reader, so it should not get too much in the way.

The only dependency beyond Javascript and a browser with good Canvas support is the excellent underscore.js library. In the code, when you see ‘_.’, we’re using underscore to make iteration and functional manipulation less painful.

For the full code check here: https://gist.github.com/838963

Our primary neighborhood boundaries are in GeoJSON format, while other information like bounding boxes is stored in arrays of [latitude, longitude] ordered pairs. The core geometric component of our boundaries is a MultiPolygon. This is just a collection of Polygons each of which have one or many paths composed of ordered pairs. The first thing we need to do is project the geospatial coordinates into standard x,y Cartesian space. The Mercator projection is used by Google Maps and works especially well for smaller regions like cities. The code for this is:

/* Container for Mercator transformations */
CanvasMap.Mercator = {
  /* Transforms a geographic point in format [lng, lat] to cartesian coordinates */
  transform: function(point) {
    var lat = point[1],
        lng = point[0];

    var x = (lng*Math.PI/180) + Math.PI*2,
        y = (Math.log(Math.tan(lat*(Math.PI/180)) +
            (1/Math.cos(lat*(Math.PI/180))))) + Math.PI*2;

    return [x, y];
  },

  transformPath: function(path) {
    return _.map(path, CanvasMap.Mercator.transform);
  }
};

An important thing in this code, is that we’re making all coordinates positive. This simplifies some of the math and is just one less thing to worry about.

Mapping involves a lot of operations on geometric objects, so we need a few basic utility classes to make life easier for us. Everything depends on bounding boxes, so they have the most functionality. The methods defined here are just standard geometric things that you learn (and soon forget) pretty early on in school.

/* Constructs a bounding box from an array of ordered_pairs in cartesian space.
 * The standard case for a bounding box is a 2 element array with some variation on
 * [[left, top], [right, bottom]] or some other such scheme
 */
CanvasMap.BoundingBox = function(ordered_pairs) {
  var t = this;
  var c = CanvasMap;
  this.maxX = _.max(ordered_pairs, function(point){ return point[0]; })[0];
  this.maxY = _.max(ordered_pairs, function(point){ return point[1]; })[1];
  this.minX = _.min(ordered_pairs, function(point){ return point[0]; })[0];
  this.minY = _.min(ordered_pairs, function(point){ return point[1]; })[1];

  this.centerX = this.minX + (this.maxX - this.minX)/2;
  this.centerY = this.minY + (this.maxY - this.minY)/2;

  this.overlaps = function(bbox) {
    return (t.minX < bbox.maxX && t.maxX > bbox.minX &&
           t.maxY > bbox.minY && t.minY < bbox.maxY);
  };

  this.area = function() {
    return (this.maxX - this.minX)*(this.maxY-this.minY);
  };

  this.contains = function(bbox) {
    return bbox.minX >= t.minX && bbox.minX <= t.maxX &&
           bbox.minY >= t.minY && bbox.minY <= t.maxY &&
           bbox.maxX >= t.minX && bbox.maxX <= t.maxX &&
           bbox.maxY >= t.minY && bbox.maxY <= t.maxY;
  }

  this.canContain = function(bbox) {
    var a = new c.BoundingBox([[t.maxX - t.centerX, t.maxY - t.centerY],
                               [t.minX - t.centerX, t.minY - t.centerY]]),
        b = new c.BoundingBox([[bbox.maxX - bbox.centerX, bbox.maxY - bbox.centerY],
                               [bbox.minX - bbox.centerX, bbox.minY - bbox.centerY]]);

    return a.contains(b);
  };

  return this;
};

/* Creates a bounding box from an array of ordered pairs in geographic space with
 * the format [lat, lng].
 */
CanvasMap.BoundingBox.fromLatLng = function(ordered_pairs) {
  return new CanvasMap.BoundingBox(
      CanvasMap.Mercator.transformPath(
        _.map(ordered_pairs, function(point) { return [point[1], point[0]]; })));
};

/* 
 * Constructs a MultiPolygon projected in cartesian space from a 
 * GeoJSON MultiPolygon in geographic space.
 */
CanvasMap.MultiPolygon = function(geojson) {
  var t = this;
  this.polygons = _.map(geojson.coordinates, function(polygon) {
    return new CanvasMap.Polygon(polygon);
  });

  return this;
};

/*
 * Constructs a Polygon projected in cartesian space from a
 * GeoJSON Polygon in geographic space
 */
CanvasMap.Polygon = function(poly) {
  var t = this;
  this.paths = _.map(poly, CanvasMap.Mercator.transformPath);

  return this;
};

CanvasMap.LineSegment = function(a, b) {
  var t = this;
  this.a = a;
  this.b = b;

  this.dist = function() {
    return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));
  };

  return this;
}

These classes will get beefed up with more esoteric features as well as the ability to draw themselves, as we go on.

For our maps, we’re drawing neighborhoods which are represented as CanvasMap.Drawables. A Drawable stores the underlying geometry (multipolygon), its bounding box, and some metadata like uri and name.

To successfully draw on the canvas, we need to figure out the region that we’re drawing as well as the scale. Without this, we’d have beautiful maps that render in about 0.001 pixels of the drawing space. For this we need to define our viewport. A viewport functions as the bounding box of the drawing, but has specialized logic to handle the mapping from real pixel space to the coordinate system of the drawing.

Our goal with our maps is to draw them so that every neighborhood big and small will be well highlighted when drawn. We also want to make sure that we are drawing the neighborhood in a part of the canvas where it is visible. We also want our maps to give a spatial cue to how the neighborhood relates to the city as a whole. Having a bunch of maps naively centered around the neighborhood in focus is not sexy. We want to preserve standards for display, while keeping pleasing amounts of variability. The lionshare of the logic in our maps is for working with these cues.

We size the viewport for a neighborhood by making its area some multiple of the area of the neighborhood’s bounding box. Having a neighborhood take up 10% of the drawing area has given us the best results. Neighborhoods come in all shapes and sizes, while our maps are designed at a constant size, so we have to calculate the dimensions of the viewport with respect to its aspect ratio. The formula for the area of a rectangle is

a = hw

so to get h and w, when we have an aspect ratio r, we use

w = sqrt(a*r)
h = a/w

Because we’re calculating desired area from the geometry’s bounding box, we get variation in the actual area of the geometry, because the area of the bounding box is the maximum area the geometry could have.

The spatial relationship in the viewport is trickier, but the ultimate goal is that if a neighborhood is located in the far west of a city, then the mass of the geometry should be pretty far west in our viewport. If it is close to the center, it should be drawn centrally. This also helps border neighborhoods look better in context, as the majority of the viewport will be focused on the rest of the city rather than a blank area where we don’t have coverage.

We calculate this by drawing a line segment from the center of the city’s bounding box through the center of the neighborhood to its intersection with an edge of the city’s bounding box. Using the slope, we find the line segment from the center of the viewport (conveniently centered on (0,0)) to the intersection with an edge of the viewport.

Using the ratio of the distance of the line drawn in the city bounding box to that of the line drawn in the viewport as our scaling factor, we find how far the viewport center should be from the neighborhood center. Using trig and the slope, we can then find how much the viewport center should be offset from the neighborhood center. We can then recenter the viewport on this point.

Before we are done, we have to ensure that the whole neighborhood bounding box is contained in the viewport. Depending on aspect ratios, this may or may not be possible. I haven’t figured out a good way to handle the impossible case, but when it is possible, we can shift the viewport just enough so that the bounding box is fully contained. Even in the case we don’t handle, the results are generally close enough that the idea of the map still works.

Our basic Viewport is:

CanvasMap.Viewport = function(width, height) {
  var t = this;
  var c = CanvasMap;

  this.pixelWidth = width;
  this.pixelHeight = height;

  this.aspectRatio = width/height;


  /* Scales the viewport to contain 'bbox' where 'bbox' takes up 'percent' of viewport */
  this.scale = function(bbox, percent) {
    var area = bbox.area();
    var viewport_area = area/percent;

    t.width = Math.sqrt(viewport_area*this.aspectRatio);
    t.height = viewport_area/t.width;
  };

  this.setOrigin = function(x, y) {
    t.originX = x;
    t.originY = y;

    t.bbox = new c.BoundingBox([[t.width/2 + x, t.height/2 + y],
                                [-1*t.width/2 + x, -1*t.height/2 + y]]);
  };

  this.moveOrigin = function(x, y) {
    t.setOrigin(t.originX + x, t.originY + y);
  };

  return this;
};

and this is our Drawable

/* Constructs a Drawable item from data.
 * In almost all cases this is a neighborhood for our purposes.
 * data should contain name, uri, bbox, and GeoJSON
 */
CanvasMap.Drawable = function(data) {
  var t = this;
  var c = CanvasMap;

  this.name = data.name;
  this.uri = data.uri;
  this.bbox = c.BoundingBox.fromLatLng(data.bbox);
  this.multipolygon = new c.MultiPolygon(data.GeoJSON);

  return this;
};

Now we must calculate a viewport for the drawable. We start with the real pixel widths and heights as well as a bounding box container that this drawable is spatially related to.

//CanvasMap.Drawable
this.calculateViewport = function(container, width, height) {
  var viewport = new c.Viewport(width, height);
  viewport.scale(t.bbox, 0.1);
  viewport.setOrigin(0, 0);

We create a new viewport, scale it for the content, and then center the origin on (0,0).

We now need to find the lines describing the spatial relationship between the neighborhood and the city and then the neighborhood and the viewport. This logic goes into the BoundingBox.

//CanvasMap.BoundingBox
this.calculateLines = function(bbox, viewport) {
  var x = bbox.centerX - t.centerX;
  var y = bbox.centerY - t.centerY;

x and y are the offset between the center of the container and the neighborhood container, this normalizes the container origin to (0,0) as well.

var intersect = [];
var vIntersect = [];
var slope;

// if slope is computable, (e.g. line is not vertical)
if(x != 0) {
  slope = y/x;
  var b = t.centerY - slope*t.centerX;

We have to handle the case of vertical lines. If the line is not vertical, slope is rise over run and b is

y = mx+b
y - mx = b

The next step is to figure out which edge this ray will intersect.

If y is positive (in quadrants one or two) and at an angle of more than 45 degrees and less than 135 degrees, it will hit the top edge.

Since the edge is a horizontal line and we know its y value we find the x intersect with

x = (y-b)/m

At this stage, we also find the intersection with the viewport (which is simplified by b being 0 as the line originates from the origin).

The same logic is applied for the other possible edges

// y = mx+b
// (y-b)/m = x
if(y > 0 && (slope >= 1 || (slope < 0 && slope >= -1))) {
  //top edge
  intersect = [(t.maxY - b)/slope, t.maxY];
  vIntersect = [viewport.bbox.maxY/slope, viewport.bbox.maxY];
} else if(y < 0 && (slope >= 1 || (slope < 0 && slope >= -1))) {
  //bottom edge
  intersect = [(t.minY - b)/slope, t.minY];
  vIntersect = [viewport.bbox.minY/slope, viewport.bbox.minY];
} else if(x > 0) {
  //right edge
  intersect = [t.maxX, slope*t.maxX + b];
  vIntersect = [viewport.bbox.maxX, slope*viewport.bbox.maxX];
} else {
  //left edge
  intersect = [t.minX, slope*t.minX + b];
  vIntersect = [viewport.bbox.minX, slope*viewport.bbox.minX];
}

When the line is vertical, the only possible intersections are the top and bottom edges.

} else {
  slope = false;

  if(y > 0) {
    //top edge
    intersect = [bbox.centerX, t.maxY];
    vIntersect = [x, viewport.bbox.maxY];
  } else {
    //bottom edge
    intersect = [bbox.centerX, t.minY];
    vIntersect = [x, viewport.bbox.minY];
  }
}

The information we need from this function is the slope of the line, and the line segments in the container from the center of the container to the intersect and to the center of the neighborhood. We also need the line segment from the viewport center to the viewport intersect.

return {
    slope: slope,
    container: {
      full: new c.LineSegment([t.centerX, t.centerY], intersect),
      toBboxCenter: new c.LineSegment([t.centerX, t.centerY], [bbox.centerX, bbox.centerY])},
    viewport: {
      full: new c.LineSegment([viewport.bbox.centerX, viewport.bbox.centerY], vIntersect) }
  };
};

Going back to our Drawable, we can continue calculating the viewport

//CanvasMap.Drawable#calculateViewport
var lines = container.calculateLines(t.bbox, viewport);

var lineRatio = lines.container.full.dist()/
  lines.viewport.full.dist();

var viewportToCenter = lines.container.toBboxCenter.dist()/lineRatio;

We find the desired distance from the viewport center to the neighborhood center by dividing the distance from the container to the neighborhood center by the ratio of the line distances from the container and viewport centers to their intersects.

We then apply trigonometric identities to find how much to shift the viewport center away from the neighborhood center.

var pY, pX;

if(lines.slope) {
  var A = Math.atan(lines.slope);
  pY = viewportToCenter*Math.sin(A);
  pX = viewportToCenter*Math.cos(A);
} else {
  //vertical line
  pX = 0;
  pY = viewportToCenter;
}

Vertical lines are again special because there is no change in the X component, so the distance is purely on the Y axis.

Because the domain of Math.atan is -90 to 90 degrees (e.g. lines going into quadrants 1 and 4), for lines that are in quadrants 2 or 3, we have to reverse the x and y shift.

//correct for quadrants 2 and 3
if(t.bbox.centerX < container.centerX) {
  pX *= -1;
  pY *= -1;
}

We now set the viewport’s origin and ensure that the entirety of the neighborhood bounding box is included in the viewport. At this stage, we are done.

viewport.setOrigin(t.bbox.centerX - pX, t.bbox.centerY - pY);

  viewport.includeBbox(t.bbox);

  return viewport;
};

The includeBbox method only comes in to play if the bbox is not already entirely contained by the viewport. It then checks if the viewport can even contain the bbox. If it can, we adjust the origin of the viewport so that it contains all points in the bbox.

//CanvasMap.Viewport
/* Shifts the viewport to include all of bbox if possible */
this.includeBbox = function(bbox) {
  if(!t.bbox.contains(bbox)) {
    // Check if a shift is possible
    // if it is do the shift

    if(t.bbox.canContain(bbox)) {
      // yay, its possible

      //adjust minimum x
      if(bbox.minX < t.bbox.minX) {
        t.moveOrigin(bbox.minX - t.bbox.minX, 0);
      } else if(bbox.minX > t.bbox.maxX) {
        t.moveOrigin(bbox.minX - t.bbox.maxX, 0);
      }

      //adjust maximum x
      if(bbox.maxX < t.bbox.minX) {
        t.moveOrigin(bbox.maxX - t.bbox.minX, 0);
      } else if(bbox.maxX > t.bbox.maxX) {
        t.moveOrigin(bbox.maxX - t.bbox.maxX, 0);
      }

      //adjust minimum y
      if(bbox.minY < t.bbox.minY) {
        t.moveOrigin(0, bbox.minY - t.bbox.minY);
      } else if(bbox.minY > t.bbox.maxY) {
        t.moveOrigin(0, bbox.minY - t.bbox.maxY);
      }

      //adjust maximum y
      if(bbox.maxY < t.bbox.minY) {
        t.moveOrigin(0, bbox.maxY - t.bbox.minY);
      } else if(bbox.maxY > t.bbox.maxY) {
        t.moveOrigin(0, bbox.maxY - t.bbox.maxY);
      }

    } else {
      // I should handle this case
      console.log("damn, foiled");
    }
  }
};

This leaves us with a viewport something like

where the bounding boxes for all the neighborhoods are in red, the viewport center is in cyan, and the viewport is the smaller black box. Look at how proportional it is!

Now, it is time to draw.

The first step in drawing is transforming the coordinate space of the canvas into the coordinate space of our viewport. We are scaling from real pixel space to our own invented space and then translating the origin to the origin of our viewport.

We do this by defining a transformation matrix. This matrix works by:

|pixelX|   |scaleX skewY translateX|   |x|
|pixelY| = |skewX scaleY translateY| * |y|
|   1  |   |  0     0        1     |   |1|

For our transformation, we only care about scaling and translating.

We find our scale by dividing our viewport’s width by its pixelWidth, and height by its pixelHeight, and taking the larger of the two as our scaling factor.

We set the y scale to be negative so that our origin is in the bottom left rather than the default top left.

We then move the origin of the canvas left to the left of our viewport and then down to the top of our viewport creating the matrix:

|1/scale    0    (-1/scale)*minX|
|   0    -1/scale (1/scale)*maxY|
|   0       0           1       |

and the code

//CanvasMap.Viewport
this.transformCanvas = function(ctx) {
  var scaleX = t.width/t.pixelWidth,
      scaleY = t.height/t.pixelHeight,
      scale = (scaleX > scaleY)? scaleX : scaleY;

  ctx.setTransform(1/scale, 0, 0, -1/scale, 
      (-1/scale)*t.bbox.minX, (1/scale)*t.bbox.maxY);

  return scale;
}

We return the scale value so that we can size constant sized things like line width appropriate to the coordinate space.

Our actual drawing is handled by a CanvasMap object

var CanvasMap = function(items) {
  var t = this;
  var c = CanvasMap;

  this.drawables = _.map(items, function(data) { return new c.Drawable(data); });

  this.findDrawable = function(uri) {
    return _.detect(t.drawables, function(d) { return d.uri == uri; });
  };

  this.draw = function(ctx, uri, container, w, h) {
    var item = t.findDrawable(uri);
    if(!item) return false;

    var viewport = item.calculateViewport(container, w, h);

    var scale = viewport.transformCanvas(ctx);

Now it is time to setup some styles for drawing neighborhood

ctx.lineWidth = 1.75*scale;
    ctx.strokeStyle = "#fff";
    ctx.shadowBlur = 0.5;
    ctx.lineJoin = 'round';

For each drawable we check if its bbox overlaps our viewport as there is no sense in drawing something that will not be visible. We also want to save the neighborhood that we are highlighting for drawing at the very end.

_.each(t.drawables, function(d) {
      if(d != item && viewport.bbox.overlaps(d.bbox)) {
        c.RenderingQueue.add(function() {
          setTimeout(function() { 
            ctx.fillStyle = "#ede4db";
            d.draw(ctx); 
            c.RenderingQueue.runNext();
          }, 10);
        });
      }
    });

Now it is time to draw the neighborhood of focus.

c.RenderingQueue.add(function() {
      setTimeout(function() {
        ctx.fillStyle = "#339933";
        item.draw(ctx);
      }, 0);
    });
    c.RenderingQueue.runNext();
  };

The RenderingQueue is a simple function queue that we use to preserve the ordering of the drawing. We use setTimeout to avoid blocking the browser while drawing. The drawing process is in general very fast, but a certain browser is pretty terrible about it and will give errors if a script executes a few million statements in one computational unit. I believe we all know which browser I am speaking about.

CanvasMap.RenderingQueue = {
  _fns: [],
  add: function(fn) {
    CanvasMap.RenderingQueue._fns.push(fn);
  },
  runNext: function() {
    var fn = CanvasMap.RenderingQueue._fns.shift()
    if(fn) fn();
  }
};

Now for the actual drawing, each Drawable just tells its MultiPolygon to draw itself. The MultiPolygon in turn just makes each of its Polygons draw themselves.

//CanvasMap.Drawable
this.draw = function(ctx) {
  t.multipolygon.draw(ctx);
};

//CanvasMap.MultiPolygon
this.draw = function(ctx) {
  _.each(t.polygons, function(polygon) { polygon.draw(ctx) });
};

The Polygon does the real drawing work. Luckily this is pretty straightforward as a polygon is composed of paths, and Canvas really likes paths.

//CanvasMap.Polygon
this.draw = function(ctx) {
  _.each(t.paths, function(path) {
    ctx.beginPath();
    ctx.moveTo(path[0][0], path[0][1]);
    _.each(path.slice(1), function(point) {
      ctx.lineTo(point[0], point[1]);
    });
    ctx.closePath();
    ctx.stroke();
    ctx.fill();
  });
};

And that is how we draw maps at NabeWise!

NabeWise uses Redis to store much of our neighborhood data. Capturing the identity of a neighborhood across 40+ (constantly changing) attributes does not fit well in the relational model and Redis is the mojo of features like our NabeFinder. Many of our pages, including our home page, never touch MySQL or Memcached or neighborhood results.

Our primary difficulty with working with Redis has been our need for essentially atomic operations that are composed of a few commands. When a number of changes are streaming in that all affect different facets of our encoded neighborhood records, we would prefer to not clobber the changes through interleaved gets and sets. These cases have been minimized (and we are constantly working to reduce them further). The obvious solution is to serialize access in these cases.

The standard Rails app runs with a number of worker processes, random rake tasks on cron or flights of manual folly, and probably an background task queue with one or more workers. This sucks when you’re trying to limit access to one process. After briefly looking at solutions to forcibly neuter concurrency, we decide to embrace and control it. Like Bond villains. With Erlang.

Thanks to GitHub and BERTRPC, exposing Erlang services to Rails is pretty trivial. Besides being good at dealing with and managing concurrency and distributed systems, Erlang makes expressing our data constraints and data access very clean and strict. The goal is still to keep certain write operations from interfering with others, but Ernie, our BERTRPC server, spawns a new process (in the Erlang sense) for every call. This is mostly what we want as the majority of any call can be completed as concurrently as we can go.

Two core features of Erlang are its OTP (Open Telecom Platform) and distributed Erlang. These allow the construction of networks of nodes and servers that can be used very flexibly. We constructed an OTP backend with gen_servers that would handle our precious order sensitive writes. Currently this is separated into single servers for each overall type of write (totals vs. ranks in our system), but should our load increase, we can easily separate at higher degrees of specificity to up our parallelism (and also allow for many possibilities in Redis sharding).

The last piece is hooking up Ernie to our distributed node. Distributed nodes are identified by names like fred@localhost or nabewise_attributes@127.0.0.1. Our first modification was to allow Ernie to be named by passing its executable the -name parameter. Distributed nodes are made aware of each other by pinging or otherwise accessing other nodes. Our second modification added the ability to specify an init function to be called on server start. This also allows us to share a redis connection between many short-lived processes. Our modified ernie is available at http://github.com/schleyfox/ernie .

This is our ernie.cfg

[{module, attributes},
 {type, native},
 {init, {attributes, init, []}},
 {codepaths, ["ebin/"]}].

The relevant bit of our attributes.erl is basically

init() ->
  start_redis(),
  net_adm:ping('nabewise_attributes@127.0.0.1').

Our actual setup differs only in that we add in monitoring for the remote node and attempt to reconnect on disconnect.

Summary

With Erlang, adding services distributed across different access needs, computers, or code divisions to your Rails app is simple. In addition to a reliable environment with powerful control of concurrency, you also get features like painlessly easy instant, asynchronous processing (cast in BERTRPC). In practice at NabeWise, this has significantly increased the performance and flexibility of our features that touch our neighborhood attribute data. Future posts will go into more detail on how we use this technology for our site.

Hi, We are the NabeWise development team. You don’t know us, but the breakdown is basically:

Andy Kramolisch — He makes features and makes them pretty.

Ben Hughes — I take our features and make them fast. I like to freak out about the details and sweat the raw queries.

We are currently hosted on SoftLayer, which is awesome! Our average response time is 99ms, and we have many pages that require fresh data out of both Redis and MySQL.

We make extensive use of jQuery, Redis, Rails, Erlang, MySQL, PostgreSQL/PostGIS, Unicorn, Nginx, and EventMachine/Thin.

We have a healthy obsession with how our website loads, and we strive to make even advanced features work quickly for everyone (even those who use Internet Explorer).

We use the most advanced, yet appropriate, technologies towards the goal of bringing neighborhoods to life. These approaches will be explained in subsequent blog posts.