Posted on July 23, 2013

Adding boundaries inside a hexagonal heatmap with d3.js

In the previous post I explained how to create a hexagonal heatmap. For example to use as output for a self organizing map. I like to create rather large maps with a lot of hexagons if I have enough data. It gives the idea of a high resolution. In that case it’s very useful to divide the entire map into a manageable number of higher level segments.

A 'lay of the land' map showing the different segments in the SOM

Finding the neighbours

I explain more about the R SOM program in this post

I use the SOM-Ward method to calculate the segments, which is all done in R with a SOM program I developed. I could create a post completely on this, but in essence:

In the end each node will have a new property, namely the segment number it belongs to. When two neighboring nodes have a different segment number, a line should be plotted in the heatmap to section off each segment. I therefore loop over each hexagon and calculate if a side needs to get a line in between them. In the end I have a matrix looking like this, where node1 and node2 being neighbors of different segments:

node1     node2
5         6
1         31
...       ...
577       548
578       579

The calculation of the line coordinates

For large maps, there is never a single-node segment, or you did things wrong

As you can see in the image below, one hexagon (not in the edges of the map) has six neighbors. Therefore, there are six types of lines that could be drawn. It depends on the position of the neighbor around the node.

At first I wanted to use cases, where each case would be a different neighboring position around the node. In this set-up I would have six cases. Once I would know the case, I could draw the corresponding line segment based on the center coordinates of the node, using the angle information of the case.

Six neighbors

But before I was going to write out six cases and add a lot of lines to my d3.js code, I wanted to see if I could find something smarter. Instead of six cases, couldn’t I see each possible neighbor as the same, only rotated? Was it possible to calculate the line segment coordinates by using only the center coordinates of the two neighbors? I already had this information anyway from creating the hexagonal grid in the first place.

And then it hit me! I could see the problem as calculating the two points of intersection between two circles, since the line would need to be drawn between two corner points

The line between neighbors is drawn between the points of the hexagon's 'circles'

You can find several pages online that have calculated the formula needed to find the blue to dots in the image above, based on the red two center points.

Line segment calculation

The one I found most helpful was the following site about the intersection of two circles. Especially the plot included with the formula is a great help

The 'variables' available when two circles intersect

Taking the following mathematical points into account:

This turns the formula on The intersection of two circles website into:

//Point one
x3 = x2 + (y1 - y2)/Math.sqrt(3)
y3 = y2 - (x1 - x2)/Math.sqrt(3)

//Point two
x3' = x2 - (y1 - y2)/Math.sqrt(3)
y3' = y2 + (x1 - x2)/Math.sqrt(3)

Where P1[x1,y1] is the center of one of the two nodes and P2[x2,y2] is the location in the middle of the two centers of the nodes (thus in the middle of the line segment).

Coding in d3.js

How to transport this all to d3? Like I said before, I only have to input an array (of arrays) where each subarray contains two entries, the two node id’s where a line should be drawn in between. I can use the points array that I already calculated to make the grid, take the centers of each node and apply the above formulas.

There is just one small catch. In my previous post I explained that when trying to calculate the true centers of each node, the hexgrid plugin created a jump in nodes after ~12 nodes. I therefore used a slightly different version. Now however, I do need to use the exact locations. So I just create another array, called truePoints, and use Math.sqrt(3) instead of 1.75 as follows

//Calculate the center positions of each hexagon
var points = [];
var truePoints = [];
for (var i = 0; i < MapRows; i++) {
    for (var j = 0; j < MapColumns; j++) {
        points.push([hexRadius * j * 1.75, hexRadius * i * 1.5]);
        truePoints.push([hexRadius * j * Math.sqrt(3), hexRadius * i * 1.5]);
    }//for j
}//for i

The rest of the code, to actually calculate the coordinates of the line segment [x3,y3] to [x3',y3'] looks like this

