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