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:

• At the start every node is its own segment
• Next merge the two segments that have the smallest distance between them and that are neighbors
• Then update the distance of the new segment (that now consists of two nodes)- Iterate until you have the number of segments you wanted, e.g. 8

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.

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

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

Taking the following mathematical points into account:

• We have two circles with the same radius
• The width of a hexagon, `2*a` or `2*b` in the image above, is equal to `sqrt(3) * radius`
• The height of a hexagon is equal to `2 * radius`. And therefore `h` in the image above is `0.25 * height = 0.5 * radius`

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.

``````//Calculate the center positions of each hexagon
var points = []
for (var i = 0; i < MapRows; i++) {
for (var j = 0; j < MapColumns; j++) {
var x = hexRadius * j * Math.sqrt(3)
//Offset each uneven row by half of a "hex-width" to the right
if(i%2 === 1) x += (hexRadius * Math.sqrt(3))/2
var y = hexRadius * i * 1.5
points.push([x,y])
}//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];
Node2 = neighbour[i];

Node1_xy = [points[Node1],points[Node1]];
Node2_xy = [points[Node2],points[Node2]];

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

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

### 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;})
.y(function(d) {return d;})
.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: