Bounded Voronoi Tesselation using the algorithm described in xlr8r.info
This is a variant of the Bounded Voronoi Tessellation, with:
circularly distributed sites
the median distance instead of the mean (allowing a small optimisation)
many more exterior control points
a d3.curveCatmullRomClosed convex hull shape
not displaying links and sites
Other (unfinished) variants:
Shape-shifting, bad animation
Alpha-Shape, bad computation
Author: Philippe Rivière, August 2016
Based on mbostock's block: Voronoi Tessellation
forked from Fil's block: Circular Bounded Voronoi Tessellation
xxxxxxxxxx
<meta charset="utf-8">
<style>
.links {
stroke: #000;
stroke-opacity: 0;
}
.polygons {
stroke: #fff;
}
.polygons :first-child {
fill: #ff3d5a;
}
.sites {
fill: none;
stroke: none;
}
.sites :first-child {
fill: #fff;
}
.convex-hull {
fill: pink;
fill-opacity: 0.1;
stroke: #feccd5;
stroke-width: 5px;
}
</style>
<svg width="960" height="500"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://d3js.org/d3-scale-chromatic.v1.min.js"></script>
<script>
// Computes boundaries of connected triangles, given an array of triangles.
// Jason Davies - https://bl.ocks.org/jasondavies/1554783
function boundary(mesh) {
var counts = {},
edges = {},
r,
result = [];
// Traverse the edges of all triangles and discard any edges that appear twice.
mesh.forEach(function(triangle) {
for (var i = 0; i < 3; i++) {
var edge = [triangle[i], triangle[(i + 1) % 3]].sort(ascendingCoords).map(String);
(edges[edge[0]] = (edges[edge[0]] || [])).push(edge[1]);
(edges[edge[1]] = (edges[edge[1]] || [])).push(edge[0]);
var k = edge.join(":");
if (counts[k]) delete counts[k];
else counts[k] = 1;
}
});
while (1) {
var k = null;
// Pick an arbitrary starting point on a boundary.
for (k in counts) break;
if (k == null) break;
result.push(r = k.split(":").map(function(d) { return d.split(",").map(Number); }));
delete counts[k];
var q = r[1];
while (q[0] !== r[0][0] || q[1] !== r[0][1]) {
var p = q,
qs = edges[p.join(",")],
n = qs.length;
for (var i = 0; i < n; i++) {
q = qs[i].split(",").map(Number);
var edge = [p, q].sort(ascendingCoords).join(":");
if (counts[edge]) {
delete counts[edge];
r.push(q);
break;
}
}
}
}
return result;
}
function ascendingCoords(a, b) {
return a[0] === b[0] ? b[1] - a[1] : b[0] - a[0];
}
function alphashape(sites, alpha){
var dsq = function(a,b) {
var dx = a[0]-b[0], dy = a[1]-b[1];
return dx*dx+dy*dy;
},
asq = alpha*alpha,
mesh = d3.voronoi().triangles(sites).filter(function(t) {
return dsq(t[0],t[1]) < asq && dsq(t[0],t[2]) < asq && dsq(t[1],t[2]) < asq;
});
return boundary(mesh);
}
var svg = d3.select("svg").on("touchmove mousemove", moved),
width = +svg.attr("width"),
height = +svg.attr("height"),
margin = 0.2; // 0 ≤ m < 0.5
var color = d3.scaleOrdinal(d3.schemePastel1),
line = d3.line().curve(d3.curveCatmullRomClosed);
var sites = d3.range(200)
.map(function(d) {
var len = Math.min(width, height) / 10 * (1 - margin) * Math.sqrt(Math.random()),
angle = Math.random() * 2 * Math.PI;
var pole = [1-2*Math.round(Math.random()), 1-2*Math.round(Math.random())];
return [
pole[0] * 0.3 * Math.min(width, height) + width / 2 + len * Math.cos(angle),
pole[1] * 0.3 * Math.min(width, height) +height / 2 + len * Math.sin(angle)
]; });
var voronoi = d3.voronoi()
.extent([[-1, -1], [width + 1, height + 1]]);
var polygon = svg.append("g")
.attr("class", "polygons");
var convexhull = svg.append('path')
.attr('class', 'convex-hull');
var convexhull2 = svg.append('path')
.attr('class', 'convex-hull');
var convex2 = svg.append('g')
.attr('class', 'convex-hull');
var link = svg.append("g")
.attr("class", "links");
var site = svg.append("g")
.attr("class", "sites");
redraw();
function moved() {
sites[0] = d3.mouse(this);
redraw();
}
function redraw() {
var links = voronoi.links(sites),
ext = Math.sqrt(d3.median(links, function(l) {
var dx = l.source[0] - l.target[0],
dy = l.source[1] - l.target[1];
return dx*dx + dy*dy;
}));
var convex = d3.polygonHull(sites);
convex.centroid = d3.polygonCentroid(convex);
convex = convex.map(function(p){
var dx = p[0] - convex.centroid[0],
dy = p[1] - convex.centroid[1],
angle = Math.atan2(dy, dx);
return [p[0] + Math.cos(angle) * ext, p[1] + Math.sin(angle) * ext];
});
var sites2 = sites.slice(); // clone
for (var i = 0; i < convex.length; i++) {
var n = convex[i], m = convex[i+1]||convex[0];
var dx = n[0] - m[0],
dy = n[1] - m[1],
dist = Math.sqrt(dx * dx + dy * dy);
var pts = 2 * Math.ceil(dist / 2 / ext);
for(var j=0; j <= pts; j++) {
var p = [m[0] + dx *j / pts, m[1] + dy * j / pts];
p.artificial = 1;
sites2.push(p);
}
}
var diagram = voronoi(sites2);
var p = polygon.selectAll("path")
.data(diagram.polygons());
p.enter().append("path").merge(p).call(redrawPolygon)
p.exit().remove();
var l = link
.selectAll("line")
.data(diagram.links().filter(function(l){
return !l.source.artificial && !l.target.artificial;
}));
l.enter()
.append("line")
.merge(l)
.call(redrawLink)
.exit()
.remove();
var s = site
.selectAll("circle")
.data(sites);
s.enter()
.append("circle")
.attr("r", 2.5)
.merge(s)
.call(redrawSite);
var points =
diagram.polygons()
.filter(function(p){
return !p.data.artificial;
}),
unique = d3.map(d3.merge(points)).values(),
convex4 = alphashape(d3.merge([unique,sites, points.map(d3.polygonCentroid)]), 80),
// convex4 = boundary(mesh), //[d3.polygonHull(d3.merge(points))], //boundary(mesh),
_;
if (false) {
convex2
.select('g').remove();
var convex22 = convex2.append('g')
.selectAll('circle')
.data(unique)
.enter()
.append('circle')
.attr('r', 3);
convex22
.exit()
.remove();
convex22
.merge(convex22)
.attr('cx', function(d){return d[0];})
.attr('cy', function(d){return d[1];});
}
console.log(convex4)
convexhull2.attr('d', convex4.map(line).join(' '));
convexhull.attr('d', line(convex));
}
function redrawPolygon(polygon) {
polygon
.attr("fill", function(d, i) {
return i < sites.length ? color(i) : 'none';
})
.attr("stroke-width", function(d, i) {
return i < sites.length ? 2 : 0;
})
.attr("d", function(d) { return d ? "M" + d.join("L") + "Z" : null; });
}
function redrawLink(link) {
link
.attr("x1", function(d) { return d.source[0]; })
.attr("y1", function(d) { return d.source[1]; })
.attr("x2", function(d) { return d.target[0]; })
.attr("y2", function(d) { return d.target[1]; });
}
function redrawSite(site) {
site
.attr("cx", function(d) { return d[0]; })
.attr("cy", function(d) { return d[1]; });
}
</script>
https://d3js.org/d3.v4.min.js
https://d3js.org/d3-scale-chromatic.v1.min.js