Skip to content

Instantly share code, notes, and snippets.

@veltman

veltman/README.md

Last active November 25, 2019 20:16
Show Gist options
  • Save veltman/4d1413aa5fd3bb5af1a806c146870031 to your computer and use it in GitHub Desktop.
Save veltman/4d1413aa5fd3bb5af1a806c146870031 to your computer and use it in GitHub Desktop.
Download ZIP
Smoother polygon transitions
Raw
README.md

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

Raw
index.html
<!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
us.topo.json
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@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