block by emeeks 9aa0478cf739164c9005

Interactive Concave Hull

Full Screen

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

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>

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