D3 Examples - Jigsaw morphing

Jigsaw morphing
Tweening between a single polygon (California) and multiple polygons (Hawaii). The basic steps:
Draw a relaxed Voronoi diagram over the single polygon with a bunch of random points.
Traverse the graph and assign cells to islands one at a time, keeping the groups contiguous and roughly proportional in area.
Convert the cells to a topology using Mike Bostock's method and merge each group.
Align the resulting puzzle piece polygon with the destination island for smoother animation using this method.
This isn't totally robust - bad Voronoi luck can result in a weird clipping result that leaves out a chunk. But it works... almost all the time? The breadth-first search of all the cells is also way slower than it needs to be. A hex grid would probably be a lot simpler.
xxxxxxxxxx
 
<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="utf-8" />
  <style>
​
    path {
      fill: #ddd;
    }
​
    .cell {
      opacity: 0.4;
      stroke-width: 1px;
      stroke: #666;
      fill: none;
    }
​
  </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://cdnjs.cloudflare.com/ajax/libs/topojson/1.6.20/topojson.min.js"></script>
<script src="polybool.min.js"></script>
<script>
​
var svg = d3.select("svg"),
    colors;
​
d3.queue()
  .defer(d3.json, "HI.json")
  .defer(d3.json, "CA.json")
  .await(ready);
