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).
xxxxxxxxxx
<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);
}
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>
https://d3js.org/d3.v4.min.js