Alpha-Shape Bounded Voronoi Tessellation

not fully working

Bounded Voronoi Tesselation using the algorithm described in xlr8r.info and an alpha shape

This is a variant of the Bounded Voronoi Tessellation, with:

sites distributed around two poles
poles are indentified with an alpha-shape (we then use the convex hull of each pole) - thanks to Jason Davies for the boundary() function (aka polygonBoundary)
the median distance instead of the mean (allowing a small optimisation)
many more exterior control points
a d3.curveCatmullRomClosed convex hull shape
not displaying links and sites

Author: Philippe Rivière, August 2016

Based on mbostock's block: Voronoi Tessellation

forked from Fil's block: Circular Bounded Voronoi Tessellation

<!DOCTYPE html>
<meta charset="utf-8">
<style>

.links {
  stroke: #000;
  stroke-opacity: 0;
}

.polygons {
  stroke: #fff;
}

.polygons :first-child {
  fill: #ff3d5a;
}

.sites {
  fill: none;
  stroke: none;
}

.sites :first-child {
  fill: #fff;
}

.convex-hull {
    fill: none;
    stroke: #feccd5;
    stroke-width: 5px;
}

</style>
<svg width="960" height="500"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://d3js.org/d3-scale-chromatic.v1.min.js"></script>
<script>

// Computes boundaries of connected triangles, given an array of triangles.
// Jason Davies - https://bl.ocks.org/jasondavies/1554783
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];
}

var color = d3.scaleOrdinal(d3.schemePastel1),
    line = d3.line().curve(d3.curveCatmullRomClosed);

var sites = d3.range(100)
    .map(function(d) {
      var len = Math.min(width, height) / 4 * (1 - margin) * Math.sqrt(Math.random()),
          angle = Math.random() * 2 * Math.PI;
      
      return [
       (2 * Math.round(4 * Math.random()) + 1) * width / 8 + len * Math.cos(angle),
      height / 2 + len * Math.sin(angle)
    ]; });
  
var voronoi = d3.voronoi()
    .extent([[-1, -1], [width + 1, height + 1]]);

var convexhull = svg.append('path')
  .attr('class', 'convex-hull');

var polygon = svg.append("g")
    .attr("class", "polygons");

var link = svg.append("g")
    .attr("class", "links");

var site = svg.append("g")
    .attr("class", "sites");

redraw();
  
function moved() {
  sites[0] = d3.mouse(this);
  redraw();
}

function redraw() {
  
  var links = voronoi.links(sites),
    ext = Math.sqrt(d3.median(links, function(l) {
      var dx = l.source[0] - l.target[0],
          dy = l.source[1] - l.target[1];
      return dx*dx + dy*dy;
    }));

// compute the alpha-shape boundary
  var sites2 = sites.slice(); // clone
  alphashape(sites, ext*2)
  .forEach(function(hull, i){

convex = d3.polygonHull(hull);
    convex.centroid = d3.polygonCentroid(convex);
  convex = convex.map(function(p){
    var dx = p[0] - convex.centroid[0],
      dy = p[1] - convex.centroid[1],
      angle = Math.atan2(dy, dx);
    return [p[0] + Math.cos(angle) * ext, p[1] + Math.sin(angle) * ext];
  });

for (var i = 0; i < convex.length; i++) {
    var n = convex[i], m = convex[i+1]||convex[0]; 
    var dx = n[0] - m[0],
        dy = n[1] - m[1],
        dist = Math.sqrt(dx * dx + dy * dy);
    var pts = 10 * Math.ceil(dist / 2 / ext);
    for(var j=0; j <= pts; j++) {
      var p = [m[0] + dx *j / pts, m[1] + dy * j / pts];
      p.artificial = 1;
      sites2.push(p);
    }
  }
  });

var diagram = voronoi(sites2);

var p = polygon.selectAll("path") 
    .data(diagram.polygons());
  p.enter().append("path").merge(p).call(redrawPolygon)
  p.exit().remove();

var l = link
    .selectAll("line")
  .data(diagram.links().filter(function(l){
    return !l.source.artificial && !l.target.artificial;
  }));
   l.enter()
     .append("line")
   .merge(l)
     .call(redrawLink)
   .exit()
     .remove();

var s = site
    .selectAll("circle")
    .data(sites);
  s.enter()
      .append("circle")
      .attr("r", 2.5)
  .merge(s)
    .call(redrawSite);

convexhull.attr('d', line(convex));
 
}

function redrawSite(site) {
  site
      .attr("cx", function(d) { return d[0]; })
      .attr("cy", function(d) { return d[1]; });
}

</script>

https://d3js.org/d3.v4.min.js

https://d3js.org/d3-scale-chromatic.v1.min.js