Voronoi Spanning tree - short paths

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 (compare to the Voronoi spanning tree long path).

See also the colorized version.

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

forked from Fil's block: Voronoi Spanning tree - short paths

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

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

.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(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,
      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: 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.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