|
<!DOCTYPE html> |
|
<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> |