31:T628,dragclipped = { const svg = d3.create("svg") .attr("viewBox", [0, 0, width, height]); const g = svg.append("g") .attr("cursor", "grab"); const voronoiLines = g.append("g") .selectAll('line') .data(cleanVoronoi) .join("line") .attr("stroke","#999") .attr("opacity", 0.8) .attr("stroke-width", 0.25) .attr("x1", e => e[0][0]) .attr("y1", e => e[0][1]) .attr("x2", e => e[1][0]) .attr("y2", e => e[1][1]) const origalPolygon = g.append("path") .attr("d", background) .attr("stroke", "black") .attr("stroke-width", 0.25) .attr("fill", "none") const polygonPoints = g.append("g") .selectAll("circle") .data(pointsOnPolygon) .join("circle") .attr("cx", d => d[0]) .attr("cy", d => d[1]) .attr("r", 0.45) .attr("fill", "red"); const innerNodeCircles = g.append("g") .selectAll("circle") .data(innerNodes) .join("circle") .attr("cx", d => d[0]) .attr("cy", d => d[1]) .attr("r", .55) .attr("fill", 'mediumpurple'); const perimeterNodeCircles = g.append("g") .selectAll("circle") .data(perimeterNodes) .join("circle") .attr("cx", d => d[0]) .attr("cy", d => d[1]) .attr("r", .65) .attr("fill", 'dimgray'); svg.call(d3.zoom() .extent([[0, 0], [width, height]]) .scaleExtent([1, 8]) .on("zoom", zoomed)); function zoomed() { g.attr("transform", d3.event.transform); } return svg.node(); }32:T442,nodes = { const nodes = []; // loop over clipped voronoi edges clippedEdges.forEach(edge => { console.log(edge[0]) // add Nodes of each Edge to Nodes array edge.forEach((node, i) => { // if no index or if not is not clipped // so this is only for innerNodes and first node (0th) if (!i || !node.clipped) { // check if node is in nodes array, if so return element // this is to set same id for wellconnected nodes const nodeInNodes = nodes.find(d => d === node); if (nodeInNodes) { // if node is in nodes array return (node.id = nodeInNodes.id); // set node id equal to one already in nodes array } } node.id = nodes.length.toString(); node.links = {}; nodes.push(node); }); const startNode = edge[0]; const endNode = edge[1]; console.log(edge[0]) // set links to connected node startNode.links[endNode.id] = edge.distance; endNode.links[edge[0].id] = edge.distance; }); return nodes; }33:T4a0,dragfinal = { const svg = d3.create("svg") .attr("viewBox", [0, 0, width, height]); const g = svg.append("g") .attr("cursor", "grab"); const origalPolygon = g.append("path") .attr("d", background) .attr("stroke", "plum") .attr("stroke-width", 0.3) .attr("fill", "none") .append("title") .text("The original polygon") // // const traversalCenterline = g.append("path") // .attr("d", d3.geoPath().projection(projection)(centerlineGeoJSON.geometry)) // .attr("stroke", "#444") // .attr("stroke-width", 0.1) // .attr("fill", "none") // .append("title") // .text("The centerline") const finalCenterline = g.append("path") .attr("d", d3.geoPath().projection(projection)(centerlineTraversalGeoJSON.geometry)) .attr("stroke", "indianred") .attr("stroke-width", 0.4) .attr("fill", "none") .append("title") .text("The centerline") svg.call(d3.zoom() .extent([[0, 0], [width, height]]) .scaleExtent([1, 8]) .on("zoom", zoomed)); function zoomed() { g.attr("transform", d3.event.transform); } return svg.node(); }34:T2e63,Graph = { // Observable-compatible stub of Alberto Restifo's node-dijsktra // https://github.com/albertorestifo/node-dijkstra class Queue { /** * Creates a new empty priority queue */ constructor() { // The `keys` set is used to greatly improve the speed at which we can // check the presence of a value in the queue this.keys = new Set(); this.queue = []; } /** * Sort the queue to have the least expensive node to visit on top * * @private */ sort() { this.queue.sort((a, b) => a.priority - b.priority); } /** * Sets a priority for a key in the queue. * Inserts it in the queue if it does not already exists. * * @param {any} key Key to update or insert * @param {number} value Priority of the key * @return {number} Size of the queue */ set(key, value) { const priority = Number(value); if (isNaN(priority)) throw new TypeError('"priority" must be a number'); if (!this.keys.has(key)) { // Insert a new entry if the key is not already in the queue this.keys.add(key); this.queue.push({ key, priority }); } else { // Update the priority of an existing key this.queue.map((element) => { if (element.key === key) { Object.assign(element, { priority }); } return element; }); } this.sort(); return this.queue.length; } /** * The next method is used to dequeue a key: * It removes the first element from the queue and returns it * * @return {object} First priority queue entry */ next() { const element = this.queue.shift(); // Remove the key from the `_keys` set this.keys.delete(element.key); return element; } /** * @return {boolean} `true` when the queue is empty */ isEmpty() { return Boolean(this.queue.length === 0); } /** * Check if the queue has a key in it * * @param {any} key Key to lookup * @return {boolean} */ has(key) { return this.keys.has(key); } /** * Get the element in the queue with the specified key * * @param {any} key Key to lookup * @return {object} */ get(key) { return this.queue.find(element => element.key === key); } } class Graph { /** * Creates a new Graph, optionally initializing it a nodes graph representation. * * A graph representation is an object that has as keys the name of the point and as values * the points reacheable from that node, with the cost to get there: * * { * node (Number|String): { * neighbor (Number|String): cost (Number), * ..., * }, * } * * In alternative to an object, you can pass a `Map` of `Map`. This will * allow you to specify numbers as keys. * * @param {Objec|Map} [graph] - Initial graph definition * @example * * const route = new Graph(); * * // Pre-populated graph * const route = new Graph({ * A: { B: 1 }, * B: { A: 1, C: 2, D: 4 }, * }); * * // Passing a Map * const g = new Map() * * const a = new Map() * a.set('B', 1) * * const b = new Map() * b.set('A', 1) * b.set('C', 2) * b.set('D', 4) * * g.set('A', a) * g.set('B', b) * * const route = new Graph(g) */ constructor(graph) { if (graph instanceof Map) { validateDeep(graph); this.graph = graph; } else if (graph) { this.graph = toDeepMap(graph); } else { this.graph = new Map(); } } /** * Adds a node to the graph * * @param {string} name - Name of the node * @param {Object|Map} neighbors - Neighbouring nodes and cost to reach them * @return {this} * @example * * const route = new Graph(); * * route.addNode('A', { B: 1 }); * * // It's possible to chain the calls * route * .addNode('B', { A: 1 }) * .addNode('C', { A: 3 }); * * // The neighbors can be expressed in a Map * const d = new Map() * d.set('A', 2) * d.set('B', 8) * * route.addNode('D', d) */ addNode(name, neighbors) { let nodes; if (neighbors instanceof Map) { validateDeep(neighbors); nodes = neighbors; } else { nodes = toDeepMap(neighbors); } this.graph.set(name, nodes); return this; } /** * @deprecated since version 2.0, use `Graph#addNode` instead */ addVertex(name, neighbors) { return this.addNode(name, neighbors); } /** * Removes a node and all of its references from the graph * * @param {string|number} key - Key of the node to remove from the graph * @return {this} * @example * * const route = new Graph({ * A: { B: 1, C: 5 }, * B: { A: 3 }, * C: { B: 2, A: 2 }, * }); * * route.removeNode('C'); * // The graph now is: * // { A: { B: 1 }, B: { A: 3 } } */ removeNode(key) { this.graph = removeDeepFromMap(this.graph, key); return this; } /** * Compute the shortest path between the specified nodes * * @param {string} start - Starting node * @param {string} goal - Node we want to reach * @param {object} [options] - Options * * @param {boolean} [options.trim] - Exclude the origin and destination nodes from the result * @param {boolean} [options.reverse] - Return the path in reversed order * @param {boolean} [options.cost] - Also return the cost of the path when set to true * * @return {array|object} Computed path between the nodes. * * When `option.cost` is set to true, the returned value will be an object with shape: * - `path` *(Array)*: Computed path between the nodes * - `cost` *(Number)*: Cost of the path * * @example * * const route = new Graph() * * route.addNode('A', { B: 1 }) * route.addNode('B', { A: 1, C: 2, D: 4 }) * route.addNode('C', { B: 2, D: 1 }) * route.addNode('D', { C: 1, B: 4 }) * * route.path('A', 'D') // => ['A', 'B', 'C', 'D'] * * // trimmed * route.path('A', 'D', { trim: true }) // => [B', 'C'] * * // reversed * route.path('A', 'D', { reverse: true }) // => ['D', 'C', 'B', 'A'] * * // include the cost * route.path('A', 'D', { cost: true }) * // => { * // path: [ 'A', 'B', 'C', 'D' ], * // cost: 4 * // } */ path(start, goal, options = {}) { // Don't run when we don't have nodes set if (!this.graph.size) { if (options.cost) return { path: null, cost: 0 }; return null; } const explored = new Set(); const frontier = new Queue(); const previous = new Map(); let path = []; let totalCost = 0; let avoid = []; if (options.avoid) avoid = [].concat(options.avoid); if (avoid.includes(start)) { throw new Error(`Starting node (${start}) cannot be avoided`); } else if (avoid.includes(goal)) { throw new Error(`Ending node (${goal}) cannot be avoided`); } // Add the starting point to the frontier, it will be the first node visited frontier.set(start, 0); // Run until we have visited every node in the frontier while (!frontier.isEmpty()) { // Get the node in the frontier with the lowest cost (`priority`) const node = frontier.next(); // When the node with the lowest cost in the frontier in our goal node, // we can compute the path and exit the loop if (node.key === goal) { // Set the total cost to the current value totalCost = node.priority; let nodeKey = node.key; while (previous.has(nodeKey)) { path.push(nodeKey); nodeKey = previous.get(nodeKey); } break; } // Add the current node to the explored set explored.add(node.key); // Loop all the neighboring nodes const neighbors = this.graph.get(node.key) || new Map(); neighbors.forEach((nCost, nNode) => { // If we already explored the node, or the node is to be avoided, skip it if (explored.has(nNode) || avoid.includes(nNode)) return null; // If the neighboring node is not yet in the frontier, we add it with // the correct cost if (!frontier.has(nNode)) { previous.set(nNode, node.key); return frontier.set(nNode, node.priority + nCost); } const frontierPriority = frontier.get(nNode).priority; const nodeCost = node.priority + nCost; // Otherwise we only update the cost of this node in the frontier when // it's below what's currently set if (nodeCost < frontierPriority) { previous.set(nNode, node.key); return frontier.set(nNode, nodeCost); } return null; }); } // Return null when no path can be found if (!path.length) { if (options.cost) return { path: null, cost: 0 }; return null; } // From now on, keep in mind that `path` is populated in reverse order, // from destination to origin // Remove the first value (the goal node) if we want a trimmed result if (options.trim) { path.shift(); } else { // Add the origin waypoint at the end of the array path = path.concat([start]); } // Reverse the path if we don't want it reversed, so the result will be // from `start` to `goal` if (!options.reverse) { path = path.reverse(); } // Return an object if we also want the cost if (options.cost) { return { path, cost: totalCost, }; } return path; } /** * @deprecated since version 2.0, use `Graph#path` instead */ shortestPath(...args) { return this.path(...args); } } function validateDeep(map) { if (!(map instanceof Map)) { throw new Error(`Invalid graph: Expected Map instead found ${typeof map}`); } map.forEach((value, key) => { if (typeof value === 'object' && value instanceof Map) { validateDeep(value); return; } if (typeof value !== 'number' || value <= 0) { throw new Error(`Values must be numbers greater than 0. Found value ${value} at ${key}`); } }); } function toDeepMap(source) { const map = new Map(); const keys = Object.keys(source); keys.forEach((key) => { const val = source[key]; if (val !== null && typeof val === 'object' && !Array.isArray(val)) { return map.set(key, toDeepMap(val)); } if (!isValidNode(val)) { throw new Error(`Could not add node at key "${key}", make sure it's a valid node`, val); } return map.set(key, Number(val)); }); return map; } function isValidNode(val) { const cost = Number(val); if (isNaN(cost) || cost <= 0) { return false; } return true; } function removeDeepFromMap(map, key) { const newMap = new Map(); for (const [aKey, val] of map) { if (aKey !== key && val instanceof Map) { newMap.set(aKey, removeDeepFromMap(val, key)); } else if (aKey !== key) { newMap.set(aKey, val); } } return newMap; } return Graph; }35:[{"id":"862c1ff75e2e910db7997a2199a3a5be9136682b36768877a8d44ef7d4037046ed1b885f22df43ddbfbab18a098ec15fb02ca0d7e997fec6cf996e3144b16082","href":"https://static.observableusercontent.com/files/862c1ff75e2e910db7997a2199a3a5be9136682b36768877a8d44ef7d4037046ed1b885f22df43ddbfbab18a098ec15fb02ca0d7e997fec6cf996e3144b16082","name":"amsterdamtransitmap@1.json","type":"application/json","lastModified":1582461947420.712,"size":269547}] 2f:{"title":"[Abandoned] Centerlines from GeoJSON Polygon with d3-voronoi","cells":[{"id":0,"value":"md`# [Abandoned] Centerlines from GeoJSON Polygon with d3-voronoi\n\n\n

Abandoned!This notebook is unfinished and never will be finished, check out [Centerlines from a GeoJSON Polygon with d3-delaunay](https://observablehq.com/@julesblm/clean-centerlines) instead.

\n\n\n[Noah Veltman's centerline labeling](https://observablehq.com/@veltman/centerline-labeling) adapted for getting the centerline of geoJSON polygons of (rail) lines and converting these to LineStrings.\nLike lines [resulting from this turf.js function](https://turfjs.org/docs/#polygonToLine) or from [this little Mapbox tool to convert SVG to geoJSON](https://labs.mapbox.com/svg-to-geojson/).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2268,"value":"md`## The Original geoJSON polygon\nWell, a FeatureCollection of polygons, pick one. It's Amsterdam's [GVB metro/tram rail transit map](https://www.gvb.nl/sites/default/files/railkaart2020.pdf) converted to geoJSON\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1134,"value":"viewof railNum = radio({\n options: railLinesGeoJSON.features.map((f, i) => i.toString()),\n value: \"31\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":108,"value":"{\n const { id, href } = DOM.uid(\"centerline\"); // necessary for Firefox\n return svg``;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1419,"value":"railLine","pinned":false,"hidden":false,"mode":"ojs"},{"id":259,"value":"md`## Step 1: Turn the shape into evenly spaced points\nFirst, we walk the perimeter of the shape to get a set of evenly spaced points that approximate the original shape. Adjust the slider to change how many points we're using (more points = more precision and more computation).\n\n* outerRing applies projection to feature's coordinates\n* getPointsAlongPolyline takes these projected coordinates and return evenly-spaced points along it perimeter\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1620,"value":"md`\n### Idea: Adaptive sampling for curves of polygon\n\n

\nIdeally, the number of perimeter points would be derived from the 'wonkiness' (curvature?) of the polygon. Ie very straight polygons don't require a large number of points while very curvy ones do, could optimize for that\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":273,"value":"viewof numPerimeterPoints = slider({\n min: 500,\n max: 1500,\n step: 50,\n value: 500,\n title: \"Number of perimeter points\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":278,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":127,"value":"pointsOnPolygon = getPointsAlongPolyline(outerRing, numPerimeterPoints)","pinned":false,"hidden":false,"mode":"ojs"},{"id":2933,"value":"railLine","pinned":true,"hidden":false,"mode":"ojs"},{"id":1301,"value":"// Ignore first point because it's in here twice to close the polygon\nouterRing = railLine.geometry.coordinates[0]\n .slice(1)\n .map(applyProjection);","pinned":true,"hidden":false,"mode":"ojs"},{"id":288,"value":"md`## Old Step 2: compute the Voronoi diagram of the points and clip to polygon\nNext, we compute the Voronoi diagram from our generated points, and we clip all the edges to the boundary of our polygon.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":293,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":316,"value":"clipped = {\n let clip = false;\n yield clip;\n while (true) {\n clip = !clip;\n yield Promises.delay(2000, clip);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":520,"value":"voronoi = {\n const [xMin, xMax] = d3.extent(pointsOnPolygon.map(d => d[0]));\n const [yMin, yMax] = d3.extent(pointsOnPolygon.map(d => d[1]));\n\n const leftTop = [xMin - 1, yMin - 1];\n const rightBottom = [xMax + 1, yMax + 1];\n\n return d3.voronoi().extent([leftTop, rightBottom])(pointsOnPolygon).edges;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":173,"value":"filteredEdges = voronoi\n .filter(edge => {\n if (edge && edge.right) {\n // array of booleans\n const inside = edge.map(point =>\n d3.polygonContains(pointsOnPolygon, point)\n );\n\n // necessary for corners\n if (inside[0] === inside[1]) {\n return inside[0]; // boolean\n }\n\n // again why?\n if (inside[1]) {\n edge.reverse();\n }\n return true;\n }\n return false;\n })\n","pinned":true,"hidden":false,"mode":"ojs"},{"id":1989,"value":"// Clip voronoi edges to polygon\nclippedEdges = filteredEdges.map(([start, end] = []) => {\n const { intersection, distance } = originalFindClosestPolygonIntersection(\n start,\n end,\n pointsOnPolygon\n );\n\n if (intersection) {\n intersection.clipped = true;\n }\n\n // Each edge has a starting point, a clipped end point, and an original end point\n const edge = [start, intersection || end];\n edge.distance = intersection ? distance : distanceBetween(start, end);\n\n return edge;\n })","pinned":true,"hidden":false,"mode":"ojs"},{"id":2699,"value":"cleanVoronoi = voronoi.filter(e => e[0][0]) // for drawing only","pinned":false,"hidden":false,"mode":"ojs"},{"id":2676,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":311,"value":"md`## Step 3: Compute a graph from the clipped Voronoi edges\nUse [node-dijkstra](https://github.com/albertorestifo/node-dijkstra) to construct a graph of all the nodes and edges in the Voronoi diagram.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":339,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":207,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":330,"value":"graph = { \n const graph = new Graph();\n nodes.forEach(node => graph.addNode(node.id, node.links));\n return graph;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1476,"value":"innerNodes = nodes.filter(d => !d.clipped)","pinned":true,"hidden":false,"mode":"ojs"},{"id":221,"value":"perimeterNodes = nodes.filter(d => d.clipped)","pinned":false,"hidden":false,"mode":"ojs"},{"id":2794,"value":"viewof speed = radio({\n title: \"Traversal speed\",\n description: \"Slow things down to see each step.\",\n options: [\n { label: \"Slow\", value: \"250\" },\n { label: \"Medium\", value: \"100\" },\n { label: \"Fast\", value: \"0\" }\n ],\n value: \"0\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1487,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":1628,"value":"md`\n## \\`traversal\\` function is bugging sometimes\nSometimes it hangs or skips, taking only a part of the longer line. If this is the case, try increasing the number of perimeter points. Perhaps because new bestPath is longer than existing bestPath from the start🤔?\n\n### Possible improvements to \\`traversal\\`\n* Most graphnodes have only one 'linked' neighbour, could be sped up be selecting those\n* If the polygon is wider and the inner graph branches then traversal is necessary\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2884,"value":"md`### Zoomable end result\nIncrease the number of points (border density) above to reduce jaggedness of the centerline\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2786,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":1488,"value":"// prefer Nodes with more links over those with just one!\ntraversal = {\n let totalBest;\n\n for (let i = 0; i < perimeterNodes.length; i++) {\n const start = perimeterNodes[i];\n const longestShortestPath = perimeterNodes.slice(i + 1).reduce((nodeBest, node) => {\n const path = graph.path(node.id, start.id, { cost: true });\n if (path && (!nodeBest || path.cost > nodeBest.cost)) {\n return path;\n }\n return nodeBest;\n }, null);\n\n if (longestShortestPath && longestShortestPath.path) {\n longestShortestPath.path = longestShortestPath.path.map(id => nodes[+id]);\n\n // Ignore fitnessFunction for now\n \n if (!totalBest || longestShortestPath.cost > totalBest.cost) {\n totalBest = longestShortestPath;\n }\n \n yield Promises.delay(+speed, {\n bestPath: totalBest.path,\n currentPath: longestShortestPath.path\n });\n }\n }\n if (totalBest) {\n yield {\n bestPath: totalBest.path\n };\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2737,"value":"md`## Step 4: Turn the centerline into a geoJSON LineString \n\nRemove the projection from the points and turn it into a geoJSON LineString with a little help of a turf.js function and we're done.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2816,"value":"// ideally, wait until bestPath is finished walking the graph\ncenterlineTraversalGeo = traversal.bestPath.map(removeProjection)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2760,"value":"md`#### Download geoJSON by clicking the three dots left of the cell`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2828,"value":"centerlineTraversalGeoJSON = turf.lineString(centerlineTraversalGeo)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2915,"value":"md`## Step 3 alt: Easy way out: Make a centerline simply by connecting inner nodes`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2877,"value":"md` When simply making a line by connecting the innerNodes, things go bad`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2860,"value":"// innerNodesSvgLine = d3.pairs(innerNodes) // for svg line,","pinned":true,"hidden":false,"mode":"ojs"},{"id":2864,"value":"// geoPointsCenterline = innerNodes.map(removeProjection)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2867,"value":"// centerlineGeoJSON = turf.lineString(geoPointsCenterline)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2,"value":"md`## Appendix`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2914,"value":"md`### Reading material\n\nhttps://smathermather.com/2011/09/16/what-is-the-center-line-of-a-polygon-or-how-to-change-labeling-in-geoserver/\n\n`","pinned":true,"hidden":false,"mode":"ojs"},{"id":1363,"value":"height = Math.min(width / 2, 500)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1360,"value":"railLinesGeoJSON = FileAttachment(\"amsterdamtransitmap@1.json\").json()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1543,"value":"railNum","pinned":true,"hidden":false,"mode":"ojs"},{"id":1250,"value":"railLine = railLinesGeoJSON.features[railNum]","pinned":false,"hidden":false,"mode":"ojs"},{"id":2776,"value":"md`#### Projection`","pinned":false,"hidden":false,"mode":"ojs"},{"id":130,"value":"function getPointsAlongPolyline(polyline, count) {\n // Calculate distance between each point of polyline\n const distances = polyline.map((p, i) => {\n return distanceBetween(p, polyline[i + 1] || polyline[0]);\n });\n\n const totalLength = d3.sum(distances);\n const stepsize = totalLength / count;\n let traversed = 0;\n let next = stepsize / 2;\n\n const done = polyline.reduce((arr, currentPoint, i) => {\n const distanceBetweenCurrentPoints = distances[i];\n while (next < traversed + distanceBetweenCurrentPoints) {\n let nextPoint = polyline[i + 1] || polyline[0];\n\n // What does pct stand for?\n let pct = (next - traversed) / distanceBetweenCurrentPoints;\n arr.push([\n currentPoint[0] + (nextPoint[0] - currentPoint[0]) * pct,\n currentPoint[1] + (nextPoint[1] - currentPoint[1]) * pct\n ]);\n next += stepsize;\n }\n traversed += distanceBetweenCurrentPoints;\n return arr;\n }, []);\n return done;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":106,"value":"// Rescale to fit at the current screen width\nprojection = d3\n .geoIdentity()\n .fitExtent([[5, 5], [width - 5, height - 5]], railLine)","pinned":false,"hidden":false,"mode":"ojs"},{"id":2628,"value":"t = projection.translate();","pinned":true,"hidden":false,"mode":"ojs"},{"id":2630,"value":"s = projection.scale();","pinned":true,"hidden":false,"mode":"ojs"},{"id":2634,"value":"applyProjection = ([x, y]) => [s * x + t[0], s * y + t[1]]","pinned":true,"hidden":false,"mode":"ojs"},{"id":2635,"value":"removeProjection = ([x, y]) => [(x - t[0])/s, (y - t[1])/s]","pinned":true,"hidden":false,"mode":"ojs"},{"id":1357,"value":"background = d3.geoPath().projection(projection)(railLine)","pinned":false,"hidden":false,"mode":"ojs"},{"id":2779,"value":"md`#### Intersection`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1514,"value":"// Used for clipping Voronoi edges to polygon\nfunction originalFindClosestPolygonIntersection(start, end, polygon) {\n return polygon.reduce((best, point, i) => {\n \n // Find intersection between polygon and Voronoi edge\n const intersection = findIntersection(\n start,\n end,\n point,\n polygon[i + 1] || polygon[0]\n );\n \n if (intersection) {\n const distance = distanceBetween(start, intersection);\n if (!best.distance || distance < best.distance) {\n return { intersection, distance };\n }\n }\n \n return best;\n }, {});\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":978,"value":"function findIntersection(a1, a2, b1, b2) {\n // Adapted from https://github.com/Turfjs/turf-line-slice-at-intersection\n const uaT = (b2[0] - b1[0]) * (a1[1] - b1[1]) - (b2[1] - b1[1]) * (a1[0] - b1[0]),\n ubT = (a2[0] - a1[0]) * (a1[1] - b1[1]) - (a2[1] - a1[1]) * (a1[0] - b1[0]),\n uB = (b2[1] - b1[1]) * (a2[0] - a1[0]) - (b2[0] - b1[0]) * (a2[1] - a1[1]);\n\n if (uB !== 0) {\n const ua = uaT / uB,\n ub = ubT / uB;\n if (ua > 0 && ua < 1 && ub > 0 && ub < 1) {\n return [a1[0] + ua * (a2[0] - a1[0]), a1[1] + ua * (a2[1] - a1[1])];\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":981,"value":"function distanceBetween(a, b) {\n const dx = a[0] - b[0],\n dy = a[1] - b[1];\n return Math.sqrt(dx * dx + dy * dy);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2652,"value":"md`# Imports`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2653,"value":"turf = require(\"@turf/turf@5\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":960,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":572,"value":"import {slider, radio} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1152,"value":"styles = html``","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}