Voronoi Spanning tree - short paths by Fil

index.html

<!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);
}

function redrawPolygon(polygon) {
  polygon
      .attr("d", function(d) { return d ? "M" + d.join("L") + "Z" : null; });
}
function redrawSite(site) {
  site
      .attr("transform", function(d) { return 'translate(' + d + ')'; });
}


</script>