Urquhart graph by fil

index.html

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

.graph {
  stroke: #f40024;
  stroke-opacity: 1;
  stroke-width: 2;
}

.polygons {
  fill: none;
  stroke: #dbdbdb;
  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"),
    width = +svg.attr("width"),
    height = +svg.attr("height");

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

var voronoi = d3.voronoi();

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

var graph = svg.append('g')
.attr('class', 'graph');

var site = svg.append('g')
.attr('class', 'site')
.selectAll('circle')
.data(sites)
.enter()
.append('circle')
.attr('r',2)
.attr('fill','white')
.attr('stroke','black')
.call(redrawSite)
;

var diagram = voronoi(sites);
  
  diagram.urquhart = function(){
    var urquhart = d3.map();
    
    diagram.links()
    .forEach(function(link) {
      var v = d3.extent([link.source.index, link.target.index]);
      urquhart.set(v, link);
    });
    urquhart._remove = [];
    diagram.triangles()
    .forEach(function(t) {
      var l = 0, length = 0, i, v;
      for (var j=0; j<3; j++) {
        var a = t[j], b = t[(j+1)%3];
        v = d3.extent([a.index, b.index]);
        length = (a[0]-b[0]) * (a[0]-b[0]) + (a[1]-b[1]) * (a[1]-b[1]);
        if (length > l) {
          l = length;
          i = v;
        }
      }
      urquhart._remove.push(i);
    });
    urquhart._remove.forEach(function(i) {
      if (urquhart.has(i)) urquhart.remove(i);
    });
    return urquhart.values();
  }

  drawgraph();
  
function drawgraph(){
   var links = diagram.urquhart();
  graph
    .selectAll('line')
   .data(links)
  .enter().append('line')
    .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(sites).call(redrawSite);
  drawgraph();
}

function redrawPolygon(polygon) {
  polygon.attr("d", function(d) {
    if (d && !d.filter(function(n){ return !n}).length) {
      return "M" + d.join("L") + "Z";
    }
  });
}
function redrawSite(site) {
  site
      .attr("transform", function(d) { return 'translate(' + d + ')'; });
}


</script>