​
function ready(err, hiGeo, caGeo) {
​
  var diagram,
      ca = caGeo.coordinates[0].slice(0, caGeo.coordinates[0].length - 1),
      hi = hiGeo.coordinates.map(function(d){ return d[0].slice(0, d[0].length - 1); });
​
  colors = hi.map(function(d, i){
    return d3.interpolateRainbow(i / hi.length);
  });
​
  svg.append("path")
    .attr("class", "ca")
    .datum(ca)
    .attr("d", join);
​
  diagram = relaxedVoronoi(ca);
​
  d3.queue(1)
    .defer(wait, 1000)
    .defer(drawCells, diagram.polygons)
    .defer(removeOutsideCells)
    .defer(getGroups, hi, diagram.polygons)
    .defer(merge, hi, diagram)
    .defer(clip, hi, ca)
    .awaitAll(function(err){
      d3.selectAll(".merged").each(morph);
    });
​
}
​
function drawCells(polygons, cb) {
​
  svg.selectAll(".cell")
    .data(polygons)
    .enter()
    .append("path")
      .attr("class", "cell")
      .attr("d", join);
​
  wait(1500, cb);
​
}
​
function removeOutsideCells(cb) {
​
  svg.selectAll(".cell").filter(function(d){
    return d.outside;
  }).remove();
​
  wait(1500, cb);
​
}
​
function getGroups(islands, polygons, cb) {
​
  var areaAssigned = totalArea = 0;
​
  var groups = islands.map(function(island, i){
​
    var area = d3.polygonArea(island);
​
    totalArea += area;
​
    return {
      index: i,
      area: area,
      centroid: d3.polygonCentroid(island),
      targetArea: 0
    };
​
  });
​
  assignCell();
​
  function assignCell() {
​
    if (areaAssigned) {
      // Get the source polygon that's the most under-assigned
      groups.sort(function(a,b){
        return (a.targetArea / areaAssigned) / (a.area / totalArea) - (b.targetArea / areaAssigned) / (b.area / totalArea);
      });
    }
​
    var found = groups.some(function(source){
​
      var closest,
          minDistance = Infinity;
​
      if (!source.head) {
        polygons.forEach(function(cell){
​
          var distance;
​
          if (!cell.outside && cell.assigned === undefined && (distance = distanceBetween(cell.centroid, source.centroid)) < minDistance) {
            minDistance = distance;
            closest = cell;
          }
​
        });
        closest.assigned = source.index;
        source.targetArea += closest.area;
        areaAssigned += closest.area;
        source.head = closest;
        return true;
      }
​
      closest = findAvailableNeighbor(source.head, source.index);
​
      if (closest) {
        closest.assigned = source.index;
        source.targetArea += closest.area;
        areaAssigned += closest.area;
        return true;
      }
​
      return false;
​
    });
​
    svg.selectAll(".cell")
      .style("fill", function(d){
        return colors[d.assigned];
      });
​
    if (found) {
      requestAnimationFrame(assignCell);
    } else {
      cb(null);
    }
​
  }
​
}
​
function merge(hi, diagram, cb) {
​
  var topology = createTopology(diagram.diagram, diagram.polygons);
​
  var merged = d3.range(hi.length).map(function(i){
    return topojson.merge(topology, topology.objects.voronoi.geometries.filter(function(g){return g.properties.assigned === i; })).coordinates[0][0];
  });
​
  svg.selectAll(".merged")
    .data(merged)
    .enter()
    .append("path")
      .attr("class", "merged")
      .attr("d", join)
      .style("fill", function(d, i){
        return colors[i];
      });
​
  svg.selectAll(".cell").remove();
​
  wait(1500, cb);
​
}
​
function clip(hi, ca, cb) {
​
  var merged = svg.selectAll(".merged").data()
    .map(function(d, i){
​
      var island = hi[i],
          clipped = clipPolygon(d, ca);
​
      clipped = align(clipped, island);
​
      return {
        coordinates: [clipped, island],
        color: colors[i],
        split: false,
        first: !i
      };
​
    });
​
  svg.selectAll(".merged")
    .data(merged)
    .attr("d", function(d){
      return join(d.coordinates[0]);
    });
​
  wait(1500, cb);
​
}
​
function morph(d) {
​
  d.coordinates.reverse();
  d.split = !d.split;
​
  var t = d3.select(this).transition()
    .delay(500)
    .duration(3000)
    .style("fill", d.split ? d.color : "#ddd")
    .attr("d", join(d.coordinates[0]))
    .on("end", morph);
​
  if (d.first) {
    t.on(d.split ? "start.bg" : "end.bg", function(){
      d3.select(".ca").style("display", d.split ? "none" : "block");
    });
  }
​
}
​
function relaxedVoronoi(background) {
​
  var bounds = d3.geoPath().bounds({ type: "Polygon", coordinates: [background] }),
      voronoi = d3.voronoi().extent([[bounds[0][0] - 1, bounds[0][1] - 1],[bounds[1][0] + 1, bounds[1][1] + 1]]),
      points = d3.range(300).map(function(){
        return [
          bounds[0][0] + Math.random() * (bounds[1][0] - bounds[0][0]),
          bounds[0][1] + Math.random() * (bounds[1][1] - bounds[0][1])
        ];
      });
​
  diagram = voronoi(points);
​
  for (var i = 0; i < 25; i++) {
    polygons = diagram.polygons();
    diagram = voronoi(polygons.map(d3.polygonCentroid));
  }
​
  polygons.forEach(function(poly, i){
    poly.index = i;
    poly.centroid = d3.polygonCentroid(poly);
    poly.area = d3.polygonArea(poly);
    poly.neighbors = [];
  });
​
  addNeighbors(polygons, diagram.edges, background);
​
  return {
    diagram: diagram,
    polygons: polygons
  };
​
}
​
function addNeighbors(polygons, edges, boundary) {
​
  edges.forEach(function(edge){
​
    if (!edge.left || !edge.right) {
      return;
    }
​
    var left = polygons[edge.left.index],
        right = polygons[edge.right.index];
​
    if (left.outside === undefined) left.outside = isPolygonOutside(left, boundary);
    if (right.outside === undefined) right.outside = isPolygonOutside(right, boundary);
​
    if (!left.outside && !right.outside) {
      left.neighbors.push(right);
      right.neighbors.push(left);
    }
​
  });
​
}
​
// Lazy breadth-first search
function findAvailableNeighbor(head, index) {
​
  var queue = [head],
      visited = {},
      current;
​
  while (queue.length) {
    current = queue.shift();
    if (current.assigned === undefined) {
      return current;
    }
    visited[current.index] = true;
    current.neighbors.forEach(function(neighbor){
      if (!visited[neighbor.index] && (neighbor.assigned === undefined || neighbor.assigned === index)) queue.push(neighbor);
    });
  }
​
  return null;
​
}
​
function align(a, b) {
​
  // 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);
  }
