jasondavies · January 3, 2012 12:46
diff --git a/index.html b/index.html
 <!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;
  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"; });

 svg.append("g")
  .selectAll("path")
    .data(boundary(mesh))
  .enter().append("path")
    .style("fill", "#fc0")
    .style("fill-opacity", .5)
    .style("stroke-width", 2)
    .attr("d", function(d) { return "M" + d.join("L"); });

 // 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>
	<!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;
	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 dxdx+dydy;
	},

	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"; });

	svg.append("g")
	.selectAll("path")
	.data(boundary(mesh))
	.enter().append("path")
	.style("fill", "#fc0")
	.style("fill-opacity", .5)
	.style("stroke-width", 2)
	.attr("d", function(d) { return "M" + d.join("L"); });

	// 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>