|
<!DOCTYPE html> |
|
<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 - http://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> |