3f:null 40:["$","title",null,{"children":"Triangulation morphing | Alex Lockwood | Observable"}] 46:T2295,{ var svg = d3.select(DOM.svg(width, height)), path = d3.geoPath(); var points = tx.coordinates[0], vertices = points.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, points); svg .append("path") .datum(tx) .attr("class", "background") .attr("d", path); svg.append("path").attr("class", "mesh"); // Asynchronous for demo purposes collapse(topology, 8, done); return svg.node(); function done(pieces) { // Turn MultiPolygon into list of rings var destinations = hi.coordinates.map(function(poly) { return poly[0]; }); // Get array of tweenable pairs of rings var pairs = getTweenablePairs(pieces, destinations); // Collate the pairs into before/after path strings var pathStrings = [ pairs .map(function(d) { return join(d[0]); }) .join(" "), pairs .map(function(d) { return join(d[1]); }) .join(" ") ]; // For showing borderless when rejoined pathStrings.outer = join(points); svg .select(".mesh") .attr("d", pathStrings[0]) .classed("mesh", false) .datum(pathStrings) .each(morph); } function morph(d) { var path = d3.select(this); path .transition() .delay(d.direction ? 0 : 1000) .duration(0) .attr("d", d[0]) .transition() .duration(2500) .attr("d", d[1]) .on("end", function() { d.reverse(); // Show borderless if (!(d.direction = !d.direction)) { path.attr("d", d.outer); } path.each(morph); }); } // Merge polygons into neighbors one at a time until only numPieces remain function collapse(topology, numPieces, cb) { // Show fragment being merged for demo purposes var merging = svg.append("path").attr("class", "merging"); var geometries = topology.objects.triangles.geometries, bisector = d3.bisector(function(d) { return d.area; }).left; if (geometries.length > numPieces) { mergeSmallestFeature(); } // 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]), features; // 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); if (geometries.length > numPieces) { // Don't bother repainting if we're still on tiny triangles if (smallest.area < 50) { return mergeSmallestFeature(); } svg .select(".mesh") .datum(topojson.mesh(topology, topology.objects.triangles)) .attr("d", path); merging.datum(topojson.feature(topology, smallest)).attr("d", path); setTimeout(mergeSmallestFeature, 50); } else { // Merged down to numPieces features = topojson.feature(topology, topology.objects.triangles) .features; d3.selectAll(".background, .merging").remove(); cb( features.map(function(f) { return f.geometry.coordinates[0]; }) ); } } } 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) { // Rearrange order of polygons for least movement start = closestCentroids(start, end); 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++; } } 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]; }); } 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]; } function join(ring) { return "M" + ring.join("L") + "Z"; } } 47:[] 44:{"id":"e6364492cb507d75","slug":"triangulation-morphing","title":"Triangulation morphing","thumbnail":"b970fc62ddeb4f29857cbb1804020732db24899c6872a0da11bcae0ac639bc09","access_level":"public","create_time":"$D2018-03-29T18:36:56.922Z","update_time":"$D2018-03-29T18:53:25.827Z","view_time":null,"first_public_time":"$D2018-03-29T18:54:27.754Z","has_unpublished_edits":null,"fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"6d132976a5d13ae0","login":"alexjlockwood","name":"Alex Lockwood","avatar_url":"https://avatars-next.observableusercontent.com/9202c2d37afa77f4123f2046c8f8db5f34f05f35d361cda0587576ce1b119493","tier":"starter_2024","bio":"","following":false},"version":30,"publish_version":30,"role":null,"authored":false,"authors":[{"type":"individual","id":"c44c7df024fdc0c2","login":"alexjlockwood","name":"Alex Lockwood","avatar_url":"https://avatars-next.observableusercontent.com/9202c2d37afa77f4123f2046c8f8db5f34f05f35d361cda0587576ce1b119493","tier":null,"bio":"","following":false}],"members":[{"type":"individual","id":"c44c7df024fdc0c2","login":"alexjlockwood","name":"Alex Lockwood","avatar_url":"https://avatars-next.observableusercontent.com/9202c2d37afa77f4123f2046c8f8db5f34f05f35d361cda0587576ce1b119493","tier":null,"role":"editor"}],"comments":[{"id":"6e17d3646ada62c2","reply_to_id":null,"content":"This is a port of a block by Noah Veltman: https://bl.ocks.org/veltman/218a162265c772f86bc26c1bc91fe58b","create_time":"$D2021-03-16T17:37:05.079Z","update_time":null,"resolved":false,"user":{"type":"individual","id":"07362516b5994994","login":"mootari","name":"Fabian Iwand","avatar_url":"https://avatars-next.observableusercontent.com/0d7defa821f38094c03bad23b9b360a5364e6e97e21fc238c39ddc48db7994ad","tier":null}}],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Triangulation morphing","cells":[{"id":0,"value":"md`# Triangulation morphing`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"height = 500","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"html`\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"hi = d3.json(\"https://gist.githubusercontent.com/veltman/218a162265c772f86bc26c1bc91fe58b/raw/5f64244b1c2b9617420c1788ed456106a5d17532/HI.json\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"tx = d3.json(\"https://gist.githubusercontent.com/veltman/218a162265c772f86bc26c1bc91fe58b/raw/5f64244b1c2b9617420c1788ed456106a5d17532/TX.json\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"topojson = require(\"https://d3js.org/topojson.v2.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"earcut = require(\"https://unpkg.com/earcut@2.1.1/dist/earcut.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"d3 = require(\"https://d3js.org/d3.v5.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W47","stdlib":"1"}} 45:"$44:body"