D3 Examples - Triangulation morphing

Triangulation morphing
Tweening between a single polygon (Texas) and multiple polygons (Hawaii) with an approach that's somewhat faster and more robust than this Voronoi jigsaw attempt.
This version uses earcut and some artisanal TopoJSON to triangulate the polygon and successively merge the triangles into the desired number of pieces. Then it uses this method to add points and rewind polygon pairs for smoother transitions.
The biggest area for improvement would probably be a smarter strategy for merging the polygons that factors in the relative areas and positions of the destination shapes like the Voronoi version does, or something that avoids the merge step altogether by only keeping certain cuts during the initial triangulation.
xxxxxxxxxx
 
<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="utf-8" />
  <style>
​
    path {
      stroke: #666;
      fill: #ccc;
    }
​
    .mesh {
      fill: none;
    }
​
    .merging {
      fill: lime;
    }
​
  </style>
</head>
<body>
<svg width="960" height="500"></svg>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/4.2.3/d3.min.js"></script>
<script src="https://unpkg.com/earcut@2.1.1/dist/earcut.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/topojson/1.6.20/topojson.min.js"></script>
<script>
​
var svg = d3.select("svg"),
    path = d3.geoPath();
​
d3.queue()
  .defer(d3.json, "TX.json")
  .defer(d3.json, "HI.json")
  .await(ready);
