Drag the circles (drawn at every vertex) to see the d3.geom.concaveHull algorithm adapt interactively. Also shows an issue with the padding calculation
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<title>Interactive 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 = d3.range(50).map(function () {return [Math.random() * 500, Math.random() * 500]})
defaultHull = d3.geom.concaveHull().distance(100);
paddedHull = d3.geom.concaveHull().distance(100).padding(25);
colorRamp = d3.scale.linear().domain([0,10]).range(["red", "blue"])
svg = d3.select("body")
.append("svg")
.attr("width", 1000)
.attr("height", 1000);
drag = d3.behavior.drag().on("drag", dragging).on("dragend", dragstop)
svg.selectAll("circle")
.data(vertices)
.enter()
.append("circle")
.call(drag);
render();
function dragging(d) {
d[0] = d3.event.x;
d[1] = d3.event.y;
render();
}
function dragstop(d) {
svg
.selectAll("path")
.data(paddedHull(vertices))
.transition()
.duration(1000)
.attr("d", function(d) { return "M" + d.join("L") + "Z"; })
.style("fill", function (d,i) {return colorRamp(i)})
}
function render() {
svg
.selectAll("path")
.data(defaultHull(vertices))
.enter().insert("path", "circle")
.style("fill-opacity", 0.5)
.style("stroke", "pink")
.style("stroke-width", "1px");
svg
.selectAll("path")
.data(defaultHull(vertices))
.exit().remove();
d3.selectAll("path")
.attr("d", function(d) { return "M" + d.join("L") + "Z"; })
.style("fill", function (d,i) {return colorRamp(i)})
d3.selectAll("circle")
.attr("cx", function (d) {return d[0]})
.attr("cy", function (d) {return d[1]})
.attr("r", 5)
.style("fill", "blue")
}
</script>
</body>
</html>
(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;
}
})()