behind the gist

thoughts on code, analysis and craft

Client-server hexgrids

I like using hexgrids to summarize spatial statistics. Doing this in R is easy using stat_binhex from ggplot2. There are also client-side binning examples using D3. But what I want are statistics aggregated on the server and simple rendering of those on the client side. To support this use case, I created a Rails model to define the grid and JavaScript to render the results in D3.

To do this efficiently, we need a convention for labeling the bins within the hexgrid layer. We define a base property for the layer which defines the length of the base of the hexagon. Given this base and a grid identifier, we can draw the bin or determine if a point exists within it.

On the Ruby side, this looks like

define bin
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class HexgridLayer < ActiveRecord::Base

  def find_or_create_bin_containing!(x,y)
    # The origin of the grid system is the left vertex of the base
    # which has coordinates of (0.5*base, 0) in the rectangle that
    # circumscribes the hexagon.
    # That rectangle has width of base*2 and height of base*sqrt(3).
    # Hexagons in even columns have the same base, while odd columns
    # have a lower base, in other words, rows are numbered as in
    # the following diagram:
    #    
    #  /  \__/  \__/  \__/  \
    #  \1_/  \1_/  \1_/  \1_/
    #  /  \1_/  \1_/  \1_/  \
    #  \0_/  \0_/  \0_/  \0_/
    #  /  \0_/  \0_/  \0_/  \
    #--------------------------
    #   0  1  2  3  4  5  6  column

    col_width = 1.5 * base
    row_offset = 0.5 * height

    col = (x / col_width).floor
    x_in_col = x - col * col_width;
    y += col % 2 == 1 ? row_offset : 0
    row = (y / height).floor
    y_in_row = y - row * height

    if x_in_col > base
      dx = x_in_col - base
      dy = dx * slope
      if y_in_row < row_offset && y_in_row < dy
        # this belongs to the lower right neighbor
        row -= 1 if col % 2 == 1
        col += 1
      elsif y_in_row >= row_offset && y_in_row >= (height - dy)
        # this belongs to upper right neighbor
        row += 1 if col % 2 == 0
        col += 1
      end
    end
    Hexbin.find_or_create_by_layer_id_and_name!(layer_id: self.id, row: row, col: col)
  end

  private

  def height
    @height ||= base * Math.sqrt(3)
  end

  def slope
    @slope ||= height / base
  end
end

We define the grid in terms of columns and rows. As the code comments state, the rows actually overlap and we need to distinguish between rows for even columns or rows for odd columns.

Where a row and column intersect, we have three different bins that a point can be placed within: the main bin, the upper-right or the lower-right. Most of the guts of the method has to do with keeping track of even or odd columns and detecting which of the three bins the point belongs in.

In JavaScript, we can define a Hexgrid object that knows how to draw the grid based on row and col.

Hexgrid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

var Hexgrid = function(base) {
  this.base = base;
  this.height = Math.sqrt(3) * base;
  this.tile_path = this.make_path(base);
}

Hexgrid.prototype.make_path = function() {
  var half_base = 0.5 * this.base;
  var half_height = 0.5 * this.height;
  var segments = ["m"];
  [[0,0],
   [this.base,0],
   [half_base,half_height],
   [-half_base,half_height],
   [-this.base,0],
   [-half_base,-half_height]].forEach(function(point) {segments.push(point.join(","))});
  segments.push("z");
  return segments.join(" ");
};

Hexgrid.prototype.transform = function(row,col) {
  return (row % 2 == 0) ?
    "translate("+(row*1.5*this.base)+","+(col*this.height)+")" :
    "translate("+(row*1.5*this.base)+","+((col-0.5)*this.height)+")";
};

We just create one grid tile and then use transforms to reuse it for a specific row and column. We could use this in a shading layer like the following.

Hexgrid layer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

var Layer = function(svg, prefix, grid) {
  this.svg = svg;
  this.prefix = prefix;
  this.grid = grid;
};

Layer.prototype.bin_id = function(row, col) {
  return this.prefix + row + "-" + col;
};

Layer.prototype.add_bin = function(row, col) {
  this.svg.append("path")
  .attr("id",this.bin_id(row,col))
  .attr("class", "tile")
  .attr("transform", this.grid.transform(row,col))
  .attr("d", this.grid.tile_path);
};

Layer.prototype.update_bin = function(record) {
  this.svg.select("#"+this.bin_id(record.row, record.col))
  .datum(record)
  .attr("class", "tile " + this.shade_class(record));
};

Layer.prototype.shade_class = function(record) {
  return "q" + Math.floor(6 * record.value / 100) + "-6";
};

We would typically only need to add the bins once and would then update the bin shading based on updates from the server. Notice that the record for each bin can have multiple values associated with it. By attaching the record with datum, we can access it in event handlers to recompute the shading based on user inputs. A user would pick a particular statistic from a menu, for example, and we would recompute the class from the attached datum for all the bins. But in our simple example, we just calculate a lib/colorbrewer class based on value.