All examples By author By category About

veltman

Full window Github gist

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.

<!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>

https://cdnjs.cloudflare.com/ajax/libs/d3/4.2.3/d3.min.js

https://cdnjs.cloudflare.com/ajax/libs/topojson/1.6.20/topojson.min.js