Skip to content

Instantly share code, notes, and snippets.

@veltman
Last active November 25, 2019 20:16
  • Star 6 You must be signed in to star a gist
  • Fork 3 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save veltman/4d1413aa5fd3bb5af1a806c146870031 to your computer and use it in GitHub Desktop.
Smoother polygon transitions

Smooth transitioning US tour in the same vein as this example. Steps:

  1. Compares both shapes and adds evenly-spaced points to whichever polygon has fewer so that both have the same number of points
  2. Picks the winding of the first polygon that minimizes the sum of the squared distances between point pairs

Some possible improvements:

  • Adding additional points to both shapes first such that every segment longer than a certain distance is bisected
  • Tweaking the placement of added points with simulated annealing
  • Using a cost function that factors in self-intersections at the halfway mark in addition to distance traveled
  • Try reversing the order of points too

States are preprojected to appropriate State Plane projections and don't include islands or multipart states (AK, HI, MI).

See also: Jigsaw morphing

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<style>
path {
fill: #e3e3e3;
stroke-width: 1px;
stroke: #666;
}
circle {
stroke: none;
fill: #fc0;
}
.added {
fill: #f0f;
}
</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>
var svg = d3.select("svg"),
path = svg.append("path"),
circles = svg.append("g");
d3.json("us.topo.json", function(err, topo){
var states = topojson.feature(topo, topo.objects.states).features.map(function(d){
return d.geometry.coordinates[0];
});
d3.shuffle(states);
draw();
function draw() {
var a = states[0].slice(0),
b = states[1].slice(0);
// 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);
}
// Pick optimal winding
a = wind(a, b);
path.attr("d", join(a));
// Redraw points
circles.datum(a)
.call(updateCircles);
// Morph
var t = d3.transition()
.duration(800);
path.transition(t)
.on("end", function(){
states.push(states.shift());
setTimeout(draw, 100);
})
.attr("d", join(b));
circles.selectAll("circle").data(b)
.transition(t)
.attr("cx",function(d){
return d[0];
})
.attr("cy",function(d){
return d[1];
});
}
});
function updateCircles(sel) {
var circles = sel.selectAll("circle")
.data(function(d){ return d; });
var merged = circles.enter()
.append("circle")
.attr("r", 2)
.merge(circles);
merged.classed("added", function(d){
return d.added;
})
.attr("cx",function(d){
return d[0];
})
.attr("cy",function(d){
return d[1];
});
circles.exit().remove();
}
function addPoints(ring, numPoints) {
var desiredLength = ring.length + numPoints,
step = d3.polygonLength(ring) / numPoints;
var i = 0,
cursor = 0,
insertAt = step / 2;
do {
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++;
} while (ring.length < desiredLength);
}
function pointBetween(a, b, pct) {
var point = [
a[0] + (b[0] - a[0]) * pct,
a[1] + (b[1] - a[1]) * pct
];
point.added = true;
return point;
}
function distanceBetween(a, b) {
return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));
}
function join(d) {
return "M" + d.join("L") + "Z";
}
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));
}
</script>
Display the source blob
Display the rendered blob
Raw
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@alexjlockwood
Copy link

Just curious... could you explain this possible improvement in a bit more detail? I wasn't sure what you meant.

Using a cost function that factors in self-intersections at the halfway mark in addition to distance traveled

@alexjlockwood
Copy link

I'm also curious about this possible improvement:

Tweaking the placement of added points with simulated annealing

Is there a specific simulated annealing algorithm that could be used here? I assume that you would want to place the points in such a way that minimizes the distance traveled during the morph... but the points are added before the optimal winding is calculated, so I'm not sure how this would be possible.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment