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 (See Voronoi spanning tree 2).
We then traverse the tree to paint the cells with nice colors.
Original work by Philippe Rivière for d3-voronoi (issue 17).
xxxxxxxxxx
<meta charset="utf-8">
<style>
.spanning {
stroke: #ffffff;
stroke-opacity: 1;
stroke-width: 3;
}
.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(1000)
.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: {0: sites[f][0], 1: sites[f][1], index: f }
};
})
.filter(function(e) { return !!e; });
}
findcell([width/2, height/2]);
function moved() {
findcell(d3.mouse(this));
}
function colorize_tree(tree){
var links = diagram.cells.map(function(d,i){
return {index:i, inbound:[], outbound:[]};
})
tree
.forEach(function(l){
links[l.target.index].inbound.push(l.source.index);
links[l.source.index].outbound.push(l.target.index);
});
var root = links.filter(function(e){
return e.outbound.length == 0;
});
var colorized = new Array(diagram.cells.length);
colorize_subtree(root[0].index, links, 180, 0);
function angle(e, c){
var dx = sites[e][0] - sites[c][0],
dy = sites[e][1] - sites[c][1];
return Math.atan2(dy, dx) * 180 / Math.PI + (dx <0 ? 180:0);
}
function colorize_subtree(cell, links, cur, level) {
colorized[cell] = [cur, level];
var l = links[cell].inbound;
if (l.length > 0){
var d = Math.pow(2,-level);
l
.forEach(function(c){
colorize_subtree(c, links, cur * (1-d) + d * angle(c,cell), level+1);
});
}
}
return colorized;
}
function color(i) {
return d3.hsl(i[0], 1, Math.pow(1+i[1], -0.4));
}
function findcell(m) {
var found = diagram.find(m[0],m[1], 50);
var tree = diagram.spanning(m[0],m[1]);
var colorized = colorize_tree(tree);
polygon.attr('fill', function(d,i) {
return color(colorized[i]);
})
spanning = spanning
.data(tree, 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