​
function ready(err, tx, hi) {
​
  var points = tx.coordinates[0],
      vertices = points.reduce(function(arr, point){
        return arr.concat(point);
      }, []),
      cuts = earcut(vertices),
      triangles = [],
      topology;
​
  for (var i = 0, l = cuts.length; i < l; i += 3) {
​
    // Save each triangle as segments [a, b], [b, c], [c, a]
    triangles.push([
      [cuts[i], cuts[i + 1]],
      [cuts[i + 1], cuts[i + 2]],
      [cuts[i + 2], cuts[i]]
    ]);
​
  }
​
  topology = createTopology(triangles, points);
​
  svg.append("path")
    .datum(tx)
    .attr("class", "background")
    .attr("d", path);
​
  svg.append("path")
    .attr("class", "mesh");
​
  // Asynchronous for demo purposes
  collapse(topology, 8, done);
​
  function done(pieces) {
​
    // Turn MultiPolygon into list of rings
    var destinations = hi.coordinates.map(function(poly){
      return poly[0];
    });
​
    // Get array of tweenable pairs of rings
    var pairs = getTweenablePairs(pieces, destinations);
​
    // Collate the pairs into before/after path strings
    var pathStrings = [
      pairs.map(function(d){ return join(d[0]); }).join(" "),
      pairs.map(function(d){ return join(d[1]); }).join(" ")
    ];
​
    // For showing borderless when rejoined
    pathStrings.outer = join(points);
​
    svg.select(".mesh")
      .attr("d", pathStrings[0])
      .classed("mesh", false)
      .datum(pathStrings)
      .each(morph);
​
  }
​
}
​
function morph(d) {
​
  var path = d3.select(this);
​
  path.transition()
    .delay(d.direction ? 0 : 1000)
    .duration(0)
    .attr("d", d[0])
    .transition()
      .duration(2500)
      .attr("d", d[1])
      .on("end", function(){
        d.reverse();
​
        // Show borderless
        if (!(d.direction = !d.direction)) {
          path.attr("d", d.outer);
        }
​
        path.each(morph);
      });
​
}
​
// Merge polygons into neighbors one at a time until only numPieces remain
function collapse(topology, numPieces, cb) {
​
  // Show fragment being merged for demo purposes
  var merging = svg.append("path")
    .attr("class", "merging");
​
  var geometries = topology.objects.triangles.geometries,
      bisector = d3.bisector(function(d) { return d.area; }).left;
​
  if (geometries.length > numPieces) {
    mergeSmallestFeature();
  }
​
  // Shuffle just for fun
  function mergeSmallestFeature() {
​
    var smallest = geometries[0],
        neighborIndex = d3.shuffle(topojson.neighbors(geometries)[0])[0],
        neighbor = geometries[neighborIndex],
        merged = topojson.mergeArcs(topology, [smallest, neighbor]),
        features;
​
    // MultiPolygon -> Polygon
    merged.area = smallest.area + neighbor.area;
    merged.type = "Polygon";
    merged.arcs = merged.arcs[0];
​
    // Delete smallest and its chosen neighbor
    geometries.splice(neighborIndex, 1);
    geometries.shift();
​
    // Add new merged shape in sorted order
    geometries.splice(bisector(geometries, merged.area), 0, merged);
​
    if (geometries.length > numPieces) {
​
      // Don't bother repainting if we're still on tiny triangles
      if (smallest.area < 50) {
        return mergeSmallestFeature();
      }
​
      svg.select(".mesh")
        .datum(topojson.mesh(topology, topology.objects.triangles))
        .attr("d", path);
​
      merging
        .datum(topojson.feature(topology, smallest))
        .attr("d", path);
​
      setTimeout(mergeSmallestFeature, 50);
​
    } else {
​
      // Merged down to numPieces
      features = topojson.feature(topology, topology.objects.triangles).features;
​
      d3.selectAll(".background, .merging").remove();
​
      cb(features.map(function(f){
        return f.geometry.coordinates[0];
      }));
​
    }
​
  }
​
}
​
function createTopology(triangles, points) {
​
  var arcIndices = {},
      topology = {
        type: "Topology",
        objects: {
          triangles: {
            "type": "GeometryCollection",
            "geometries": []
          }
        },
        arcs: []
      };
​
  triangles.forEach(function(triangle){
​
    var geometry = [];
​
    triangle.forEach(function(arc, i){
​
      var slug = arc[0] < arc[1] ? arc.join(",") : arc[1] + "," + arc[0],
          coordinates = arc.map(function(pointIndex){
            return points[pointIndex];
          });
​
      if (slug in arcIndices) {
        geometry.push(~arcIndices[slug]);
      } else {
        geometry.push(arcIndices[slug] = topology.arcs.length);
        topology.arcs.push(coordinates);
      }
​
    });
​
    topology.objects.triangles.geometries.push({
      type: "Polygon",
      area: Math.abs(d3.polygonArea(triangle.map(function(d){
        return points[d[0]];
      }))),
      arcs: [
        geometry
      ]
    });
​
  });
​
  // Sort smallest first
  topology.objects.triangles.geometries.sort(function(a, b){
    return a.area - b.area;
  });
​
  return topology;
​
}
​
function getTweenablePairs(start, end) {
​
  // Rearrange order of polygons for least movement
  start = closestCentroids(start, end);
​
  return start.map(function(a, i){
    return align(a.slice(0), end[i].slice(0));
  });
​
}
​
function align(a, b) {
​
  // Matching rotation
  if (d3.polygonArea(a) * d3.polygonArea(b) < 0) {
    a.reverse();
  }
​
  // Smooth out by bisecting long triangulation cuts
  bisectSegments(a, 25);
  bisectSegments(b, 25);
​
  // Same number of points on each ring
  if (a.length < b.length) {
    addPoints(a, b.length - a.length);
  } else if (b.length < a.length) {
    addPoints(b, a.length - b.length);
  }
​
  // Wind the first to minimize sum-of-squares distance to the second
  return [wind(a, b), b];
​
}
​
function addPoints(ring, numPoints) {
​
  var desiredLength = ring.length + numPoints,
      step = d3.polygonLength(ring) / numPoints;
​
  var i = 0,
      cursor = 0,
      insertAt = step / 2;
​
  while (ring.length < desiredLength) {
​
    var a = ring[i],
        b = ring[(i + 1) % ring.length];
​
    var segment = distanceBetween(a, b);
​
    if (insertAt <= cursor + segment) {
      ring.splice(i + 1, 0, pointBetween(a, b, (insertAt - cursor) / segment));
      insertAt += step;
      continue;
    }
​
    cursor += segment;
    i++;
​
  }
​
}
​
function wind(ring, vs) {
​
  var len = ring.length,
      min = Infinity,
      bestOffset,
      sum;
​
  for (var offset = 0, len = ring.length; offset < len; offset++) {
​
    var sum = d3.sum(vs.map(function(p, i){
      var distance = distanceBetween(ring[(offset + i) % len], p);
      return distance * distance;
    }));
​
    if (sum < min) {
      min = sum;
      bestOffset = offset;
    }
​
  }
​
  return ring.slice(bestOffset).concat(ring.slice(0, bestOffset));
​
}
​
// Find ordering of first set that minimizes squared distance between centroid pairs
// Could loosely optimize instead of trying every permutation (would probably have to with 10+ pieces)
function closestCentroids(start, end) {
​
  var min = Infinity,
      best,
      distances = start.map(function(p1){
        return end.map(function(p2){
          var distance = distanceBetween(d3.polygonCentroid(p1), d3.polygonCentroid(p2));
          return distance * distance;
        });
      });
​
  function permute(arr, order, sum) {
​
    var cur,
        distance,
        order = order || [],
        sum = sum || 0;
​
    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      distance = distances[cur[0]][order.length];
      if (arr.length) {
        permute(arr.slice(), order.concat(cur), sum + distance);
        arr.splice(i, 0, cur[0]);
      } else if (sum + distance < min) {
        min = sum + distance;
        best = order.concat(cur);
      }
    }
​
  }
​
  permute(d3.range(start.length));
​
  return best.map(function(i){
    return start[i];
  });
​
}
​
function bisectSegments(ring, threshold) {
  for (var i = 0; i < ring.length - 1; i++) {
​
    while (distanceBetween(ring[i], ring[i + 1]) > threshold) {
      ring.splice(i + 1, 0, pointBetween(ring[i], ring[i + 1], 0.5));
    }
​
  }
}
​
function distanceBetween(a, b) {
​
  var dx = a[0] - b[0],
      dy = a[1] - b[1];
​
  return Math.sqrt(dx * dx + dy * dy);
​
}
​
function pointBetween(a, b, pct) {
​
  return [
    a[0] + (b[0] - a[0]) * pct,
    a[1] + (b[1] - a[1]) * pct
  ];
​
}
​
function join(ring) {
  return "M" + ring.join("L") + "Z";
}
​
</script>
​
    