30:T6ec,TELEPORT = { await visibility(); const context = DOM.context2d(width, height); yield context.canvas; function drawCell(cell) { if (!cell) return false; context.moveTo(cell[0][0], cell[0][1]); for (var j = 1, m = cell.length; j < m; ++j) { context.lineTo(cell[j][0], cell[j][1]); } context.closePath(); return true; } function draw(quick) { const delaunay = d3.Delaunay.from(teleport), voronoi = delaunay.voronoi([-2, -2, width + 2, height + 2]); for (let j = 0; j < teleport.length; j++) { const point = teleport[j]; context.save(), context.beginPath(), voronoi.renderCell(j, context), context.clip(); context.strokeStyle = "white"; const N = quick ? 10 : 5; for (let i = Math.floor((width + height) / N) * N; i > 0; i -= N) { context.beginPath(); context.fillStyle = color(i); context.arc(point[0], point[1], i, 0, 2 * Math.PI); context.fill(); if (i % 10 === 0) { context.lineWidth = i % 50 === 0 ? 1 : 0.25; context.stroke(); } } context.restore(); } context.lineWidth = 1; context.strokeStyle = "white"; context.setLineDash([5, 10]); context.beginPath(); voronoi.render(context); context.stroke(); context.setLineDash([]); context.lineWidth = 1.5; context.beginPath(), (context.fillStyle = "white"); context.strokeStyle = "black"; teleport.forEach( d => ( context.beginPath(), context.arc(d[0], d[1], 5, 0, 2 * Math.PI), context.fill(), context.stroke() ) ); } draw(); d3.select(context.canvas).call( drag(teleport, draw, () => (mutable teleport = teleport)) ); }31:T41f,COSTS = { await visibility(); const context = DOM.context2d(width, height); yield context.canvas; function draw(quick) { const run = shortest_tree({ origins: [{ id: nodes.length - 1, cost: 0 }], graph: createGraph(nodes) }).next().value; const delaunay = d3.Delaunay.from(nodes); context.fillStyle = "white"; context.fillRect(0, 0, width, height); context.strokeStyle = "#222"; context.lineWidth = 0.4; context.beginPath(); delaunay.render(context); context.stroke(); context.strokeStyle = "red"; context.lineWidth = 4; const r = quick && !stepbystep ? run : run0; r.cost.forEach((cost, i) => { context.fillStyle = color(cost); context.beginPath(); context.arc(...nodes[i], 5, 0, 2 * Math.PI); context.fill(); if (run0.front.includes(i)) context.stroke(); }); draw_starting_points(context, nodes.slice(-1)); } draw(); d3.select(context.canvas).call( drag(nodes.slice(-1), draw, () => (mutable nodes = mutable nodes)) ); }32:T42e,TELEPORT2 = { await visibility(); const context = DOM.context2d(width, height); function draw(quick) { const run = shortest_tree({ origins: [{ id: nodes.length - 1, cost: 0 }], graph: graph2(nodes) }).next().value; context.fillStyle = color(300); context.fillRect(0, 0, width, height); draw_contours(context, nodes, run, { lines: teleport2_draw_options.includes("contours"), labels: teleport2_draw_options.includes("contours"), quick }); if (teleport2_draw_options.includes("connections")) draw_connections(context, nodes, run); draw_special_points( context, nodes.filter((_, i) => teleport2.indexOf(i) > -1) ); if (teleport2_draw_options.includes("points")) draw_points(context, mutable nodes); draw_starting_points(context, nodes.slice(-1)); } draw(); const draggable = nodes.slice(-1).concat(teleport2.map(i => nodes[i])); d3.select(context.canvas).call( drag(draggable, draw, () => (mutable nodes = mutable nodes)) ); return context.canvas; }33:T439,ROADS = { await visibility(); const context = DOM.context2d(width, height); const nodes = roads_nodes; function draw(quick) { const run = shortest_tree({ origins: [{ id: nodes.length - 1, cost: 0 }], graph: roads_graph(nodes) }).next().value; context.clearRect(0, 0, width, height); draw_contours(context, nodes, run, { lines: roads_draw_options.includes("contours"), labels: roads_draw_options.includes("contours"), quick }); context.beginPath(); context.moveTo(0, height / 2); context.lineTo(width, height / 2); context.lineWidth = 8; context.strokeStyle = "lightblue"; context.globalAlpha = 0.4; context.stroke(); context.globalAlpha = 1; if (roads_draw_options.includes("connections")) draw_connections(context, nodes, run); draw_starting_points(context, nodes.slice(-1)); } draw(); const draggable = nodes.slice(-1); d3.select(context.canvas).call( drag(draggable, draw, () => (mutable roads_nodes = mutable roads_nodes)) ); return context.canvas; }34:T43a,function mix_graph() { const graph = { sources: [], targets: [], costs: [] }, nodes = mix_nodes, n = nodes.length, delaunay = d3.Delaunay.from(nodes); for (let i = 0; i < 49; i++) { const j = i + 1; graph.sources.push(i); graph.targets.push(j); graph.costs.push(5); graph.sources.push(j); graph.targets.push(i); graph.costs.push(5); } delaunay.halfedges.forEach((ei, ej) => { if (ei > ej) { const i = delaunay.triangles[ei], j = delaunay.triangles[ej], D = euclidian(nodes[i], nodes[j]); // a small detail: use an alpha-shape to avoid artifacts // with the long Delaunay links on the borders if (D > 30) return; // waterproof: no connection between the two halves if ((nodes[i][0] - width / 2) * (nodes[j][0] - width / 2) <= 0) return; const cost = D * 2.5; graph.sources.push(i); graph.targets.push(j); graph.costs.push(cost); graph.sources.push(j); graph.targets.push(i); graph.costs.push(cost); } }); return graph; }35:T4b6,MIX = { await visibility(); const context = DOM.context2d(width, height); const nodes = mix_nodes; function draw(quick) { const run = shortest_tree({ origins: [{ id: nodes.length - 1, cost: 0 }], graph: mix_graph(nodes) }).next().value; context.clearRect(0, 0, width, height); draw_contours(context, nodes, run, { lines: mix_draw_options.includes("contours"), labels: mix_draw_options.includes("contours"), quick }); context.lineWidth = 2; context.strokeStyle = "darkblue"; context.beginPath(); context.moveTo(width / 2, 0); context.lineTo(width / 2, height); context.stroke(); context.beginPath(); context.moveTo(0, height / 2); context.lineTo(width, height / 2); context.lineWidth = 8; context.strokeStyle = "lightblue"; context.globalAlpha = 0.4; context.stroke(); context.globalAlpha = 1; if (mix_draw_options.includes("connections")) draw_connections(context, nodes, run); draw_starting_points(context, nodes.slice(-1).reverse()); } draw(); const draggable = nodes.slice(-1); d3.select(context.canvas).call(drag(draggable, draw)); return context.canvas; }36:Tb70,// the "Roma" color map from http://www.fabiocrameri.ch/colourmaps.php interpolateRoma = { var colormaps = JSON.parse(` { "Roma":["#7e1900","#801c01","#811f02","#822203","#832504","#852705","#862a06","#872d06","#882f07","#8a3108","#8b3409","#8c360a","#8d380b","#8e3b0c","#8f3d0c","#903f0d","#92410e","#93440f","#944610","#954811","#964a12","#974c13","#984e14","#995015","#9a5315","#9b5516","#9c5717","#9d5918","#9e5b19","#9f5d1a","#a05f1b","#a1611c","#a2631c","#a3651d","#a4671e","#a5691f","#a66b20","#a76d21","#a86f21","#a97122","#aa7323","#ab7524","#ac7725","#ad7926","#ae7c27","#af7e27","#b08028","#b18229","#b2842a","#b3862b","#b4882c","#b58a2d","#b68c2e","#b78e2e","#b8902f","#b99230","#ba9431","#bb9632","#bc9933","#bd9b35","#be9d36","#bf9f37","#c0a138","#c1a339","#c2a63b","#c3a83c","#c4aa3e","#c6ac3f","#c7af41","#c8b143","#c9b344","#cab646","#cbb848","#cdba4a","#cebc4d","#cfbf4f","#d0c151","#d2c354","#d3c556","#d4c859","#d5ca5c","#d6cc5e","#d8ce61","#d9d064","#dad267","#dbd36a","#dcd56c","#ddd76f","#ded872","#dfda75","#e0db78","#e0dc7b","#e1de7e","#e2df80","#e3e083","#e3e186","#e4e289","#e4e38b","#e5e48e","#e5e590","#e5e593","#e6e695","#e6e798","#e6e79a","#e6e89d","#e6e89f","#e6e9a1","#e6e9a4","#e6eaa6","#e6eaa8","#e6ebaa","#e5ebad","#e5ebaf","#e4ecb1","#e4ecb3","#e3ecb5","#e2ecb7","#e1edb9","#e0edba","#dfedbc","#deedbe","#ddedc0","#dbedc1","#daeec3","#d8eec4","#d7eec6","#d5eec7","#d3eec9","#d1edca","#cfedcb","#cdedcc","#cbedcd","#c9edcf","#c6edd0","#c4ecd1","#c1ecd1","#bfecd2","#bcebd3","#b9ebd4","#b7ead5","#b4ead5","#b1e9d6","#aee9d7","#abe8d7","#a8e7d8","#a5e7d8","#a2e6d9","#9fe5d9","#9ce4d9","#99e3da","#96e2da","#93e1da","#90e0da","#8ddfda","#8addda","#87dcdb","#84dbda","#81d9da","#7ed8da","#7bd6da","#78d5da","#75d3da","#73d1d9","#70d0d9","#6eced9","#6bccd8","#69cad8","#67c9d7","#65c7d7","#63c5d6","#61c3d6","#5fc1d5","#5ebfd4","#5cbed4","#5abcd3","#59bad2","#58b8d2","#56b6d1","#55b4d0","#54b2d0","#53b0cf","#52afce","#50adcd","#4fabcd","#4ea9cc","#4da7cb","#4da5ca","#4ca4ca","#4ba2c9","#4aa0c8","#499ec7","#489cc7","#479ac6","#4799c5","#4697c4","#4595c3","#4493c3","#4492c2","#4390c1","#428ec0","#418cc0","#418abf","#4089be","#3f87bd","#3e85bd","#3e84bc","#3d82bb","#3c80bb","#3c7eba","#3b7db9","#3a7bb8","#3979b8","#3978b7","#3876b6","#3774b5","#3773b5","#3671b4","#356fb3","#356eb3","#346cb2","#336ab1","#3369b0","#3267b0","#3165af","#3164ae","#3062ae","#2f61ad","#2f5fac","#2e5dac","#2d5cab","#2d5aaa","#2c59a9","#2b57a9","#2b55a8","#2a54a7","#2952a7","#2951a6","#284fa5","#274da5","#274ca4","#264aa3","#2549a3","#2547a2","#2446a1","#2344a1","#2342a0","#22419f","#213f9f","#203e9e","#1f3c9d","#1f3b9c","#1e399c","#1d379b","#1c369a","#1b349a","#1a3399"] }`); Object.keys(colormaps).forEach(function(scheme) { d3["interpolate" + scheme] = d3.piecewise( d3.interpolateRgb, colormaps[scheme] ); }); return (d3.interpolateColor = t => d3.interpolateRoma(1 - t)); }37:Tacf,// adapted from https://observablehq.com/@fil/contour-labels-canvas function drawLabels(context, contour) { const width = parseInt(context.canvas.style.width), height = (context.canvas.height / context.canvas.width) * width, scale = 1, path = d3.geoPath().context(context); const threshold = contour.value, labels = [], steps = 30; contour.coordinates.forEach(polygon => polygon.forEach((ring, j) => { const p = ring.slice(1, Infinity), // best number of steps to divide ring.length possibilities = d3.range(steps, steps * 1.4), scores = possibilities.map(d => -((p.length - 1) % d)), n = possibilities[d3.scan(scores)], // best starting point: bottom for first rings, top for holes start = 1 + (d3.scan(p.map(xy => (j === 0 ? -1 : 1) * xy[1])) % n), margin = 2; if (p.length < 15) return; // no label on small contours p.forEach((xy, i) => { if ( i % n === start && xy[0] > margin && xy[0] < width - margin && xy[1] > margin && xy[1] < height - margin ) { const a = (i - 2 + p.length) % p.length, b = (i + 2) % p.length, dx = p[b][0] - p[a][0], dy = p[b][1] - p[a][1]; if (dx === 0 && dy === 0) return; labels.push({ threshold, // value xy: xy.map(d => scale * d), angle: Math.atan2(dy, dx), text: `${threshold}` }); } }); }) ); // create the mask for this threshold: // the full rectangle minus a rectangle around each label context.save(); context.beginPath(); context.moveTo(0, 0), context.lineTo(width, 0), context.lineTo(width, height), context.lineTo(0, height), context.lineTo(0, 0); const arc = d3.arc(); for (const label of labels) { for (let i = 0; i < 2 * Math.PI; i += 0.2) { const pos = [Math.cos(i) * 13, -Math.sin(i) * 10], c = Math.cos(label.angle), s = Math.sin(label.angle); context[i === 0 ? "moveTo" : "lineTo"]( label.xy[0] + pos[0] * c - pos[1] * s, label.xy[1] + pos[1] * c + pos[0] * s ); } } // context.stroke(); // uncomment to see the mask context.clip(); // draw white contour for this threshold context.beginPath(); path(contour); context.stroke(); // draw labels for this threshold context.restore(); for (const label of labels) { addlabel(context, label); } function addlabel(context, label) { context.save(); context.translate(...label.xy); context.rotate(label.angle + (Math.cos(label.angle) < 0 ? Math.PI : 0)); context.fillText(label.text, -1, 4); context.restore(); } }38:T5dd,// adapted from https://observablehq.com/@d3/hello-d3-drag drag = (agents, draw, end) => { // When starting a drag gesture, move the subject to the top and mark it as active. function dragstarted() { d3.select(this).style("cursor", "grabbing"); } // When dragging, update the subject’s position. async function dragged(event) { const agent = event.subject; agent[0] = Math.max(0, Math.min(width, event.x)); agent[1] = Math.max(0, Math.min(height, event.y)); await draw(true); } // When ending a drag gesture, mark the subject as inactive again. function dragended() { // d3.event.subject.active = false; d3.select(this).style("cursor", "grab"); if (end) end(); draw(); } function dragsubject(event) { const radius = 30; let subject = null; let distance = radius * 1.5; for (const c of agents) { let d = Math.hypot(event.x - c[0], event.y - c[1]); if (d < distance) { distance = d; subject = c; } } return subject; } return function (sel) { sel .style("cursor", "pointer") .call( d3 .drag() .subject(dragsubject) .on("start", dragstarted) .on("drag", dragged) .on("end", dragended) ) .on("mousemove", function () { const m = d3.mouse(this), subject = dragsubject({ x: m[0], y: m[1] }); d3.select(this).style("cursor", subject ? "grab" : "pointer"); }); }; }39:[] 2e:{"title":"Mobility landscapes — an introduction","cells":[{"id":0,"value":"md`# Mobility landscapes — an introduction\n\nThis notebook creates toy models of transportation networks and introduces a small toolbox that allows to compute the shortest paths on a graph, and draw the results as isochrones.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"md`## The flat landscape\n\nLet us start with the simplest (dumbest) landscape: an empty, flat, plain, uniform terrain, and a single mode of transportation with uniform speed. The shortest path between two points is… the straight line, and the time needed to follow that path is given as ${tex`t = d / v`}, where ${tex`d`} is the euclidian distance and ${tex`v`} the velocity.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"md`Now, let’s fix a starting point. We can draw time by coloring every pixel based on its distance to that point. Isochrones, in this very simple model, are circles — we’ll draw contours for distances of 50 pixels, 100 pixels, etc. (And smaller ones for multiples of 10.)\n\n_Click and drag the starting point to move it to another position._`","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"FLAT = {\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n var start = [rng() * width, rng() * height];\n\n function draw() {\n context.strokeStyle = \"white\";\n for (let i = Math.floor((width + height) / 5) * 5; i > 0; i -= 5) {\n context.beginPath();\n context.fillStyle = color(i);\n context.arc(start[0], start[1], i, 0, 2 * Math.PI);\n context.fill();\n if (i % 10 === 0) {\n context.lineWidth = i % 50 === 0 ? 1 : 0.25;\n context.stroke();\n }\n }\n\n context.lineWidth = 1.5;\n context.beginPath();\n context.fillStyle = \"white\";\n context.strokeStyle = \"black\";\n context.arc(start[0], start[1], 5, 0, 2 * Math.PI);\n context.fill();\n context.stroke();\n }\n\n draw();\n\n d3.select(context.canvas).call(drag([start], draw));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1571,"value":"legend({\n color,\n title: \"Distance (pixels)\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":42,"value":"md`This model is, admittedly, not super interesting. Now, let’s introduce an example from the future: we add a teleportation system, consisting of five stations. From any of these stations, it's possible to teleport to any other station in an instant.\n\nThe solution already presents a much more complex profile. Suppose we start from one of these stations (remember, they are all at a null distance from one another); to draw the distance to any other point, we have to select the teleport station that is the closest to that point. This, in effect, is the same as computing a Voronoi tessellation of the space. Once the starting point has thus been selected, we can paint the same circles as before, making sure we stay in the corresponding Voronoi cell (shown with dashed lines).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1177,"value":"mutable teleport = d3\n .range(5)\n .map(_ => [rng() * width, rng() * height])","pinned":false,"hidden":false,"mode":"ojs"},{"id":63,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":150,"value":"md`Alas, for all its complexity this computation only works when the starting point is one of the teleport stations. Starting from a different point would make an analytical solution intractable. Obviously we are going to have to use a different model.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":173,"value":"md`## Graphs\n\nLet’s focus for a moment on our set of stations. They form a network of points that are connected with instant transportation. We can move to a graph representation of this network: we consider 5 edges (A,B,C,D,E), and 10 connections between them (AB,AC,AD,AE,BC…) — 20 connections if we're using a directed graph.\n\nThe minimum time it takes to reach a certain node from the starting node is defined as a minimization problem on the graph, which can be solved by various graph traversal algorithms.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":182,"value":"FULLY_CONNECTED = {\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n const nodes = teleport;\n function draw() {\n (context.fillStyle = \"white\"), context.fillRect(0, 0, width, height);\n (context.lineWidth = 0.5),\n (context.strokeStyle = \"black\"),\n context.beginPath(),\n nodes.forEach(n0 =>\n nodes.forEach(n1 => (context.moveTo(...n0), context.lineTo(...n1)))\n ),\n context.stroke();\n\n nodes.forEach(\n d => (\n context.beginPath(),\n context.arc(d[0], d[1], 5, 0, 2 * Math.PI),\n context.fill(),\n context.stroke()\n )\n );\n }\n\n draw();\n\n d3.select(context.canvas).call(\n drag(teleport, draw, () => (mutable teleport = teleport))\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":197,"value":"md`This train of thought is, however, not going to get us very far, because if we increase the number of points ${tex`n`}, the number of connections ${tex`n \\times (n-1)`} is going to explode… (That’s also why no transportation system directly connects all pairs of sites: it would be costly, and it would not very useful. On top of it, maps would be very difficult to draw with lines connecting everything to everything.)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1779,"value":"md`## Delaunay graph\n\nAs a first alternative approach, we’ll create a graph by using the Delaunay triangulation. In our graph, only sites that are neighbors in the Delaunay triangulation are connected. A traveller has to hop from one site to its neighbor, until they reach their destination. No jump is allowed between sites that aren’t directly connected, and links between the sites do not overlap.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":277,"value":"mutable nodes = {\n return [\n [0, 0],\n [width, 0],\n [width, height],\n [0, height]\n ]\n .concat([...pick2d(width, height, 2500, \"poissonDisc\")])\n .concat([[width - 50, 50]]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":215,"value":"DELAUNAY = {\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n function draw() {\n context.lineWidth = 0.5;\n context.fillStyle = \"white\";\n context.fillRect(0, 0, width, height);\n const delaunay = d3.Delaunay.from(nodes);\n\n context.strokeStyle = \"black\";\n context.beginPath();\n delaunay.render(context);\n context.stroke();\n\n context.fillStyle = \"#333\";\n nodes.forEach(d => {\n context.beginPath(), context.arc(...d, 2, 0, 2 * Math.PI), context.fill();\n });\n }\n\n draw();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1781,"value":"md`This graph looks a bit more like a map. It’s tempting to set a travel time based on the euclidian distance between connected sites. The difference with the initial flat model is that the paths are now constrained: they can't go from anywhere to everywhere in a straight line, but have to make a series of steps on the graph.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":254,"value":"md`## Dijkstra’s algorithm\n\nTo compute the minimal cost from the starting point to any other vertex on the graph, we’ll use one of the variants of Dijkstra’s shortest-path tree algorithms, available [in its own notebook](https://observablehq.com/d/139ca5ac6fa70e12) — it keeps track of an active front of vertices in a priority queue, and examines their neighbors on the graph, updating the costs and the queue each time a shorter path is discovered. It stops when the queue is empty.\n\nTo consume its API, we need to pass it two data structures:\n- *graph*, an array representing the graph’s links (weighted and directed edges);\n- *origins*: a list of starting points.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":261,"value":"import { shortest_tree } from \"@fil/dijkstra\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":272,"value":"function createGraph(nodes) {\n const graph = { sources: [], targets: [], costs: [] },\n n = nodes.length,\n delaunay = d3.Delaunay.from(nodes);\n\n delaunay.halfedges.forEach((ei, ej) => {\n if (ei > ej) {\n const i = delaunay.triangles[ei],\n j = delaunay.triangles[ej],\n dist = euclidian(nodes[i], nodes[j]);\n\n graph.sources.push(i);\n graph.targets.push(j);\n graph.costs.push(dist);\n\n graph.sources.push(j);\n graph.targets.push(i);\n graph.costs.push(dist);\n }\n });\n\n return graph;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2052,"value":"graph = createGraph(nodes)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1945,"value":"run0 = shortest_tree({\n origins: [nodes.length - 1],\n graph,\n step: stepbystep ? 1 : 0\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":322,"value":"md`Having evaluated the tree of cheapest paths starting at our first point, we can color each vertex of the graph by the evaluated cost.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":325,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":700,"value":"viewof stepbystep = checkbox({\n options: [\"Draw step by step\"],\n description:\n \"Check this option if you want to watch Dijkstra’s algorithm traverse the graph.\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":355,"value":"md`The previous image is difficult to read, because of the high contrast between the white background and the colored vertices. But we can fill the gaps by painting each Voronoi cell with the color of its center site:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":364,"value":"COSTS_VORONOI = {\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n function draw(quick) {\n const run = shortest_tree({\n origins: [{ id: nodes.length - 1, cost: 0 }],\n graph: createGraph(nodes)\n }).next().value;\n\n context.fillStyle = color(300);\n context.fillRect(0, 0, width, height);\n draw_voronoi_cells(context, nodes, run);\n draw_starting_points(context, nodes.slice(-1));\n }\n\n draw();\n d3.select(context.canvas).call(\n drag(nodes.slice(-1), draw, () => (mutable nodes = mutable nodes))\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":807,"value":"md`This map conveys the values quite correctly. However, the result looks like a broken egg shell. Using isolines (created with our [d3-tricontour](https://github.com/Fil/d3-tricontour) library), we can draw much smoother surfaces (from the exact same data):`","pinned":false,"hidden":false,"mode":"ojs"},{"id":860,"value":"COSTS_CONTOURS_NO = {\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n function draw(quick) {\n const run = shortest_tree({\n origins: [{ id: nodes.length - 1, cost: 0 }],\n graph: createGraph(nodes)\n }).next().value;\n\n context.fillStyle = color(300);\n context.fillRect(0, 0, width, height);\n draw_contours(context, nodes, run, { lines: false, quick });\n draw_starting_points(context, nodes.slice(-1));\n }\n\n draw();\n d3.select(context.canvas).call(\n drag(nodes.slice(-1), draw, () => (mutable nodes = mutable nodes))\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":930,"value":"md`As the tricontour library creates the contours as GeoJSON objects, we can also draw them as topographic level lines:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":744,"value":"COSTS_CONTOURS = {\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n function draw(quick) {\n const run = shortest_tree({\n origins: [{ id: nodes.length - 1, cost: 0 }],\n graph: createGraph(nodes)\n }).next().value;\n\n context.fillStyle = color(300);\n context.fillRect(0, 0, width, height);\n draw_contours(context, nodes, run, { lines: true, quick });\n draw_starting_points(context, nodes.slice(-1));\n }\n\n draw();\n d3.select(context.canvas).call(\n drag(nodes.slice(-1), draw, () => (mutable nodes = mutable nodes))\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":940,"value":"md`… and add [contour labels](https://observablehq.com/@fil/contour-labels-canvas):`","pinned":false,"hidden":false,"mode":"ojs"},{"id":933,"value":"COSTS_CONTOURS_WITH_LABELS = {\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n function draw(quick) {\n const run = shortest_tree({\n origins: [{ id: nodes.length - 1, cost: 0 }],\n graph: createGraph(nodes)\n }).next().value;\n\n context.fillStyle = color(300);\n context.fillRect(0, 0, width, height);\n draw_contours(context, nodes, run, { lines: true, labels: true, quick });\n draw_starting_points(context, nodes.slice(-1));\n }\n\n draw();\n d3.select(context.canvas).call(\n drag(nodes.slice(-1), draw, () => (mutable nodes = mutable nodes))\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":382,"value":"md`Now, doesn’t this looks a lot like the “ideal” version we had defined on the first image? But it is based on a totally different model: a topology of interconnected nodes, with arbitrary transfer costs. This is the model we’re going to explore in the following.\n\nFirst, we can ask what happens exactly: how do we reach anywhere at the earliest time possible, from that starting point? To that end, let’s draw the connections that are effectively used from our starting point to reach any of the other sites:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":397,"value":"LINKS = {\n await visibility();\n const context = DOM.context2d(width, height);\n yield context.canvas;\n\n function draw(quick) {\n const run = shortest_tree({\n origins: [{ id: nodes.length - 1, cost: 0 }],\n graph: createGraph(nodes)\n }).next().value;\n\n context.fillStyle = color(300);\n context.fillRect(0, 0, width, height);\n draw_contours(context, nodes, run, { lines: false, quick });\n draw_connections(context, nodes, run);\n draw_starting_points(context, nodes.slice(-1));\n }\n\n draw();\n d3.select(context.canvas).call(\n drag(nodes.slice(-1), draw, () => (mutable nodes = mutable nodes))\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1137,"value":"md`Denote by [A>C] the shortest path from A to C. And note the simple property that, if B is an intermediate point on [A>C], then [A>C] is equal to the concatenation of [A>B] and [B>C]. In other words, what we have drawn here is a spanning tree rooted on A.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1774,"value":"md`## Teleport, again`","pinned":false,"hidden":false,"mode":"ojs"},{"id":451,"value":"md`Let’s go back to the teleportation model. To the Delaunay-defined links of the previous model, we can add instant travel between 5 teleport stations (picked at random and shown in orange). But, with this model, we can pick an arbitrary starting point — it doesn’t need anymore to be one of the teleportation stations.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":478,"value":"mutable teleport2 = d3.range(5).map(_ => (500 * rng()) | 0)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1361,"value":"function graph2(nodes) {\n const graph = { sources: [], targets: [], costs: [] },\n n = nodes.length,\n delaunay = d3.Delaunay.from(nodes);\n\n delaunay.halfedges.forEach((ei, ej) => {\n if (ei > ej) {\n const i = delaunay.triangles[ei],\n j = delaunay.triangles[ej],\n cost = euclidian(nodes[i], nodes[j]);\n\n graph.sources.push(i);\n graph.targets.push(j);\n graph.costs.push(cost);\n\n graph.sources.push(j);\n graph.targets.push(i);\n graph.costs.push(cost);\n }\n });\n\n // add free transport from each teleport station to the others\n teleport2.forEach(i =>\n teleport2.forEach(j => {\n const cost = 0;\n graph.sources.push(i);\n graph.targets.push(j);\n graph.costs.push(cost);\n\n graph.sources.push(j);\n graph.targets.push(i);\n graph.costs.push(cost);\n })\n );\n\n return graph;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":454,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":680,"value":"viewof teleport2_draw_options = checkbox({\n options: [\"points\", \"connections\", \"contours\"],\n description: \"What to draw\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":509,"value":"md`Notice how, if the starting point is on the right-hand side of the landscape, the left-hand side suddenly isn’t that far anymore. The neighborhood of the starting point stays the same (basically, you walk), but once you have reached a teleportation station, you use it and go much farther for free — and sometimes even walk back a bit in the general direction of the starting point. All the orange dots are local minima, except the one that is closest to the starting point, which serves as a gateway to the others.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1771,"value":"md`## Road\n\nIn the following example, we remove the teleportation facility, and replace it with a road that runs in the middle of the landscape—faster than walking, but not instantaneous as the teleport system was.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":511,"value":"mutable roads_nodes = {\n return d3\n .range(50)\n .map((d) => [(d / 50) * width, height / 2])\n .concat([...pick2d(width, height, 2500, \"poissonDisc\")]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1623,"value":"function roads_graph() {\n const graph = { sources: [], targets: [], costs: [] },\n nodes = roads_nodes,\n n = nodes.length,\n delaunay = d3.Delaunay.from(nodes);\n\n delaunay.halfedges.forEach((ei, ej) => {\n if (ei > ej) {\n const i = delaunay.triangles[ei],\n j = delaunay.triangles[ej],\n D = euclidian(nodes[i], nodes[j]);\n\n // a small detail: use an alpha-shape to avoid artifacts\n // with the long Delaunay links on the borders\n if (D > 30) return;\n\n const cost = D * (i < 50 || j < 50 ? 0.1 : 2.5);\n\n graph.sources.push(i);\n graph.targets.push(j);\n graph.costs.push(cost);\n\n graph.sources.push(j);\n graph.targets.push(i);\n graph.costs.push(cost);\n }\n });\n\n return graph;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":516,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":1288,"value":"viewof roads_draw_options = checkbox({\n options: [\"connections\", \"contours\"],\n description: \"What to draw\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1764,"value":"md`In this example, most of the long distance traffic will use the road. If we draw the connections, we can see how local traffic is trying to connect to the roads around the closest possible location.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":563,"value":"md`## River\n\nNow, let’s add a river that flows in the middle and cannot be traversed by foot. You can move the starting point from the left pane to the right pane and vice-versa and verify that the two subgraphs are waterproof.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1368,"value":"mutable river_nodes = [...pick2d(width, height, 2500, \"poissonDisc\")]","pinned":false,"hidden":false,"mode":"ojs"},{"id":1065,"value":"function river_graph(nodes) {\n const graph = { sources: [], targets: [], costs: [] },\n n = nodes.length,\n delaunay = d3.Delaunay.from(nodes);\n\n delaunay.halfedges.forEach((ei, ej) => {\n if (ei > ej) {\n const i = delaunay.triangles[ei],\n j = delaunay.triangles[ej],\n D = euclidian(nodes[i], nodes[j]);\n\n // a small detail: use an alpha-shape to avoid artifacts\n // with the long Delaunay links on the borders\n if (D > 30) return;\n\n // waterproof: no connection between the two halves\n if ((nodes[i][0] - width / 2) * (nodes[j][0] - width / 2) <= 0) return;\n\n const cost = D * 2.5;\n\n graph.sources.push(i);\n graph.targets.push(j);\n graph.costs.push(cost);\n\n graph.sources.push(j);\n graph.targets.push(i);\n graph.costs.push(cost);\n }\n });\n\n return graph;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1068,"value":"RIVER = {\n await visibility();\n const context = DOM.context2d(width, height);\n\n const nodes = river_nodes;\n\n async function draw(quick) {\n const run = shortest_tree({\n origins: [{ id: nodes.length - 1, cost: 0 }],\n graph: river_graph(nodes)\n }).next().value;\n\n context.clearRect(0, 0, width, height);\n draw_contours(context, nodes, run, {\n lines: true,\n labels: true,\n quick\n });\n\n context.lineWidth = 55;\n context.strokeStyle = \"darkblue\";\n context.beginPath();\n context.moveTo(width / 2, 0);\n context.lineTo(width / 2, height);\n context.stroke();\n\n if (false) draw_connections(context, nodes, run);\n draw_starting_points(context, nodes.slice(-1).reverse());\n }\n\n draw();\n const draggable = nodes.slice(-1);\n d3.select(context.canvas).call(drag(draggable, draw));\n\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1716,"value":"md`## Bridge on the river\n\nBy mixing the two preceding approaches, we create a road that is the only way one is allowed to cross the river:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1724,"value":"mutable mix_nodes = {\n return d3\n .range(50)\n .map((d) => [(d / 50) * width, height / 2])\n .concat(\n d3\n .range(50)\n .map((d) => [\n width / 2 + (d % 2 ? -1 : 1),\n Math.floor(d / 100) * height\n ])\n )\n .concat([...pick2d(width, height, 2500, \"poissonDisc\")]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1728,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":1733,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":1756,"value":"viewof mix_draw_options = checkbox({\n options: [\"connections\", \"contours\"],\n description: \"What to draw\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1164,"value":"md`In summary, this notebook shows how to create a toy model of a transportation network as a set of nodes, connected by links that might be directional and arbitrarily weighted. Using Dijkstra’s algorithm and tricontours, we create isochrone maps of models that can include “jumps” (zero-cost transportation), “roads” (lower cost) and “rivers” (higher or infinite cost).\n\nIn the next iterations we’ll apply these tools to analyze more realistic transportation networks, based on actual data and including slower roads, motorways, and public transportation.\n\n_Project developed for the [LIRIS M2i project](https://projet.liris.cnrs.fr/mi2/) by Philippe Rivière. Thanks to [Fabian Iwand](/@mootari) for suggestions._`","pinned":false,"hidden":false,"mode":"ojs"},{"id":27,"value":"md`-----\n_tech zone_`","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":1574,"value":"color = d3\n .scaleSequential(interpolateRoma)\n .domain([0, width])\n .nice()","pinned":true,"hidden":false,"mode":"ojs"},{"id":317,"value":"euclidian = (p, q) => Math.hypot(p[0] - q[0], p[1] - q[1])","pinned":true,"hidden":false,"mode":"ojs"},{"id":2072,"value":"function draw_points(context, points, opts = {}) {\n const TAU = 2 * Math.PI;\n const {radius = 3, fill = \"white\", stroke = \"black\", lineWidth = 1} = opts;\n context.beginPath();\n points.forEach(p => {\n context.moveTo(p[0] + radius, p[1]);\n context.arc(p[0], p[1], radius, 0, TAU);\n });\n if (fill) {\n context.fillStyle = fill;\n context.fill();\n }\n if (stroke && lineWidth) {\n context.lineWidth = lineWidth;\n context.strokeStyle = stroke;\n context.stroke();\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":464,"value":"function draw_special_points(context, points) {\n draw_points(context, points, {fill: \"orange\"});\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":404,"value":"function draw_starting_points(context, points, opts = {}) {\n const radius = 5;\n draw_points(context, points, {radius, lineWidth: 1.5});\n \n context.font = \"14px Arial\";\n context.textBaseline = \"middle\";\n if (points.length > 1 && opts.labels)\n points.forEach((p, i) => {\n context.fillText(\n String.fromCodePoint(\"A\".charCodeAt(0) + i),\n p[0] + radius + 4,\n p[1]\n );\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":429,"value":"function draw_connections(context, nodes, run) {\n context.beginPath();\n run.predecessor.forEach((d, i) => {\n if (d > -1) {\n context.moveTo(...nodes[i]);\n context.lineTo(...nodes[d]);\n }\n });\n context.lineWidth = 0.5;\n context.strokeStyle = \"white\";\n context.stroke();\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":411,"value":"function draw_voronoi_cells(context, nodes, run) {\n const width = parseInt(context.canvas.style.width),\n height = (context.canvas.height / context.canvas.width) * width,\n voronoi = d3.Delaunay.from(nodes).voronoi([0, 0, width, height]);\n\n let i = 0;\n for (const cell of voronoi.cellPolygons()) {\n context.strokeStyle = context.fillStyle = color(run.cost[i]);\n context.beginPath(),\n voronoi.renderCell(i, context),\n context.fill(),\n context.stroke();\n i++;\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":736,"value":"function draw_contours(context, nodes, run, opts = {}) {\n const path = d3.geoPath().context(context),\n contours = d3.tricontour().thresholds(opts.quick ? 50 : 300)(\n nodes.map((d, i) => [d[0], d[1], run.cost[i]]).filter(d => isFinite(d[2]))\n );\n\n context.lineWidth = 1;\n for (const c of contours) {\n context.strokeStyle = context.fillStyle = color(c.value);\n context.beginPath();\n path(c);\n context.fill();\n context.stroke();\n }\n\n if (opts.lines) {\n context.strokeStyle = \"white\";\n context.fillStyle = \"white\";\n context.textAlign = \"center\";\n context.font = \"12px Arial\";\n context.globalAlpha = 1;\n for (const c of contours) {\n if (c.value % 20 === 0) {\n context.lineWidth = c.value % 100 === 0 ? 1 : 0.5;\n if (opts.labels && !opts.quick && c.value % 100 === 0) {\n drawLabels(context, c);\n } else {\n context.beginPath();\n path(c);\n context.stroke();\n }\n }\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":944,"value":"$37","pinned":true,"hidden":false,"mode":"ojs"},{"id":1302,"value":"$38","pinned":true,"hidden":false,"mode":"ojs"},{"id":814,"value":"import { pick2d } from \"@fil/2d-point-distributions\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":1812,"value":"height = 400","pinned":true,"hidden":false,"mode":"ojs"},{"id":30,"value":"d3 = require(\"d3@7\", \"d3-tricontour@0.1\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":1569,"value":"import { legend } from \"@d3/color-legend\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":1268,"value":"import { checkbox } from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":2116,"value":"rng = Math.random","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W39","stdlib":"1","titling":"auto"}