31:T839,{ const context = DOM.context2d(width, height), path = d3.geoPath().context(context); // Bind the drag behavior for interaction. d3.select(context.canvas).call( drag(mutable selectors, context.canvas, render) ); d3.select(context.canvas).call( d3 .zoom() .scaleExtent([1, 20]) .on("zoom", () => render(d3.event.transform)) ); function render(transform = d3.zoomTransform(context.canvas)) { context.save(); context.clearRect(0, 0, width, height); context.translate(transform.x, transform.y); context.scale(transform.k, transform.k); context.beginPath(); if (fast_render) { for (const p of edges) { context.moveTo(...pts[p.u]); context.lineTo(...pts[p.v]); } } else { for (let k = 0; k < lines.length; k++) { path({ type: "LineString", coordinates: lines[k] }); } } context.strokeStyle = "#ccc"; context.fillStyle = "#ccc"; context.lineWidth = 1; context.stroke(); // the trees context.lineWidth = 1; var colorIndex = 0; for (let i = 0; i < zones.length; i++) { context.beginPath(); context.strokeStyle = color(colorIndex++); const zone = mutable zones[i]; for (const e of zone.edges) { if (fast_render) { context.moveTo(...pts[edges[e].u]); context.lineTo(...pts[edges[e].v]); } else { path({ type: "LineString", coordinates: lines[e] }); } } context.lineWidth = 1; context.stroke(); } colorIndex = 0; context.lineWidth = 3 / transform.k; for (const s of mutable selectors) { context.beginPath(); const [x, y, k, radius] = [s.x, s.y, transform.k, 10]; context.moveTo(x + radius / k, y); context.arc(x, y, radius / k, 0, 2 * Math.PI); context.fillStyle = color(colorIndex++); context.strokeStyle = "white"; context.fill(); context.stroke(); } context.restore(); return context.canvas; } yield render(); }32:T81e,function* shortest_tree({ graph, origins, cutoff, step }) { const start_time = performance.now(), _step = step === undefined ? 0 : +step, neigh = new Map(); let n = 0; // populate a fast lookup Map of links indices for each source for (let i = 0, l = graph.sources.length; i < l; i++) { const a = +graph.sources[i], b = +graph.targets[i]; if (!neigh.has(a)) neigh.set(a, []); neigh.get(a).push(i); // keep track of the highest node’s id n = Math.max(n, a + 1, b + 1); } const q = new FlatQueue(), front = q.ids, cost = new Float64Array(n).fill(Infinity), predecessor = new Int32Array(n).fill(-1), origin = new Int32Array(n).fill(-1), status = { cost, predecessor, origin, step: 0, front, max_front_size: 0, ended: false }; origins.forEach(node => { if (isFinite(node)) node = { id: node, cost: 0 }; if (node.id < n) { origin[node.id] = node.id; q.push(node.id, (cost[node.id] = node.cost)); } }); const time = performance.now(); while (q.length > 0) { const curr = q.peekValue(), node = q.pop(); if (curr > cost[node]) continue; // ignore obsolete elements if (neigh.has(node)) { for (const i of neigh.get(node)) { const c = graph.costs ? +graph.costs[i] : 1; if (!isFinite(c)) continue; const tentative = c + cost[node]; if (tentative > cutoff) continue; const dest = graph.targets[i]; if (tentative >= 0 && tentative < cost[dest]) { predecessor[dest] = node; origin[dest] = origin[node]; q.push(dest, (cost[dest] = tentative)); status.max_front_size = Math.max(status.max_front_size, front.length); } } } status.step++; if (_step && status.step % _step === 0) { status.performance = performance.now() - time; yield status; } } status.ended = true; status.performance = performance.now() - time; // console.log("Tree", status.performance); yield status; }33:T4f8,update_origins = ids => { mutable origins = ids; const short_tree = shortest_tree({ graph, origins: ids, cutoff: limit_area }).next().value; //add all nodes in zone const zone_nodes = Array.from({ length: ids.length }, () => []); for (let i = 0; i < pts.length; i++) { const j = short_tree.origin[i]; if (j > -1) zone_nodes[ids.indexOf(j)].push(i); } for (let i = 0; i < zone_nodes.length; i++) zone_nodes[i] = [...new Set(zone_nodes[i])]; //add all edges connecting nodes inside zone const zone_edges = Array.from({ length: ids.length }, () => []); for (let z = 0; z < zone_nodes.length; z++) { for (let i = 0; i < zone_nodes[z].length - 1; i++) { const na = nodes[zone_nodes[z][i]]; // console.log(zone_nodes[z].length - i); for (let j = i; j < zone_nodes[z].length; j++) { // var time1 = performance.now(); let neighborIndex = na.neighbors.indexOf(zone_nodes[z][j]); if (neighborIndex > -1) zone_edges[z].push(na.edges[neighborIndex]); // console.log(performance.now() - time1); } } // console.log(zone_edges); mutable zones[z] = { id: ids[z], edges: zone_edges[z], nodes: zone_nodes[z] }; } mutable tree = short_tree; }34:T96b,drag = (selectors, canvas, draw, end) => { // Choose the circle that is closest to the pointer for dragging. function dragsubject(event) { const transform = d3.zoomTransform(canvas); let subject = null; if (!event) event = d3.event; // Distance is expressed in unzoomed coordinates, ie. keeps proportion with circles radius // at any zoom level. let distance = 6; const x = transform.invertX(event.x); const y = transform.invertY(event.y); for (const s of selectors) { let d = Math.hypot(x - s.x, y - s.y); if (d < distance) { distance = d; subject = s; } } return subject ? { selector: subject, x: transform.applyX(subject.x), y: transform.applyY(subject.y) } : null; } // 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() { const transform = d3.zoomTransform(canvas); const agent = d3.event.subject.selector; agent.x = transform.invertX(d3.event.x); agent.y = transform.invertY(d3.event.y); const iterN = 50000; const i = delaunay.find(agent.x, agent.y, agent.id); let needTreeUpdate = agent.id === i ? false : true; if (i) agent.id = i; mutable selectors = mutable selectors; if (needTreeUpdate) update_origins(mutable selectors.map(s => s.id)); draw(); } function dragended() { d3.select(this).style("cursor", "grab"); if (end) end(); const agent = d3.event.subject.selector; const i = delaunay.find(agent.x, agent.y, agent.id); if (i) { agent.x = pts[i][0]; agent.y = pts[i][1]; agent.id = i; } mutable selectors = mutable selectors; update_origins(mutable selectors.map(s => s.id)); draw(); } return function(sel) { sel .style("cursor", "pointer") .call( d3 .drag() .subject(dragsubject) .on("start", dragstarted) .on("drag", dragged) .on("end", dragended) ) .on("mousemove", async function() { const m = d3.mouse(this), subject = await dragsubject({ x: m[0], y: m[1] }); d3.select(this).style("cursor", subject ? "grab" : "pointer"); }); }; }35:[{"id":"1dd9d61949ab0fbda7ef711f94f8edcb63f7279cb7bee53f454826c118079f797e9c069693510ba850896709933c689ae246dced55f476e0afd033ac69d9498e","href":"https://static.observableusercontent.com/files/1dd9d61949ab0fbda7ef711f94f8edcb63f7279cb7bee53f454826c118079f797e9c069693510ba850896709933c689ae246dced55f476e0afd033ac69d9498e","name":"nodes_center_lyon@5.json","type":"application/json","lastModified":1585148710881.541,"size":336505},{"id":"761e56c5666b5d1d01bd0342c158bbd46de3c872065f26ec3fab37e22d7478ad79be45fdbd63c89b0ddc6935df7b3163357db32db421f73325743de092ca39b0","href":"https://static.observableusercontent.com/files/761e56c5666b5d1d01bd0342c158bbd46de3c872065f26ec3fab37e22d7478ad79be45fdbd63c89b0ddc6935df7b3163357db32db421f73325743de092ca39b0","name":"paths_center_lyon@6.json","type":"application/json","lastModified":1585148710881.541,"size":1904337}] 2f:{"title":"Small Lyon Voronoi Full Colored","cells":[{"id":0,"value":"md`# Small Lyon Voronoi Full Colored\n\nI used [Fil's notebook](https://observablehq.com/@fil/manhattan-voronoi-osmnx) and changed the city to Lyon ! Using data from [data.grandlyon.com](https://data.grandlyon.com/jeux-de-donnees/chaussees-trottoirs-metropole-lyon/donnees).\\n\\n\n\nYou can zoom and dezoom (d3.zoom) but you can also grab and move origins thanks to Delaunay.find and d3.drag.\n\nFrom original notebook :\n> Another take on the Manhattan distance —aka [Taxicab geometry](https://en.wikipedia.org/wiki/Taxicab_geometry)—, using the [shortest paths](/@fil/dijkstra) on the _actual graph_ of Manhattan streets (with Geoff Boeing’s [OSMnx](https://github.com/gboeing/osmnx) project data). [Manhattan Voronoi II](https://observablehq.com/@fil/manhattan-voronoi-cells-osmnx) adds contours to the graph. You can also do some kind of [Lloyd’s relaxation](https://observablehq.com/@fil/lloyds-relaxation-on-a-graph) of the map.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":54,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":481,"value":"viewof fast_render = Object.defineProperty(\n html` Fast render`,\n 'value',\n {\n get() {\n return this.querySelector('input').checked;\n }\n }\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":780,"value":"viewof limit_area = slider({\n min: 1,\n max: 3000,\n step: 1,\n value: 1000,\n format: v => `${v} m`,\n title: \"Area limit\",\n description: \"Max distance in km\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":101,"value":"md`**Origins** are the indices of the starting nodes in our shortest-path search:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":808,"value":"mutable zones = mutable origins.map(id => {\n return { id, edges: [], nodes: [] };\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":428,"value":"mutable selectors = Array.from({ length: 5 }, () => {\n const index = (Math.random() * pts.length) | 0;\n return { id: index, x: pts[index][0], y: pts[index][1] };\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":633,"value":"mutable origins = {\n return mutable selectors.map(s => s.id);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":266,"value":"nodes = FileAttachment(\"nodes_center_lyon@5.json\").json()","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"edges = FileAttachment(\"paths_center_lyon@6.json\").json()","pinned":false,"hidden":false,"mode":"ojs"},{"id":384,"value":"bindEdgesWithNodes = {\n nodes.forEach(n => ((n.edges = []), (n.neighbors = [])));\n edges.forEach(({ u, v }, i) => {\n nodes[u].edges.push(i);\n nodes[u].neighbors.push(v);\n nodes[v].edges.push(i);\n nodes[v].neighbors.push(u);\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":115,"value":"md`We build the **graph** in the format expected by our [shortest_tree](/@fil/dijkstra) API:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":31,"value":"function createGraph(edges) {\n const graph = { sources: [], targets: [], costs: [] };\n edges.forEach(({ u, v, length },i) => {\n const cost = length;\n\n graph.sources.push(u);\n graph.targets.push(v);\n graph.costs.push(cost);\n\n graph.sources.push(v);\n graph.targets.push(u);\n graph.costs.push(cost);\n });\n\n return graph;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":40,"value":"graph = createGraph(edges)","pinned":false,"hidden":false,"mode":"ojs"},{"id":44,"value":"mutable tree = shortest_tree({\n graph,\n origins: mutable origins,\n cutoff: limit_area\n}).next().value","pinned":false,"hidden":false,"mode":"ojs"},{"id":108,"value":"md`The **projection** is a Mercator containing all the points:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"pts = nodes.map(d => projection([d.x, d.y]))","pinned":false,"hidden":false,"mode":"ojs"},{"id":347,"value":"lines = edges.map(e => {\n return e.coordinates.map(d => projection([d[0], d[1]]));\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":25,"value":"projection = d3.geoMercator().fitExtent([[10, 10], [width - 10, height - 10]], {\n type: \"MultiPoint\",\n coordinates: nodes.map(d => [d.x, d.y])\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":121,"value":"md`A **color** differentiates the trees associated with each origin:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":69,"value":"color = d3.scaleOrdinal(d3.schemeCategory10)","pinned":false,"hidden":false,"mode":"ojs"},{"id":127,"value":"md`---\n_Project developed for the [LIRIS M2i project](https://projet.liris.cnrs.fr/mi2/) by Pierre Ripoll with tools from Philippe Rivière and Sylvain Lesage._`","pinned":false,"hidden":false,"mode":"ojs"},{"id":811,"value":"bindZonesWithArea = {\n limit_area;\n update_origins(mutable origins);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":706,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":708,"value":"FlatQueue = require(\"flatqueue\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":649,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":424,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":544,"value":"delaunay = d3.Delaunay.from(pts, d => d[0], d => d[1])","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"d3 = require(\"d3@5\", \"d3-delaunay@^5.1\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":27,"value":"height = width * 0.9","pinned":false,"hidden":false,"mode":"ojs"},{"id":777,"value":"import { slider } from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}