///////////////////////////////////////////////////////////////////////////
///// Function to calculate the line segments between two node numbers ////
///////////////////////////////////////////////////////////////////////////
//Which nodes are neighbors
var neighbour =
[[577,548], [578,579], [578,548], [578,549], 
//... other arrays in between ..., 
[33,34], [33,4], [46,47], [46,17], [3,4], [16,17]];

//Initiate some variables
var Sqr3 = 1/Math.sqrt(3);
var lineData = [];
var Node1,
    Node2,
    Node1_xy,
    Node2_xy,
    P1,
    P2;

//Calculate the x1, y1, x2, y2 of each line segment between neighbors
for (var i = 0; i < neighbour.length; i++) {
    Node1 = neighbour[i][0];
    Node2 = neighbour[i][1];

    //An offset needs to be applied if the node is in an uneven row
    if (Math.floor(Math.floor((Node1/MapColumns)%2)) != 0) {
        Node1_xy = [(truePoints[Node1][0]+(hexRadius/(Sqr3*2))),
                     truePoints[Node1][1]];
    } else {
        Node1_xy = [truePoints[Node1][0],truePoints[Node1][1]];
    }

    //An offset needs to be applied if the node is in an uneven row
    if (Math.floor(Math.floor((Node2/MapColumns)%2)) != 0) {
        Node2_xy = [(truePoints[Node2][0]+(hexRadius/(Sqr3*2))),
                     truePoints[Node2][1]];
    } else {
        Node2_xy = [truePoints[Node2][0],truePoints[Node2][1]];
    }//else

    //P2 is the exact center location between two nodes
    P2 = [(Node1_xy[0] + Node2_xy[0])/2, (Node1_xy[1] + Node2_xy[1])/2]; //[x2,y2]
    P1 = Node1_xy; //[x1,x2]

    //A line segment will be drawn between the following two coordinates
    lineData.push([(P2[0] + Sqr3*(P1[1] - P2[1])),
                   (P2[1] + Sqr3*(P2[0] - P1[0]))]); //[x3_top, y3_top]
    lineData.push([(P2[0] + Sqr3*(P2[1] - P1[1])),
                   (P2[1] + Sqr3*(P1[0] - P2[0]))]); //[x3_bottom, y3_bottom]
}//for i

Here you can see another small catch. For hexbin, I did not have to take the offset into account for the center locations (the row after the first row is offset with 0.5 * width). Now I do need to remember this, so the if...else statements adds 0.5 * width which is Math.sqrt(3)/2 * radius to the x-coordinate of the centers if needed.

Drawing the lines

The final step: we initiate a d3.svg.line And loop over each [x3,y3], [x3',y3'] pair to draw the line

var lineFunction = d3.svg.line()
    .x(function(d) {return d[0];})
    .y(function(d) {return d[1];})
    .interpolate("linear");

var Counter = 0;
//Loop over the lineData and draw each line
for (var i = 0; i < (lineData.length/2); i++) {
    svg.append("path")
        .attr("d", lineFunction([lineData[Counter],lineData[Counter+1]]))
        .attr("stroke", "black")
        .attr("stroke-width", 1.25)
        .attr("fill", "none");

    Counter = Counter + 2;
} //for i

Because each line needs two pairs of subarrays, the loop only goes over half the length of lineData, and I use a Counter to jump two indices ahead in each loop. Adding all this to the end of the code of the previous post, should give you the following result:

Adding segment boundary lines to a hexagonal heatmap

I am sure that all of this could also be done in other (faster/better) ways, but I’ve only been playing around with d3 and Javascript for about 3 weeks so I’m just happy that I got it working in the first place. You can find the code and example here.

I’ve now started to read one of the only books on learning D3.js called Interactive Data Visualization for the Web - An Introduction to designing with D3 by Scott Murray. Especially the first bit explaining about HTML, CSS and DOM really helped me get a better understanding of the logic behind d3. I think that I appreciate the book more now that I am reading it after I really tried making things with d3 and ran into a lot of frustrations. Especially when trying to access the data that was being read in, having never really worked with JSON (*≧▽≦)

See also