veltman/README.md

## README.md

      
    Raw
  

              README.md
            
          
    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.
See also: Smoother polygon transitions, Triangle morphing #2

  
## index.html
<!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="http://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>

## us.topo.json

      
Display the source blob

    
Display the rendered blob

    
    Raw
  

              us.topo.json
            
          
      Sorry, something went wrong. Reload?
      Sorry, we cannot display this file.
      Sorry, this file is invalid so it cannot be displayed.
      
          Viewer requires iframe.
	<!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="http://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>