Voronoi colorized spanning tree

Using Voronoi.find(x,y) to create a spanning tree.

The strategy is to hop from any site to the nearest site that is nearer to the designated root (See Voronoi spanning tree 2).

We then traverse the tree to paint the cells with nice colors.

Original work by Philippe Rivière for d3-voronoi (issue 17).

<!DOCTYPE html>
<meta charset="utf-8">
<style>

.spanning {
  stroke: #ffffff;
  stroke-opacity: 1;
  stroke-width: 3;
}

.polygons {
  fill: none;
  stroke: #eaeaea;
  stroke-width: 1;
}

.polygons.found {
  fill: #f00;
}

.sites {
  fill: #000;
  stroke: #fff;
}

</style>
<svg width="960" height="500"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>

var svg = d3.select("svg").on("touchmove mousemove", moved),
    width = +svg.attr("width"),
    height = +svg.attr("height");

var sites = d3.range(1000)
    .map(function(d) { return [Math.random() * width, Math.random() * height]; });

var voronoi = d3.voronoi() 
    .extent([[1, 1], [width-1, height-1]]);

var polygon = svg.append("g")
    .attr("class", "polygons")
  .selectAll("path")
  .data(voronoi.polygons(sites))
  .enter().append("path")
    .call(redrawPolygon);

var spanning = svg.append('g')
.attr('class', 'spanning')
.selectAll('line')
.data(sites);

var diagram = voronoi(sites);

diagram.next = function(cell, x,y) {
    var dx = x - cell.site[0], 
      dy = y - cell.site[1],
      dist = dx*dx + dy*dy,
      ldist = +Infinity; // link dist

var next = null;

cell.halfedges
    .forEach(function(e){
      var edge = diagram.edges[e];
      var ea = edge.left;
      if (ea === cell.site || !ea) {
        ea = edge.right;
      }
      if (ea){
 				var dx = x - ea[0],
            dy = y - ea[1],
            ndist = dx*dx + dy*dy;
        if (ndist < dist){
          dx = cell.site[0] - ea[0];
          dy = cell.site[1] - ea[1];
          ndist = dx*dx + dy*dy;
          if (ndist < ldist) {
            ldist = ndist;
            next = ea.index;
          }
        }
      }
    });
    return next;
}

diagram.find = function(x, y, radius){
  // optimization: start from most recent result 
  var next = diagram.find.found || Math.floor(Math.random() * diagram.cells.length),
      found;
  do {
    cell = diagram.cells[found = next];
  } while (next = diagram.next(cell, x, y));

diagram.find.found = found;
  //if (!radius || dist < radius * radius) 
    return cell.site;
}

diagram.spanning = function(x,y){
  return diagram.cells.map(function(e){
    var f = diagram.next(e, x, y);
    if (f !== null)
      return {
        source: e.site,
        target: {0: sites[f][0], 1: sites[f][1], index: f }
      };
  })
  .filter(function(e) { return !!e; });
}

findcell([width/2, height/2]);

function moved() {
  findcell(d3.mouse(this));
}

var colorized = new Array(diagram.cells.length);
  colorize_subtree(root[0].index, links, 180, 0);
  
  
  function angle(e, c){
        var dx = sites[e][0] - sites[c][0],
            dy = sites[e][1] - sites[c][1];
        return Math.atan2(dy, dx) * 180 / Math.PI + (dx <0 ? 180:0);
      }

function color(i) {
  return d3.hsl(i[0], 1, Math.pow(1+i[1], -0.4));
}
  
function findcell(m) {
	var found = diagram.find(m[0],m[1], 50);

var tree = diagram.spanning(m[0],m[1]);
    var colorized = colorize_tree(tree);
  
  polygon.attr('fill', function(d,i) {
    return color(colorized[i]);
  })

spanning = spanning
  .data(tree, function(d,i){return i;})
  .enter().append('line')
  .merge(spanning);
  
  spanning.exit().remove()
  
  spanning
    .attr('x1', function(l){ return l.source[0];})
    .attr('y1', function(l){ return l.source[1];})
    .attr('x2', function(l){ return l.target[0];})
    .attr('y2', function(l){ return l.target[1];})
}

function redraw() {
  polygon = polygon.data(diagram.polygons()).call(redrawPolygon);
  site = polygon.data(diagram.polygons()).call(redrawPolygon);
}

</script>

https://d3js.org/d3.v4.min.js