Skip to content

Instantly share code, notes, and snippets.

@emeeks

emeeks/d3.geom.concaveHull.js

Last active March 16, 2016 15:45
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save emeeks/9aa0478cf739164c9005 to your computer and use it in GitHub Desktop.
Save emeeks/9aa0478cf739164c9005 to your computer and use it in GitHub Desktop.
Download ZIP
Interactive Concave Hull
Raw
readme.md

Drag the circles (drawn at every vertex) to see the d3.geom.concaveHull algorithm adapt interactively. Also shows an issue with the padding calculation

Raw
d3.geom.concaveHull.js
(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;
}
})()
Raw
index.html
<!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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment