Skip to content

Instantly share code, notes, and snippets.

@gka
Created January 3, 2012 00:08
Show Gist options
  • Save gka/1552725 to your computer and use it in GitHub Desktop.
Save gka/1552725 to your computer and use it in GitHub Desktop.
alpha-shapes aka concave hulls in d3
<!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.js"></script>
<script src="http://mbostock.github.com/d3/d3.geom.js"></script>
<style type="text/css">
path {
stroke: #000;
stroke-width: .5px;
fill: #39c;
}
circle {
fill: #39c;
}
</style>
</head>
<body>
<script type="text/javascript">
var w = 960,
h = 500,
alpha = 50,
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");
svg.append("g")
.selectAll("circle")
.data(vertices)
.enter().append("circle")
.attr("r", 3)
.attr("cx", function(d) { return d[0]; })
.attr("cy", function(d) { return d[1]; });
svg.append("g")
.selectAll("path")
.data(d3.geom.delaunay(offset(vertices,300,0)))
.enter().append("path")
.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
svg.append("g")
.selectAll("path")
.data(mesh)
.enter().append("path")
.attr("d", function(d) { return "M" + d.join("L") + "Z"; });
</script>
</body>
</html>
@ziziz9
Copy link

ziziz9 commented Jun 2, 2014

Hi is it possible to have a result without holes ?
Regards

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment