forked from jasondavies's block: hull padding
Last active
October 1, 2015 06:48
-
-
Save enjalot/1fa21f4ccf084f6369d3 to your computer and use it in GitHub Desktop.
hull padding
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<html> | |
<head> | |
<meta http-equiv="Content-Type" content="text/html;charset=utf-8"> | |
<title>Alpha-Shapes</title> | |
<script src="http://mbostock.github.com/d3/d3.min.js"></script> | |
<script src="http://mbostock.github.com/d3/d3.geom.min.js"></script> | |
<style type="text/css"> | |
path { | |
stroke: #000; | |
stroke-width: .5px; | |
} | |
.regular { | |
fill: #39c; | |
} | |
.pad { | |
fill: lightgreen; | |
} | |
.shrink { | |
fill: orange; | |
} | |
</style> | |
</head> | |
<body> | |
<script type="text/javascript"> | |
var w = 960; | |
var h = 500; | |
var alpha = 50; | |
var padding = 15; | |
var vertices = [[162, 332], [182, 299], [141, 292], [158, 264], [141, 408], [160, 400], [177, 430], [151, 442], [155, 425], [134, 430], [126, 447], [139, 466], [160, 471], [167, 447], [182, 466], [192, 442], [187, 413], [173, 403], [168, 425], [153, 413], [179, 275], [163, 292], [134, 270], [143, 315], [177, 320], [163, 311], [162, 281], [182, 255], [141, 226], [156, 235], [173, 207], [187, 230], [204, 194], [165, 189], [145, 201], [158, 167], [190, 165], [206, 145], [179, 153], [204, 114], [221, 138], [243, 112], [248, 139], [177, 122], [179, 99], [196, 82], [219, 90], [240, 75], [218, 61], [228, 53], [211, 34], [197, 51], [179, 65], [155, 70], [165, 85], [134, 80], [124, 58], [153, 44], [173, 34], [192, 27], [156, 19], [119, 32], [128, 17], [138, 36], [100, 58], [112, 73], [100, 92], [78, 100], [83, 78], [61, 63], [80, 44], [100, 26], [60, 39], [43, 71], [34, 54], [32, 90], [53, 104], [60, 82], [66, 99], [247, 94], [187, 180], [221, 168]], | |
offset = function(a,dx,dy) { | |
return a.map(function(d) { return [d[0]+dx,d[1]+dy]; }); | |
}, | |
dsq = function(a,b) { | |
var dx = a[0]-b[0], dy = a[1]-b[1]; | |
return dx*dx+dy*dy; | |
}, | |
asq = alpha*alpha, | |
// well, this is where the "magic" happens.. | |
mesh = d3.geom.delaunay(offset(vertices,600,0)).filter(function(t) { | |
return dsq(t[0],t[1]) < asq && dsq(t[0],t[2]) < asq && dsq(t[1],t[2]) < asq; | |
}); | |
var svg = d3.select("body") | |
.append("svg") | |
.attr("width", w) | |
.attr("height", h) | |
.attr("class", "Blues") | |
.append("g") | |
.attr("transform", "translate(0, 0)") | |
svg.append("g").classed("regular", true) | |
.attr("transform", "translate(-600, 0)") | |
.selectAll("path") | |
.data(mesh) | |
.enter().append("path") | |
.attr("d", function(d) { return "M" + d.join("L") + "Z"; }); | |
svg.append("g").classed("pad", true) | |
.attr("transform", "translate(-300, 0)") | |
.selectAll("path") | |
.data(mesh) | |
.enter().append("path") | |
.attr("d", function(d) { return "M" + d.join("L") + "Z"; }); | |
svg.append("g").classed("shrink", true) | |
.attr("transform", "translate(0, 0)") | |
.selectAll("path") | |
.data(mesh) | |
.enter().append("path") | |
.attr("d", function(d) { return "M" + d.join("L") + "Z"; }); | |
var bounds = boundary(mesh); | |
svg.append("g") | |
.attr("transform", "translate(-600, 0)") | |
.selectAll("path") | |
.data(bounds) | |
.enter().append("path") | |
.style("fill", "#fc0") | |
.style("fill-opacity", .5) | |
.style("stroke-width", 2) | |
.attr("d", function(d) { return "M" + d.join("L"); }); | |
var grow = pad(bounds, padding); | |
console.log(bounds[0], grow[0]); | |
svg.append("g") | |
.attr("transform", "translate(-300, 0)") | |
.selectAll("path") | |
.data(grow) | |
.enter().append("path") | |
.style("fill", "#fc0") | |
.style("fill-opacity", .5) | |
.style("stroke-width", 2) | |
.attr("d", function(d) { return "M" + d.join("L"); }); | |
var shrink = pad(bounds, -padding); | |
console.log(bounds[0], shrink[0]); | |
svg.append("g") | |
.attr("transform", "translate(0, 0)") | |
.selectAll("path") | |
.data(shrink) | |
.enter().append("path") | |
.style("fill", "#fc0") | |
.style("fill-opacity", .5) | |
.style("stroke-width", 2) | |
.attr("d", function(d) { return "M" + d.join("L"); }); | |
function pad(bounds, amount) { | |
var result = []; | |
bounds.forEach(function(bound) { | |
var padded = []; | |
var area = 0; | |
bound.forEach(function(p, i) { | |
// http://forums.esri.com/Thread.asp?c=2&f=1718&t=174277 | |
// Area = Area + (X2 - X1) * (Y2 + Y1) / 2 | |
var im1 = i - 1; | |
if(i == 0) { | |
im1 = bound.length - 1; | |
} | |
var pm = bound[im1]; | |
area += (p[0] - pm[0]) * (p[1] + pm[1]) / 2; | |
}); | |
var handedness = 1; | |
if(area > 0) handedness = -1 | |
bound.forEach(function(p, i) { | |
// average the tangent between | |
var im1 = i - 1; | |
if(i == 0) { | |
im1 = bound.length - 2; | |
} | |
//var tp = getTangent(p, bound[ip1]); | |
var tm = getTangent(p, bound[im1]); | |
//var avg = { x: (tp.x + tm.x)/2, y: (tp.y + tm.y)/2 }; | |
//var normal = rotate2d(avg, 90); | |
var normal = rotate2d(tm, 90 * handedness); | |
padded.push([p[0] + normal.x * amount, p[1] + normal.y * amount ]) | |
}) | |
result.push(padded) | |
}) | |
return result | |
} | |
function getTangent(a, b) { | |
var vector = { x: b[0] - a[0], y: b[1] - a[1] } | |
var magnitude = Math.sqrt(vector.x*vector.x + vector.y*vector.y); | |
vector.x /= magnitude; | |
vector.y /= magnitude; | |
return vector | |
} | |
function rotate2d(vector, angle) { | |
//rotate a vector | |
angle *= Math.PI/180; //convert to radians | |
return { | |
x: vector.x * Math.cos(angle) - vector.y * Math.sin(angle), | |
y: vector.x * Math.sin(angle) + vector.y * Math.cos(angle) | |
} | |
} | |
// Computes boundaries of connected triangles, given an array of triangles. | |
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]; | |
} | |
</script> | |
</body> | |
</html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment