Old school D3 from simpler times

All examples By author By category About

enjalot

Full window Github gist

hull padding

forked from jasondavies's block: hull padding

<!DOCTYPE html>
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html;charset=utf-8">
    <title>Alpha-Shapes</title>
    <script src="https://cdn.jsdelivr.net/npm/d3@12.10.3/d3.min.js"></script>
    <script src="https://cdn.jsdelivr.net/npm/d3@12.10.3/d3.geom.min.js"></script>
    <style type="text/css">
      path {
        stroke: #000;
        stroke-width: .5px;
      }
      .regular {
        fill: #39c;
      }
      .pad {
        fill: lightgreen;
      }
      .shrink {
        fill: orange;
      }
    </style>
  </head>
  <body>
    <script type="text/javascript">

var w = 960;
var h = 500;
var alpha = 50;
var padding = 15;
    
var 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")
  .append("g")
.attr("transform", "translate(0, 0)")

svg.append("g").classed("regular", true)
.attr("transform", "translate(-600, 0)")
  .selectAll("path")
    .data(mesh)
  .enter().append("path")
    .attr("d", function(d) { return "M" + d.join("L") + "Z"; });

svg.append("g").classed("pad", true)
.attr("transform", "translate(-300, 0)")
  .selectAll("path")
    .data(mesh)
  .enter().append("path")
    .attr("d", function(d) { return "M" + d.join("L") + "Z"; });
      
svg.append("g").classed("shrink", true)
.attr("transform", "translate(0, 0)")
  .selectAll("path")
    .data(mesh)
  .enter().append("path")
    .attr("d", function(d) { return "M" + d.join("L") + "Z"; });

var bounds = boundary(mesh);

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

var grow = pad(bounds, padding);
console.log(bounds[0], grow[0]);
      
svg.append("g")
.attr("transform", "translate(-300, 0)")
  .selectAll("path")
    .data(grow)
  .enter().append("path")
    .style("fill", "#fc0")
    .style("fill-opacity", .5)
    .style("stroke-width", 2)
    .attr("d", function(d) { return "M" + d.join("L"); });

var shrink = pad(bounds, -padding);
console.log(bounds[0], shrink[0]);
      
svg.append("g")
.attr("transform", "translate(0, 0)")
  .selectAll("path")
    .data(shrink)
  .enter().append("path")
    .style("fill", "#fc0")
    .style("fill-opacity", .5)
    .style("stroke-width", 2)
    .attr("d", function(d) { return "M" + d.join("L"); });
      
function pad(bounds, amount) {
  var result = [];
  bounds.forEach(function(bound) {
    var padded = [];
    
    var area = 0;
    bound.forEach(function(p, i) {
      // https://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)
  }
}
// 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>

Modified http://mbostock.github.com/d3/d3.min.js to a secure url

Modified http://mbostock.github.com/d3/d3.geom.min.js to a secure url

https://mbostock.github.com/d3/d3.min.js

https://mbostock.github.com/d3/d3.geom.min.js