All examples By author By category About

veltman

Full window Github gist

Procrustean morphing

Comparing two different approaches to shape transformation:

The top is the interpolation technique in this demo: add points until both shapes have an equal number and then pick the optimal winding order by the sum of squared distances.

The bottom is inspired by Procrustes superimposition, which decomposes the transform necessary to align two shapes into scale, translation, and rotation components. By interpolating those three components separately, it can produce nicer transitions in certain cases (e.g. in the extreme case, a shape turning into a rotated version of itself). But since it's meant for aligning similar shapes with meaningful point-to-point correspondences, it seems to do more harm than good in most cases with two unrelated shapes, though evenly spacing the points around each ring helps.

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="utf-8" />
  <style>
    path {
      fill: salmon;
      stroke-width: 1px;
      stroke: #666;
    }

.interpolated path {
      fill: papayawhip;
    }

.measure {
      display: none;
    }
  </style>
</head>
<body>
<svg xmlns="https://www.w3.org/2000/svg" width="960" height="500">
  <g class="interpolated"></g>
  <g class="procrustean" transform="translate(0 250)"></g>
  <path class="measure"></path>
</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>

var svg = d3.select("svg"),
      width = +svg.attr("width"),
      height = +svg.attr("height"),
      interpolated = svg.select(".interpolated").append("path"),
      procrustean = svg.select(".procrustean").append("path"),
      measure = svg.select(".measure");

d3.json("us.topo.json", function(err, us){

var states = topojson.feature(us, us.objects.states).features.map(function(d){
      return d.geometry.coordinates[0].slice(1);
    });

d3.shuffle(states);

morph(states);

});

function morph(states, dir) {

var a = states.shift(),
        b = states.shift();

states.push(a, b);

a = fitExtent(evenlySpace(a), [[10, 10], [width / 2 - 10, height / 2 - 10]]);
    b = fitExtent(evenlySpace(b), [[width / 2 + 10, 10], [width, height / 2 - 10]]);

var t = interpolateProcrustean(a, b);

interpolatePoints(wind(a, b), b, t)
      .on("end", function(){
        morph(states);
      });

}

function interpolatePoints(a, b, t) {
    return interpolated.datum(a)
      .attr("d", join)
      .datum(b)
      .transition(t)
      .attr("d", join);
  }

function interpolateProcrustean(a, b) {

var parameters = [a, b].map(translateAndScale),
        t;

addRotation(parameters[0], parameters[1].d);
    parameters[1].rotate = 0;

t = d3.transition()
          .delay(250)
          .duration(1750);

procrustean.datum(parameters[0])
      .call(draw)
      .datum(parameters[1])
      .transition(t)
      .call(draw);

return t;

}

function draw(sel) {

sel.attr("transform", function(d){
      return "translate(" + d.translate + ") scale(" + d.scale + " " + d.scale + ") rotate(" + d.rotate + ")";
    })
    .attr("d", function(d){
      return join(d.d);
    })
    .style("stroke-width", function(d){
      return (1 / d.scale) + "px";
    });

}

function evenlySpace(ring) {
    var path = measure.attr("d", join(ring)).node(),
        l = path.getTotalLength();

var points = d3.range(400).map(function(i){
      var p = path.getPointAtLength(l * i / 400);
      return [p.x, p.y];
    });

return points;
  }

function distanceBetween(a, b) {
    return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));
  }

function pointBetween(a, b, pct) {

return [
      a[0] + (b[0] - a[0]) * pct,
      a[1] + (b[1] - a[1]) * pct
    ];

}

function wind(ring, vs) {

var len = ring.length,
        min = Infinity,
        bestOffset,
        sum;

for (var offset = 0; 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));

}

function addRotation(params, vs) {

var ring = params.d,
        len = ring.length,
        min = Infinity,
        wound,
        theta,
        sum;

for (var offset = 0; offset < len; offset++) {

wound = windBy(ring, offset);

theta = getTheta(wound, vs);

sum = d3.sum(wound.map(rotateBy(theta)).map(function(p, i){
        var distance = distanceBetween(vs[i], p);
        return distance * distance;
      }));

if (sum < min) {
        min = sum;
        params.d = wound.map(rotateBy(-theta));
        params.rotate = theta * 180 / Math.PI;
      }

}

function getTheta(ring, vs) {

var num = denom = 0;

ring.forEach(function(point, i){
      num += point[0] * vs[i][1] - point[1] * vs[i][0];
      denom += point[0] * vs[i][0] + point[1] * vs[i][1];
    });

return Math.atan(num / denom);

}

function rotateBy(angle) {

var cos = Math.cos(angle),
        sin = Math.sin(angle);

return function(point) {

var x = point[0],
          y = point[1];

return [
        cos * x - sin * y,
        sin * x + cos * y
      ];

};

}

function join(d) {
    return "M" + d.join("L") + "Z";
  }

function windBy(ring, offset) {
    return ring.slice(offset).concat(ring.slice(0, offset));
  }

function translateAndScale(poly) {

var centroid = d3.polygonCentroid(poly);

var translated = poly.map(function(point){
          return [
            point[0] - centroid[0],
            point[1] - centroid[1]
          ];
        });

var scale = Math.sqrt(d3.sum(translated.map(function(point){
          return Math.sqrt(point[0] * point[0] + point[1] * point[1]);
        })) / poly.length);

var scaled = translated.map(function(point){
      return [
        point[0] / scale,
        point[1] / scale
      ];
    });

return {
      scale: scale,
      translate: centroid,
      d: scaled
    };

}

function fitExtent(ring, extent) {

var bounds = getBounds(ring),
        w = extent[1][0] - extent[0][0],
        h = extent[1][1] - extent[0][1],
        dx = bounds[1][0] - bounds[0][0],
        dy = bounds[1][1] - bounds[0][1],
        k = 1 / Math.max(dx / w, dy / h),
        x = extent[0][0] - k * bounds[0][0] + (w - dx * k) / 2,
        y = extent[0][1] -k * bounds[0][1] + (h - dy * k) / 2;

return ring.map(function(point){

return [
        x + k * point[0],
        y + k * point[1]
      ];

});

}

function getBounds(ring) {

var x0 = y0 = Infinity,
        x1 = y1 = -Infinity;

ring.forEach(function(point){
      if (point[0] < x0) x0 = point[0];
      if (point[0] > x1) x1 = point[0];
      if (point[1] < y0) y0 = point[1];
      if (point[1] > y1) y1 = point[1];
    });

return [
      [x0, y0],
      [x1, y1]
    ];

}

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