Skip to content

Instantly share code, notes, and snippets.

@veltman

veltman/README.md

Last active September 12, 2020 15:07
Download ZIP

Revisions

  1. veltman revised this gist Nov 4, 2016. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -291,7 +291,7 @@
    bestOffset,
    sum;

    for (var offset = 0, len = ring.length; offset < len; offset++) {
    for (var offset = 0; offset < len; offset++) {

    var sum = d3.sum(vs.map(function(p, i){
    var distance = distanceBetween(ring[(offset + i) % len], p);
  2. veltman revised this gist Oct 25, 2016. 1 changed file with 2 additions and 4 deletions.
    6 changes: 2 additions & 4 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -19,8 +19,6 @@
    <script>

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

    @@ -64,7 +62,7 @@
    pairs = getTweenablePairs(triangulate(fr[0], to.length), to, true);
    }

    g.call(updatePaths, pairs)
    svg.call(updatePaths, pairs)
    .selectAll("path")
    .transition()
    .delay(fr.length > 1 ? 0 : 400)
    @@ -78,7 +76,7 @@
    .on("end", function(){

    if (to.length === 1) {
    g.call(updatePaths, to)
    svg.call(updatePaths, to)
    .selectAll("path")
    .attr("d", join);
    }
  3. veltman revised this gist Oct 24, 2016. 1 changed file with 3 additions and 1 deletion.
    4 changes: 3 additions & 1 deletion README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,5 @@
    Tweening between one and many polygons using [this polygon triangulation method](http://bl.ocks.org/veltman/218a162265c772f86bc26c1bc91fe58b).
    Tweening between one and many polygons with an approach that's faster and more robust than [this Voronoi jigsaw attempt](http://bl.ocks.org/veltman/c582a31d347e04dd75d5331b0074558e).

    This approach uses [earcut](https://github.com/mapbox/earcut) and some artisanal TopoJSON to triangulate the polygon and successively merge the triangles into the desired number of pieces, and then adds/rewinds points for smoother transitions (see [this demo](http://bl.ocks.org/veltman/218a162265c772f86bc26c1bc91fe58b) for a better look at what's happening behind the scenes).

    See also: [Triangulation morphing](http://bl.ocks.org/veltman/218a162265c772f86bc26c1bc91fe58b), [Jigsaw morphing](http://bl.ocks.org/veltman/c582a31d347e04dd75d5331b0074558e), [Smoother polygon transitions](https://bl.ocks.org/veltman/4d1413aa5fd3bb5af1a806c146870031)
  4. veltman created this gist Oct 24, 2016.
    3 changes: 3 additions & 0 deletions README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,3 @@
    Tweening between one and many polygons using [this polygon triangulation method](http://bl.ocks.org/veltman/218a162265c772f86bc26c1bc91fe58b).

    See also: [Triangulation morphing](http://bl.ocks.org/veltman/218a162265c772f86bc26c1bc91fe58b), [Jigsaw morphing](http://bl.ocks.org/veltman/c582a31d347e04dd75d5331b0074558e), [Smoother polygon transitions](https://bl.ocks.org/veltman/4d1413aa5fd3bb5af1a806c146870031)
    482 changes: 482 additions & 0 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,482 @@
    <!DOCTYPE html>
    <html lang="en">
    <head>
    <meta charset="utf-8" />
    <style>

    path {
    stroke: #666;
    fill: #ccc;
    }

    </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://unpkg.com/earcut@2.1.1/dist/earcut.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"),
    g = svg.append("g"),
    path = svg.append("path"),
    width = +svg.attr("width"),
    height = +svg.attr("height");

    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];
    });

    d3.shuffle(states);

    morph(states);

    });

    function morph(states) {

    var source = states.shift(),
    destination = states[0],
    multi = subdivide(source);

    states.push(source);

    d3.queue(1)
    .defer(tween, [source], multi)
    .defer(tween, multi, [destination])
    .await(function(err){
    if (err) throw err;
    morph(states);
    });

    }

    function tween(fr, to, cb) {

    var pairs;

    if (to.length === 1) {
    pairs = getTweenablePairs(fr, triangulate(to[0], fr.length))
    } else {
    pairs = getTweenablePairs(triangulate(fr[0], to.length), to, true);
    }

    g.call(updatePaths, pairs)
    .selectAll("path")
    .transition()
    .delay(fr.length > 1 ? 0 : 400)
    .duration(2500)
    .style("fill", function(d, i){
    return fr.length > 1 ? "#ccc" : d3.interpolateCool(i / pairs.length);
    })
    .attrTween("d", function(d, i){
    return d3.interpolateString(join(d[0]), join(d[1]));
    })
    .on("end", function(){

    if (to.length === 1) {
    g.call(updatePaths, to)
    .selectAll("path")
    .attr("d", join);
    }

    setTimeout(cb, 0);

    })

    }

    function updatePaths(sel, pairs) {

    var paths = sel.selectAll("path")
    .data(pairs);

    paths.enter().append("path");
    paths.exit().remove();

    }

    function triangulate(ring, numPieces) {

    var vertices = ring.reduce(function(arr, point){
    return arr.concat(point);
    }, []),
    cuts = earcut(vertices),
    triangles = [],
    topology;

    for (var i = 0, l = cuts.length; i < l; i += 3) {

    // Save each triangle as segments [a, b], [b, c], [c, a]
    triangles.push([
    [cuts[i], cuts[i + 1]],
    [cuts[i + 1], cuts[i + 2]],
    [cuts[i + 2], cuts[i]]
    ]);

    }

    topology = createTopology(triangles, ring);

    return collapse(topology, numPieces);

    }

    // Merge polygons into neighbors one at a time until only numPieces remain
    function collapse(topology, numPieces) {

    var geometries = topology.objects.triangles.geometries,
    bisector = d3.bisector(function(d) { return d.area; }).left;

    while (geometries.length > numPieces) {
    mergeSmallestFeature();
    }

    return topojson.feature(topology, topology.objects.triangles).features.map(function(f){
    return f.geometry.coordinates[0];
    });

    // Shuffle just for fun
    function mergeSmallestFeature() {

    var smallest = geometries[0],
    neighborIndex = d3.shuffle(topojson.neighbors(geometries)[0])[0],
    neighbor = geometries[neighborIndex],
    merged = topojson.mergeArcs(topology, [smallest, neighbor]);

    // MultiPolygon -> Polygon
    merged.area = smallest.area + neighbor.area;
    merged.type = "Polygon";
    merged.arcs = merged.arcs[0];

    // Delete smallest and its chosen neighbor
    geometries.splice(neighborIndex, 1);
    geometries.shift();

    // Add new merged shape in sorted order
    geometries.splice(bisector(geometries, merged.area), 0, merged);

    }

    }

    function createTopology(triangles, points) {

    var arcIndices = {},
    topology = {
    type: "Topology",
    objects: {
    triangles: {
    "type": "GeometryCollection",
    "geometries": []
    }
    },
    arcs: []
    };

    triangles.forEach(function(triangle){

    var geometry = [];

    triangle.forEach(function(arc, i){

    var slug = arc[0] < arc[1] ? arc.join(",") : arc[1] + "," + arc[0],
    coordinates = arc.map(function(pointIndex){
    return points[pointIndex];
    });

    if (slug in arcIndices) {
    geometry.push(~arcIndices[slug]);
    } else {
    geometry.push(arcIndices[slug] = topology.arcs.length);
    topology.arcs.push(coordinates);
    }

    });

    topology.objects.triangles.geometries.push({
    type: "Polygon",
    area: Math.abs(d3.polygonArea(triangle.map(function(d){
    return points[d[0]];
    }))),
    arcs: [
    geometry
    ]
    });

    });

    // Sort smallest first
    topology.objects.triangles.geometries.sort(function(a, b){
    return a.area - b.area;
    });

    return topology;

    }

    function getTweenablePairs(start, end, out) {

    // Rearrange order of polygons for least movement
    if (out) {
    start = closestCentroids(start, end);
    } else {
    end = closestCentroids(end, start);
    }

    return start.map(function(a, i){
    return align(a.slice(0), end[i].slice(0));
    });

    }

    function align(a, b) {

    // Matching rotation
    if (d3.polygonArea(a) * d3.polygonArea(b) < 0) {
    a.reverse();
    }

    // Smooth out by bisecting long triangulation cuts
    bisectSegments(a, 25);
    bisectSegments(b, 25);

    // 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);
    }

    // Wind the first to minimize sum-of-squares distance to the second
    return [wind(a, b), 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++;

    }

    }

    // Find best winding for first ring of pair
    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));

    }

    // Find ordering of first set that minimizes squared distance between centroid pairs
    // Could loosely optimize instead of trying every permutation (would probably have to with 10+ pieces)
    function closestCentroids(start, end) {

    var min = Infinity,
    best,
    distances = start.map(function(p1){
    return end.map(function(p2){
    var distance = distanceBetween(d3.polygonCentroid(p1), d3.polygonCentroid(p2));
    return distance * distance;
    });
    });

    function permute(arr, order, sum) {

    var cur,
    distance,
    order = order || [],
    sum = sum || 0;

    for (var i = 0; i < arr.length; i++) {
    cur = arr.splice(i, 1);
    distance = distances[cur[0]][order.length];
    if (arr.length) {
    permute(arr.slice(), order.concat(cur), sum + distance);
    arr.splice(i, 0, cur[0]);
    } else if (sum + distance < min) {
    min = sum + distance;
    best = order.concat(cur);
    }
    }

    }

    permute(d3.range(start.length));

    return best.map(function(i){
    return start[i];
    });

    }

    // Bisect any segment longer than x with an extra point
    function bisectSegments(ring, threshold) {
    for (var i = 0; i < ring.length - 1; i++) {

    while (distanceBetween(ring[i], ring[i + 1]) > threshold) {
    ring.splice(i + 1, 0, pointBetween(ring[i], ring[i + 1], 0.5));
    }

    }
    }

    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) {

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

    }

    // Join a ring or array of rings into a path string
    function join(geom) {

    if (typeof geom[0][0] !== "number") {
    return geom.map(join).join(" ");
    }

    return "M" + geom.join("L") + "Z";

    }

    // Given a full-sized ring, return 2 - 6 smaller clones in a dice pattern
    function subdivide(ring) {

    var numClones = 2 + Math.floor(Math.random() * 5),
    bounds = getBounds(ring);

    return d3.range(numClones).map(function(d){
    var x0,
    x1,
    y0,
    y1;

    if (numClones === 2) {
    x0 = d ? width / 2 : 0;
    x1 = x0 + width / 2;
    y0 = 0;
    y1 = height;
    } else if (numClones === 3) {
    x0 = d * width / 3;
    x1 = x0 + width / 3;
    y0 = d * height / 3;
    y1 = y0 + height / 3;
    } else if (numClones === 4) {
    x0 = (d % 2) * width / 2;
    x1 = x0 + width / 2;
    y0 = d < 2 ? 0 : height / 2;
    y1 = y0 + height / 2;
    } else if (numClones === 5) {
    x0 = (d < 2 ? 0 : d === 2 ? 1 : 2) * width / 3;
    x1 = x0 + width / 3;
    y0 = [0, 1, 0.5, 0, 1][d] * height / 2;
    y1 = y0 + height / 2;
    } else {
    x0 = (d % 3) * width / 3;
    x1 = x0 + width / 3;
    y0 = d < 3 ? 0 : height / 2;
    y1 = y0 + height / 2;
    }

    return ring.map(fitExtent([[x0 + 5, y0 + 5], [x1 - 5, y1 - 5]], bounds));

    });

    }

    // Raw fitExtent to avoid some projection stream kinks
    function fitExtent(extent, bounds) {

    var 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 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>
    Binary file added preview.png
    View file
    Loading
    Sorry, something went wrong. Reload?
    Sorry, we cannot display this file.
    Sorry, this file is invalid so it cannot be displayed.
    Binary file added thumbnail.png
    View file
    Loading
    Sorry, something went wrong. Reload?
    Sorry, we cannot display this file.
    Sorry, this file is invalid so it cannot be displayed.
    1 change: 1 addition & 0 deletions us.topo.json
    View file
    1 addition, 0 deletions not shown because the diff is too large. Please use a local Git client to view these changes.