2b:null 2c:["$","title",null,{"children":"Centerline labeling | John Alexis Guerra Gómez | Observable"}] 31:T545,measurements = { const svg = DOM.svg(width, height); const path = d3 .select(svg) .append("path") .attr("d", centerline) .node(); const length = path.getTotalLength(); const measurements = []; for ( let halfwidth = 0; halfwidth < Math.min(length * offset, length * (1 - offset)); halfwidth += measurementStep ) { measurements.push( [length * offset + halfwidth, length * offset - halfwidth] .map(l => { const { x, y } = path.getPointAtLength(l), tangent = tangentAt(path, l); const perpendiculars = [tangent - Math.PI / 2, tangent + Math.PI / 2] .map(angle => findClosestPolygonIntersection( [x, y], rotatePoint([x + width, y], angle, [x, y]), polygon ) ) .filter(d => d.intersection) .sort((a, b) => a.distance - b.distance); if (!perpendiculars.length) { return null; } const { intersection, distance } = perpendiculars[0]; const line = [ intersection, [2 * x - intersection[0], 2 * y - intersection[1]] ]; line.distance = distance; return line; }) .filter(d => d) ); } return measurements; }32: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; }33:[] 2f:{"id":"e5c8afb47faab9dd","slug":"centerline-labeling","title":"Centerline labeling","thumbnail":"a0e73fbe5c3dfd7e3cbf0b5dda418c2aa7bf80d46152a21be370acf9537ac7e3","access_level":"public","create_time":"$D2018-05-30T00:18:23.199Z","update_time":"$D2020-10-19T03:02:22.154Z","view_time":null,"first_public_time":"$D2018-05-30T00:35:16.983Z","fork":{"id":"dedd94ed26f7e1ce","slug":"centerline-labeling","title":"Centerline labeling","owner":{"id":"c0d6ef9833202f4b","login":"veltman","name":"Noah Veltman"}},"stars":2,"starred":false,"owner":{"type":"team","id":"cd3c1e49fc84d010","login":"john-guerra","name":"John Alexis Guerra Gómez","avatar_url":"https://avatars-next.observableusercontent.com/21638cee44bb0ea70798da725b57111a5d3e2acebcd14524565992f7d1594aed","tier":"starter_2024"},"version":1465,"publish_version":1465,"role":null,"authored":false,"authors":[{"type":"individual","id":"be0076fec73aa550","login":"john-guerra","name":"John Alexis Guerra Gómez","avatar_url":"https://avatars-next.observableusercontent.com/21638cee44bb0ea70798da725b57111a5d3e2acebcd14524565992f7d1594aed","tier":null}],"members":[{"type":"individual","id":"be0076fec73aa550","login":"john-guerra","name":"John Alexis Guerra Gómez","avatar_url":"https://avatars-next.observableusercontent.com/21638cee44bb0ea70798da725b57111a5d3e2acebcd14524565992f7d1594aed","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Centerline labeling","cells":[{"id":0,"value":"md`# Centerline labeling\n\nForking Noah Veltman's observable with Colombian shapes. An explorable calculator for placing curved labels inside weird shapes.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1134,"value":"viewof place = radio({\n // Need to quote multi-word values\n options: places.objects.depts.geometries.map(f => ({ label: f.properties.dpt, value: f.properties.dpt })),\n value: `SANTAFE DE BOGOTA D.C`\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":108,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"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`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":273,"value":"viewof numPerimeterPoints = slider({\n min: 10, \n max: 200, \n step: 1, \n value: 50,\n title: \"Number of perimeter points\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":278,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":127,"value":"polygon = getPointsAlongPolyline(outerRing, numPerimeterPoints)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1301,"value":"outerRing = {\n const s = projection.scale(),\n t = projection.translate();\n\n return feature.geometry.coordinates[0]\n .slice(1)\n .map(point => [s * point[0] + t[0], t[1] - s * point[1] ]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":288,"value":"md`## Step 2: compute the Voronoi diagram of the points\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","author":"$undefined","summary":"$undefined"},{"id":293,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":316,"value":"clipped = {\n let clip = false;\n yield clip;\n while (true) {\n clip = !clip;\n yield Promises.delay(1000, clip);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":520,"value":"voronoi = {\n const [x0, x1] = d3.extent(polygon.map(d => d[0])),\n [y0, y1] = d3.extent(polygon.map(d => d[1]));\n\n return d3.voronoi().extent([[x0 - 1, y0 - 1], [x1 + 1, y1 + 1]])(polygon).edges;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":173,"value":"edges = voronoi\n .filter(edge => {\n if (edge && edge.right) {\n const inside = edge.map(point => d3.polygonContains(polygon, point));\n if (inside[0] === inside[1]) {\n return inside[0];\n }\n if (inside[1]) {\n edge.reverse();\n }\n return true;\n }\n return false;\n })\n .map(([start, end] = []) => {\n const { intersection, distance } = findClosestPolygonIntersection(\n start,\n end,\n polygon\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":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"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","author":"$undefined","summary":"$undefined"},{"id":339,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":330,"value":"graph = { \n const graph = new Graph();\n nodes.forEach(node => graph.addNode(node.id, node.links));\n return graph;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":207,"value":"nodes = {\n const nodes = [];\n\n edges.forEach(edge => {\n edge.forEach((node, i) => {\n if (!i || !node.clipped) {\n const match = nodes.find(d => d === node);\n if (match) {\n return (node.id = match.id);\n }\n }\n node.id = nodes.length.toString();\n node.links = {};\n nodes.push(node);\n });\n edge[0].links[edge[1].id] = edge.distance;\n edge[1].links[edge[0].id] = edge.distance;\n });\n\n return nodes;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":221,"value":"perimeterNodes = nodes.filter(d => d.clipped)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":353,"value":"md`## Step 4: walk the graph and find the best path\nFor each pair of perimeter nodes, find the shortest path between them. Keep the longest one we find, or use a strategy that also factors in how straight the line is.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":423,"value":"viewof strategy = radio({\n title: \"Optimization strategy\",\n description: \"edit fitnessFunction() below to create a custom strategy!\",\n options: [\n { label: \"Just take the longest one\", value: \"longest\" },\n { label: \"Care a little about straightness\", value: \"medium\" },\n { label: \"Care a lot about straightness\", value: \"high\" }\n ],\n value: \"medium\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":358,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":382,"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","author":"$undefined","summary":"$undefined"},{"id":361,"value":"traversal = {\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 longestShortestPath.cost = fitnessFunction(longestShortestPath.path, longestShortestPath.cost);\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":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":421,"value":"md`## Step 5: simplify the best line\nWe can use [simplify-js](http://mourner.github.io/simplify-js/) and a basis spline to smooth out our best candidate, and flip the direction of the line if the text would be upside down.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":426,"value":"viewof simplification = slider({\n min: 0.1, \n max: 50, \n value: 8,\n title: \"Simplification tolerance\",\n description: \"How much should we simplify the best line once we find it?\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":434,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":429,"value":"simplifiedLine = simplify(traversal.bestPath)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":257,"value":"flipText = {\n const svg = DOM.svg(width, height);\n \n const path = d3.select(svg)\n .append(\"path\")\n .attr(\"d\", \"M\" + simplifiedLine.join(\"L\"))\n .node();\n\n const tangent = tangentAt(path, path.getTotalLength() * offset);\n\n return Math.abs(tangent) > Math.PI / 2;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":491,"value":"centerline = d3.line().curve(d3.curveBasis)(flipText ? simplifiedLine.slice(0).reverse() : simplifiedLine)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":451,"value":"md`## Step 7: choose the best offset and font size\nAs a final step, we can roughly estimate how large we can make the text without overrunning the shape's borders.\n\nWe'll approximate this by walking the centerline from the middle out, and measuring the shortest perpendicular distance from the center to the boundary at each step. Combined with the aspect ratio of the text, we then know roughly how large we can make the text without it overrunning the containing shape's border.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":732,"value":"viewof measurementStep = slider({\n min: 1, \n max: 25, \n value: 5,\n title: \"Measurement step\",\n description: \"How frequently should we measure the available space?\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1171,"value":"viewof offset = slider({\n min: 0.01, \n max: 0.99, \n value: 0.5,\n title: \"Text offset\",\n description: \"How far along the path should we place the label? (0.5 = the center)\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":740,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":728,"value":"maxFontSize = {\n let ceiling = Infinity,\n maxWidth = 0;\n \n measurements.forEach((pair, i) => {\n pair.forEach(measurement => {\n ceiling = Math.min(measurement.distance, ceiling);\n });\n maxWidth = Math.max(maxWidth, 2 * Math.min(i * measurementStep, ceiling * aspectRatio));\n });\n \n return maxWidth / widthPerPixel;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":724,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":710,"value":"aspectRatio = bbox.width / bbox.height","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":712,"value":"widthPerPixel = bbox.width / 100","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":676,"value":"bbox = {\n const svg = DOM.svg(width, height);\n\n const text = d3.select(svg)\n .append(\"text\")\n .attr(\"class\", \"label\")\n .style(\"font-size\", \"100px\")\n .text(place)\n .node();\n \n // Have to yield the SVG first before element has a measurable width and height\n yield svg;\n yield text.getBBox();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1245,"value":"md`## Epilogue: other potential exercises\n\n1. Rather than manually select the starting offset along the path, we could [automatically find the roomiest offset](https://bl.ocks.org/veltman/6204863ae290904fbae83ca5490d4b1b).\n2. We could do a side-by-side comparison of the results of this approach vs. a flat label using [Polylabel](https://github.com/mapbox/polylabel) for different kinds of shapes and see where it tends to break down.\n3. We could make a label span multiple shapes, like the Hawaiian Islands, by using the [concave hull](https://github.com/mapbox/concaveman) of the group of shapes as the basis for all our operations.\n4. Sinuosity might not be the best choice for a fitness function, we could come up with some other heuristic that factors in some other sense of straightness or smoothness of the centerline.\n5. We could avoid using \\`.getPointAtLength()\\` for measurement and do everything with DOM-less math for better performance (but maybe more verbose code).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2,"value":"md`## Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1363,"value":"height = Math.min(width / 2, 400)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1360,"value":"places = d3.json(\"https://gist.githubusercontent.com/john-guerra/727e8992e9599b9d9f1dbfdc4c8e479e/raw/090f8b935a437e24d65b64d87598fbb437c006da/colombia-municipios.json\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1250,"value":"feature = topojson.feature(places, {\n type: \"GeometryCollection\",\n geometries: places.objects.depts.geometries\n // .filter(function(d) {\n // return (d.id / 10000 | 0) % 100 !== 99;\n // })\n }).features\n.find(f => f.properties.dpt === place)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":106,"value":"// Rescale to fit at the current screen width\nprojection = d3.geoIdentity()\n .reflectY(true)\n .fitExtent([[5, 5], [width - 5, height - 5]], feature)\n\n // .rotate([74 + 30 / 60, -38 - 50 / 60])\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1357,"value":"background = d3.geoPath().projection(projection)(feature)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":400,"value":"function fitnessFunction(path, length){\n let fitness = length;\n if (strategy !== \"longest\") {\n const sinuosity = length / distanceBetween(path[0], path[path.length - 1]);\n\n // divide the length by some power of the sinuosity\n // these choices are arbitrary, play with them!\n fitness /= Math.pow(sinuosity, strategy === \"medium\" ? 2 : 4);\n }\n return fitness;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":964,"value":"function findClosestPolygonIntersection(start, end, polygon) {\n return polygon.reduce((best, point, i) => {\n const intersection = findIntersection(start, end, point, polygon[i + 1] || polygon[0]);\n if (intersection) {\n const distance = distanceBetween(start, intersection);\n if (!best.distance || distance < best.distance) {\n return { intersection, distance };\n }\n }\n return best;\n }, {});\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":130,"value":"function getPointsAlongPolyline(polyline, count) {\n const distances = polyline.map((p, i) =>\n distanceBetween(p, polyline[i + 1] || polyline[0])\n );\n const totalLength = d3.sum(distances);\n const step = totalLength / count;\n let traversed = 0;\n let next = step / 2;\n\n const done = polyline.reduce((arr, point, i) => {\n while (next < traversed + distances[i]) {\n let a = point,\n b = polyline[i + 1] || polyline[0],\n pct = (next - traversed) / distances[i];\n arr.push([a[0] + (b[0] - a[0]) * pct, a[1] + (b[1] - a[1]) * pct]);\n next += step;\n }\n traversed += distances[i];\n return arr;\n }, []);\n return done;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"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","author":"$undefined","summary":"$undefined"},{"id":993,"value":"function rotatePoint(point, angle, center) {\n\n const x2 = (point[0] - center[0]) * Math.cos(angle) - (point[1] - center[1]) * Math.sin(angle),\n y2 = (point[0] - center[0]) * Math.sin(angle) + (point[1] - center[1]) * Math.cos(angle);\n\n return [\n (point[0] - center[0]) * Math.cos(angle) - (point[1] - center[1]) * Math.sin(angle) + center[0],\n (point[0] - center[0]) * Math.sin(angle) + (point[1] - center[1]) * Math.cos(angle) + center[1]\n ];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":987,"value":"function tangentAt(el, len) {\n const a = el.getPointAtLength(Math.max(len - 0.01, 0)),\n b = el.getPointAtLength(len + 0.01);\n\n return Math.atan2(b.y - a.y, b.x - a.x);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":981,"value":"function distanceBetween(a, b) {\n const dx = a[0] - b[0],\n dy = a[1] - b[1];\n\n return Math.sqrt(dx * dx + dy * dy);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":960,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":103,"value":"function simplify(points) {\n // Convert from [x, y] to { x, y } and back for simplify-js\n return simplifyJS(points.map(p => ({ x: p[0], y: p[1] })), simplification).map(p => [p.x, p.y]); \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":99,"value":"simplifyJS = require(\"simplify-js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1400,"value":"topojson = require(\"topojson\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":572,"value":"import {slider, radio} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1152,"value":"styles = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 30:"$2f:body"