D3 sometimes falls short in performance. Browsers just aren't meant to draw and update many svg elements. Canvas can help adress some of these problems and in this document I will demo some things that I've hacked together. All this work is heavily (!) inspired by the recent work of Mike Bostock found here.

## Minimum Spanning Tree

In d3, you would be able to keep track of the state of your visualisation via the DOM of the browser. It would keep track of where svg elements are located as well as have event bindings. Canvas will not give you this luxury, you'll need to track the state of the drawn objects yourself.

You can still use many utility functions from d3 though, or any other front end javascript code. In this next example I'm using `d3.timer`

and lodash extensively.

### A use case

Imagine that we have a set number of drones that is each doing random searches on a plane. A random search is not the best way to go about this, but the coverage would not be terrible. The plot below shows location of 100 of these drones.

Now suppose that these drones need to be in contact with eachother. They don't all need to be communicating to everybody but they do need to span a network such that no message will end up missing. The further drones are away from eachother, the more battery it costs to send a message. Can we calculate which drones need to be connected to which drones in real time such that each drone is linked?

Below you'll see the same cloud of drones with the according minimum spanning tree. Points that are generally very close to eachother will have extra blue connections drawn.

The code used to create this is very (!) similar to Mike's example except that I'm also drawing lines for the minimum spanning tree as well. You can check the source code of this blog post for a full implementation, beware that it is pretty naive as it checks distances for points that it does not need to.

The algorithm for minimum spanning tree boils down to keeping track of points in the spanning tree and points that still need to be added. At each iteration you add a point to the tree that has the shortest distance.

```
function calc_link(set_in, set_out){
var new_connection = [],
min_dist = 10000;
for (var i = set_in.length - 1; i >= 0; i--) {
for (var j = set_out.length - 1; j >= 0; j--) {
var p1 = particles[set_in[i]],
p2 = particles[set_out[j]];
var new_dist = dist_particle(p1, p2);
if(new_dist < min_dist){
new_connection = [set_in[i], set_out[j]];
min_dist = new_dist;
}
};
};
return new_connection;
}
function calc_tree(){
var connections = [];
var set_in = [particles.length - 1],
set_out = d3.range(particles.length - 1);
for(i in set_out){
connections.push(calc_link(set_in, set_out));
set_in = _.unique(_.flatten(connections)),
set_out = _.difference(d3.range(particles.length), set_in);
}
return connections;
}
```

## Community Detection

What now if we want to split these drones up, ie. cluster them according to their location? We could use their location and use kmeans but that seems a bit naive, knowing that location alone is no guarantee that two drones are connected.

Doing a MST has an extra benefit: we can use it to help find communities. It gives an extra dimension to the drone data which we can exploit to create suitable communities of drones.

The simplest heuristic I could come up with was to use the following algorithm:

```
1. Determine which paths in the tree are leaf paths
2. Remove them.
3. Repeat until only a few paths of the tree are left.
4. Pick one of these remaining paths.
```

The intuition behind the algorithm is that a good path to cut would be a path that is located centrally. By recursively removing leaf nodes, you'll end up with one of these paths. Below is the same tree as above but now with a recommendation for a cut.

If you want to expand this to more than two communities you might take the two subtrees and apply the same algorithm.

## Conclusions

Canvas is pretty darn worthwhile and has some performance benefits compared to d3. You'll need to write more javascript though, which isn't too bad if you can use `d3`

and `lodash`

.