​
  return wind(a, 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,
      backwards = false,
      forwardSum,
      backwardSum;
​
  for (var offset = 0, len = ring.length; offset < len; offset++) {
​
    forwardSum = backwardSum = 0;
​
    // Probably a more efficient way to do this...
    vs.forEach(function(p, i){
      var forwardPos = (offset + i) % len,
          backwardPos = len - offset - i - 1 + (len - offset - i < 1 ? len : 0);
          forwardDistance = distanceBetween(ring[forwardPos], p),
          backwardDistance = distanceBetween(ring[backwardPos], p);
​
      forwardSum += forwardDistance * forwardDistance;
      backwardSum += backwardDistance * backwardDistance;
    });
​
    if (forwardSum < min) {
      min = forwardSum;
      bestOffset = offset;
      backwards = false;
    }
​
    if (backwardSum < min) {
      min = backwardSum;
      bestOffset = offset;
      backwards = true;
    }
​
  }
​
  if (backwards) {
    return ring.slice(len - bestOffset).concat(ring.slice(0, len - bestOffset)).reverse();
  } else {
    return ring.slice(bestOffset).concat(ring.slice(0, bestOffset));
  }
​
}
​
// Assumes a single polygon out, not robust...
function clipPolygon(polygon, boundary) {
  var intersection = PolyBool.intersect({
      regions: [
        polygon
      ],
      inverted: false
    },{
      regions: [
        boundary
      ],
      inverted: false
    });
​
  intersection.regions.sort(function(a,b){
    return d3.polygonArea(b) - d3.polygonArea(a);
  });
​
  return intersection.regions[0];
}
​
function isPolygonOutside(polygon, boundary) {
​
  // Closed rings
  polygon = polygon.concat([polygon[0]]);
  boundary = boundary.concat([boundary[0]]);
​
  if (polygon.some(function(point){ return d3.polygonContains(boundary, point); })) {
    return false;
  }
​
  for (var i = 0, l = polygon.length - 1; i < l; i++) {
    for (var j = 0, m = boundary.length - 1; j < m; j++) {
      if (segmentsIntersect([polygon[i], polygon[i + 1]], [boundary[j], boundary[j + 1]])) {
        return false;
      }
    }
  }
​
  return true;
​
};
​
// TODO deal with points on segments?
function segmentsIntersect(a, b) {
​
  if (orientation(a[0], a[1], b[0]) === orientation(a[0], a[1], b[1])) {
    return false;
  }
​
  return orientation(b[0], b[1], a[0]) !== orientation(b[0], b[1], a[1]);
​
}
​
function orientation(p, q, r) {
​
    var val = (q[1] - p[1]) * (r[0] - q[0]) -
              (q[0] - p[0]) * (r[1] - q[1]);
​
    return val > 0 ? 1 : val < 0 ? -1 : 0;
​
}
​
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) {
​
 var point = [
   a[0] + (b[0] - a[0]) * pct,
   a[1] + (b[1] - a[1]) * pct
 ];
​
 return point;
​
}
​
function join(ring) {
  return "M" + ring.join("L") + "Z";
}
​
function wait(ms, cb) {
  d3.timeout(function(){
    cb(null);
  }, ms);
}
​
// Modified from https://bl.ocks.org/mbostock/cd52a201d7694eb9d890
function createTopology(diagram, polygons) {
  var cells = diagram.cells,
      arcs = [],
      arcIndex = -1,
      arcIndexByEdge = {};
​
  return {
    objects: {
      voronoi: {
        type: "GeometryCollection",
        geometries: cells.map(function(cell, cellNumber) {
          var cell,
              site = cell.site,
              halfedges = cell.halfedges,
              cellArcs = [],
              clipArc;
​
          halfedges.forEach(function(halfedge) {
            var edge = diagram.edges[halfedge];
            if (edge.right) {
              var l = edge.left.index,
                  r = edge.right.index,
                  k = l + "," + r,
                  i = arcIndexByEdge[k];
              if (i == null) arcs[i = arcIndexByEdge[k] = ++arcIndex] = edge;
              cellArcs.push(site === edge.left ? i : ~i);
              clipArc = null;
            } else if (clipArc) { // Coalesce border edges.
              if (edge.left) edge = edge.slice(); // Copy-on-write.
              clipArc.push(edge[1]);
            } else {
              arcs[++arcIndex] = clipArc = edge;
              cellArcs.push(arcIndex);
            }
          });
​
          // Ensure the last point in the polygon is identical to the first point.
          var firstArcIndex = cellArcs[0],
              lastArcIndex = cellArcs[cellArcs.length - 1],
              firstArc = arcs[firstArcIndex < 0 ? ~firstArcIndex : firstArcIndex],
              lastArc = arcs[lastArcIndex < 0 ? ~lastArcIndex : lastArcIndex];
          lastArc[lastArcIndex < 0 ? 0 : lastArc.length - 1] = firstArc[firstArcIndex < 0 ? firstArc.length - 1 : 0].slice();
​
          return {
            type: "Polygon",
            properties: {
              assigned: polygons[cellNumber].assigned
            },
            arcs: [cellArcs]
          };
        }).filter(function(d){ return d.properties.assigned !== undefined; })
      }
    },
    arcs: arcs
  };
}
​
</script>
​
    