An example of d3.geom.concaveHull. It basically wraps the implementation by Gregor Aisch and Jason Davies with Ian Johnson's padding hull padding while providing some dynamic edge cutting.
Last active
March 16, 2016 15:45
-
-
Save emeeks/436c12e5bea2bdb9de57 to your computer and use it in GitHub Desktop.
Reusable Concave Hull 1
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
(function() { | |
d3.geom.concaveHull = function() { | |
var calculateDistance = stdevDistance, | |
padding = 0, | |
delaunay; | |
function distance(a, b) { | |
var dx = a[0]-b[0], | |
dy = a[1]-b[1]; | |
return Math.sqrt((dx * dx) + (dy * dy)); | |
} | |
function stdevDistance(delaunay) { | |
var sides = []; | |
delaunay.forEach(function (d) { | |
sides.push(distance(d[0],d[1])); | |
sides.push(distance(d[0],d[2])); | |
sides.push(distance(d[1],d[2])); | |
}); | |
var dev = d3.deviation(sides); | |
var mean = d3.mean(sides); | |
return mean + dev; | |
} | |
function concaveHull(vertices) { | |
delaunay = d3.geom.delaunay(vertices); | |
var longEdge = calculateDistance(delaunay); | |
mesh = delaunay.filter(function (d) { | |
return distance(d[0],d[1]) < longEdge && distance(d[0],d[2]) < longEdge && distance(d[1],d[2]) < longEdge | |
}) | |
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; | |
} | |
} | |
} | |
} | |
if (padding !== 0) { | |
result = pad(result, padding); | |
} | |
return result; | |
} | |
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) | |
} | |
} | |
function ascendingCoords(a, b) { | |
return a[0] === b[0] ? b[1] - a[1] : b[0] - a[0]; | |
} | |
concaveHull.padding = function (newPadding) { | |
if (!arguments.length) return padding; | |
padding = newPadding; | |
return concaveHull; | |
} | |
concaveHull.distance = function (newDistance) { | |
if (!arguments.length) return calculateDistance; | |
calculateDistance = newDistance; | |
if (typeof newDistance === "number") { | |
calculateDistance = function () {return newDistance}; | |
} | |
return concaveHull; | |
} | |
return concaveHull; | |
} | |
})() |
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 lang="en"> | |
<head> | |
<meta charset="utf-8" /> | |
<title>Concave Hulls</title> | |
<style> | |
</style> | |
</head> | |
<body> | |
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.16/d3.min.js" charset="utf-8" type="text/javascript"></script> | |
<script src="d3.geom.concaveHull.js" charset="utf-8" type="text/javascript"></script> | |
<script type="text/javascript"> | |
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]]; | |
defaultHull = d3.geom.concaveHull(); | |
fixedLengthHull = d3.geom.concaveHull().distance(50); | |
fixedLengthHull2 = d3.geom.concaveHull().distance(100); | |
colorRamp = d3.scale.linear().domain([0,100]).range(["red", "blue"]) | |
svg = d3.select("body") | |
.append("svg") | |
.attr("width", 1000) | |
.attr("height", 1000); | |
svg.append("g") | |
.attr("transform", "translate(0,0)") | |
.selectAll("path") | |
.data(defaultHull(vertices)) | |
.enter().append("path") | |
.attr("d", function(d) { return "M" + d.join("L") + "Z"; }) | |
.style("fill-opacity", 0.5) | |
.style("fill", function (d,i) {return colorRamp(i * 50)}) | |
.style("stroke", "pink") | |
.style("stroke-width", "1px"); | |
svg.append("g") | |
.attr("transform", "translate(300,0)") | |
.selectAll("path") | |
.data(fixedLengthHull(vertices)) | |
.enter().append("path") | |
.attr("d", function(d) { return "M" + d.join("L") + "Z"; }) | |
.style("fill-opacity", 0.5) | |
.style("fill", function (d,i) {return colorRamp(i * 50)}) | |
.style("stroke", "pink") | |
.style("stroke-width", "1px"); | |
svg.append("g") | |
.attr("transform", "translate(600,0)") | |
.selectAll("path") | |
.data(fixedLengthHull2(vertices)) | |
.enter().append("path") | |
.attr("d", function(d) { return "M" + d.join("L") + "Z"; }) | |
.style("fill-opacity", 0.5) | |
.style("fill", function (d,i) {return colorRamp(i * 50)}) | |
.style("stroke", "pink") | |
.style("stroke-width", "1px"); | |
</script> | |
</body> | |
</html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment