Voronoi Spanning tree - long paths

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

The strategy is to hop from any site to the next site that is nearest to the designated root (compare with Voronoi spanning tree - short path).

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

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

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

.polygons {
  fill: none;
  stroke: #c9c9c9;
  stroke-width: 0.5;
}

.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(1500)
    .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;

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){
          dist = 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){
    if (f = diagram.next(e, x,y)) return { source: e.site, target: sites[f] };
  })
  .filter(function(e) { return !!e; });
}

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

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

function findcell(m) {
	var found = diagram.find(m[0],m[1], 50);

spanning = spanning
  .data(diagram.spanning(m[0],m[1]), function(d,i){return i;})
  .enter().append('line')
  .merge(spanning);
  
  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