Skip to content

Instantly share code, notes, and snippets.

@veltman

veltman/README.md

Last active December 18, 2020 08:51
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 4 You must be signed in to fork a gist
  • Save veltman/403f95aee728d4a043b142c52c113f82 to your computer and use it in GitHub Desktop.
Save veltman/403f95aee728d4a043b142c52c113f82 to your computer and use it in GitHub Desktop.
Download ZIP
Centerline label placement
Raw
README.md

Implementing a variation of Joachim Ungar's curved label placement method described here. The basic process is:

  1. Turn the shape into a polygon of evenly-spaced points.
  2. Generate a Voronoi diagram of those points.
  3. Clip the edges.
  4. Turn the edges into a graph.
  5. Find the "longest shortest path" between any pair of perimeter nodes.
  6. Smooth/simplify that path a bit.
  7. Place text along the smoothed centerline with a <textPath>.

Some potential optimizations:

  1. Don't check every pair of points when pathfinding, you could probably safely skip 90% of the operations with some sort of heuristic.
  2. Keep track of shared nodes during the Voronoi creation process, instead of looping through them all afterwards to find which ones are reused in multiple edges.
  3. Instead of just taking the longest path, choose the best path with some fitness function that factors in how long, how straight, and how horizontal it is.
  4. For a more complex starting shape, pre-simplify it and/or use a concave hull, to avoid getting weird results because of little nooks and crannies.
  5. Auto-detect the usable font-size based on distance from the centerline to the shape border.

This uses simplify.js for the line simplification, node-dijkstra for Dijkstra's algorithm, and a line/line intersection function from turf-line-slice-at-intersection.

A twistier version

See also: [Automatic label placement along path] (https://bl.ocks.org/veltman/6204863ae290904fbae83ca5490d4b1b)

Raw
dijkstra.js
(function(f){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=f()}else if(typeof define==="function"&&define.amd){define([],f)}else{var g;if(typeof window!=="undefined"){g=window}else if(typeof global!=="undefined"){g=global}else if(typeof self!=="undefined"){g=self}else{g=this}g.Graph = f()}})(function(){var define,module,exports;return (function(){function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}return e})()({1:[function(require,module,exports){
const Queue = require('./PriorityQueue');
const removeDeepFromMap = require('./removeDeepFromMap');
const toDeepMap = require('./toDeepMap');
const validateDeep = require('./validateDeep');
/** Creates and manages a graph */
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);
}
}
module.exports = Graph;
},{"./PriorityQueue":2,"./removeDeepFromMap":3,"./toDeepMap":4,"./validateDeep":5}],2:[function(require,module,exports){
/**
* This very basic implementation of a priority queue is used to select the
* next node of the graph to walk to.
*
* The queue is always sorted to have the least expensive node on top.
* Some helper methods are also implemented.
*
* You should **never** modify the queue directly, but only using the methods
* provided by the class.
*/
class PriorityQueue {
/**
* 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);
}
}
module.exports = PriorityQueue;
},{}],3:[function(require,module,exports){
/**
* Removes a key and all of its references from a map.
* This function has no side-effects as it returns
* a brand new map.
*
* @param {Map} map - Map to remove the key from
* @param {string} key - Key to remove from the map
* @return {Map} New map without the passed key
*/
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;
}
module.exports = removeDeepFromMap;
},{}],4:[function(require,module,exports){
/**
* Validates a cost for a node
*
* @private
* @param {number} val - Cost to validate
* @return {bool}
*/
function isValidNode(val) {
const cost = Number(val);
if (isNaN(cost) || cost <= 0) {
return false;
}
return true;
}
/**
* Creates a deep `Map` from the passed object.
*
* @param {Object} source - Object to populate the map with
* @return {Map} New map with the passed object data
*/
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;
}
module.exports = toDeepMap;
},{}],5:[function(require,module,exports){
/**
* Validate a map to ensure all it's values are either a number or a map
*
* @param {Map} map - Map to valiadte
*/
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}`);
}
});
}
module.exports = validateDeep;
},{}]},{},[1])(1)
});
Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<link href="https://fonts.googleapis.com/css?family=Spectral" rel="stylesheet">
<style>
text {
font: 64px Spectral;
letter-spacing: 0.08em;
fill: #444;
}
line, path {
stroke-width: 1px;
fill: none;
}
circle {
fill: #f0f;
}
.edge, .clipped {
stroke: #999;
}
.original {
stroke: #444;
fill: #f9f9f9;
}
.longest,
#centerline {
stroke: #f0f;
stroke-width: 3px;
stroke-dasharray: 6,6;
}
</style>
<svg width="960" height="500">
<path class="original" d="M290.417,20L298.097,20.387L310.968,20.667L320.606,20.971L327.647,20.697L331.188,21.04L342.434,21.185L354.406,21.061L369.682,21.376L390.428,21.587L396.579,21.453L401.791,21.538L425.94,20.948L437.336,20.428L438.24,43.697L439.155,67.325L440.1,87.711L440.478,96.99L441.145,115.841L441.751,133.843L442.18,149.952L442.911,163.167L457.624,175.097L478.697,191.949L494.201,204.255L508.215,215.383L528.879,231.482L535.777,236.956L550.176,248.075L566.204,260.333L577.086,268.669L599.148,285.357L614.024,296.529L626.359,305.705L644.079,318.79L656.377,327.824L673.333,340.205L674.602,347.117L676.256,348.019L678.466,351.504L682.238,353.699L683.989,356.975L684.662,359.466L687.445,362.342L687.772,366.003L689.783,366.021L693.388,368.089L695.201,369.583L697.387,370.091L699.376,372.157L699.868,374.429L698.706,374.94L695.59,379.484L694.25,379.861L692.938,381.834L689.339,383.916L688.733,385.064L689.077,388.378L685.808,393.957L687.556,396.782L686.609,397.851L688.195,401.784L688.24,403.536L689.209,405.334L688.131,406.077L688.034,408.048L688.803,409.872L688.172,411.009L689.174,412.859L687.896,414.129L685.728,418.444L685.664,419.943L681.957,421.57L683.327,425.078L682.299,427.048L684.875,428.35L685.62,433.898L684.9,437.427L686.966,440.241L689.296,440.451L690.978,439.761L694.224,440.202L695.978,444.205L696.985,445.542L697.234,448.819L694.953,452.029L695.437,453.756L691.795,455.835L688.517,455.827L687.365,457.03L664.506,462.312L640.712,467.682L610.501,474.27L583.255,480L582.314,475.793L581.589,474.256L580.74,473.12L579.704,472.529L578.131,472.58L577.969,471.938L578.779,471.004L580.512,471.599L580.761,472.365L582.485,474.973L582.929,476.205L583.814,475.392L582.87,473.793L582.813,472.851L582.088,471.911L580.019,470.794L580.076,470.172L578.54,470.403L577.406,471.466L576.573,471.838L576.412,468.602L576.144,467.538L574.73,464.869L575.684,463.913L575.796,462.272L574.319,456.728L573.673,455.198L573.088,454.624L571.673,450.959L569.658,448.147L562.463,439.984L558.421,437.475L555.673,435.039L551.99,433.138L550.008,430.991L547.795,429.502L545.262,428.097L543.048,427.503L540.852,426.229L535.642,421.724L532.868,420.505L531.462,420.682L531.252,422.036L530.486,421.548L529.866,420.113L528.473,420.506L527.56,421.959L527.915,423.149L526.707,423.524L524.328,422.853L523.971,422.391L521.814,422.241L521.026,420.638L522.269,418.891L522.338,417.317L519.63,411.645L517.823,409.213L515.06,407.352L513.921,407.318L512.295,407.714L509.458,407.783L509.295,408.197L506.382,408.314L504.925,408.93L503.996,410.15L501.936,408.516L498.316,408.255L496.53,407.523L495.207,407.266L493.867,406.445L492.897,406.406L491.625,405.712L490.443,405.476L489.967,405.807L487.076,403.852L486.071,403.716L484.03,400.143L483.534,398.223L482.604,397.266L481.996,397.413L480.496,396.564L479.048,395.141L478.178,395.252L476.454,393.543L475.437,392.829L474.379,392.67L473.627,392.122L471.822,391.619L470.659,390.691L470.129,390.865L468.364,390.511L465.407,391.147L464.591,391.98L463.526,391.926L461.167,391.021L459.294,391.154L457.346,391.735L455.473,390.441L453.966,390.377L451.679,389.183L450.55,389.12L448.243,389.434L446.442,388.79L444.824,388.992L439.703,389.254L434.157,390.322L432.949,390.797L432.152,390.44L430.464,386.846L428.416,385.894L427.55,385.285L425.71,385.386L425.062,384.878L424.557,383.725L426.18,378.886L426.269,377.583L424.631,374.882L425.425,371.761L425.521,369.779L424.459,368.726L424.254,367.921L423.057,367.321L424.198,362.533L424.511,360.781L424.579,358.806L423.898,355.493L422.461,354.837L421.297,353.793L419.495,353.678L418.859,354.566L417.784,353.639L415.309,352.485L414.169,351.451L413.27,350.152L413.328,348.946L414.411,346.036L415.91,345.712L415.019,344.163L414.408,343.977L414.188,342.243L413.487,340.86L412.609,340.104L411.044,340.238L410.321,339.728L408.59,339.562L404.532,335.136L403.291,332.579L402.777,332.368L401.677,330.777L400.629,331.026L399.735,330.262L397.563,329.464L395.664,326.992L395.281,324.433L394.687,323.333L392.625,321.601L391.034,319.756L389.481,318.348L388.339,313.554L387.649,312.504L385.198,311.68L384.132,310.158L384.051,309.473L383.08,308.466L382.585,307.032L380.632,304.555L378.547,302.789L375.718,300.98L375.253,301.086L374.23,300.249L373.829,299.086L372.688,298.206L371.796,297.011L371.445,293.477L370.992,291.544L369.741,288.111L369.903,287.111L370.493,286.514L370.207,284.647L369.434,284.731L368.466,283.973L369.574,282.217L370.078,280.754L371.503,281.674L372.095,282.609L372.792,282.347L374.072,280.926L375.011,278.548L375.439,275.196L375.962,272.418L375.381,270.936L373.15,266.395L371.331,264.33L370.075,263.875L368.607,265.025L366.742,264.654L366.584,265.235L365.167,265.341L363.375,264.993L361.487,263.929L359.342,261.825L357.533,259.839L356.465,257.974L355.39,256.971L354.167,256.869L354.23,256.06L353.379,255.281L352.999,254.112L351.946,253.715L351.621,253.085L351.096,250.218L351.427,249.403L351.85,244.909L351.415,244.154L350.151,241.05L349.983,239.115L349.44,238.123L347.961,237.878L347.217,236.385L347.456,234.933L347.303,233.51L347.927,232.937L348.224,231.663L348.29,229.798L347.598,225.505L347.552,224.084L349.578,222.915L351.313,222.643L352.503,223.645L352.69,224.982L353.78,226.654L353.466,227.395L352.296,227.612L352.458,229.246L352.959,230.335L352.606,231.5L353.386,231.713L352.972,232.847L353.576,233.413L354.674,233.588L355.894,234.213L357.501,234.487L358.213,235.706L359.786,236.301L360.416,237.656L362.33,238.144L363.657,240.257L364.413,240.572L366.069,240.442L365.537,239.454L365.142,237.957L363.929,237.863L363.316,237.151L363.025,235.936L361.866,234.137L361.236,229.923L360.108,228.151L359.231,228.209L357.78,227.035L357.373,226.037L357.896,225.779L359.315,226.022L359.13,225.283L358.272,225.435L356.555,225.032L354.694,224.083L354.821,222.998L356.108,221.686L355.793,220.13L354.842,217.905L353.442,218.112L351.696,216.71L350.953,215.115L352.187,215.526L352.297,214.832L353.676,213.989L353.424,212.776L354.592,213.202L356.024,212.849L356.881,212.179L356.939,211.485L357.94,210.693L358.818,210.547L360.394,211.066L361.071,212.046L361.867,212.265L364.424,211.081L367.43,210.679L369.94,211.246L371.911,211.412L373.879,212.291L376.122,212.655L377.205,212.455L378.294,212.857L379.567,212.948L379.897,212.537L378.985,211.671L379.731,211.2L380.274,209.277L382.071,208.999L382.755,208.501L383.708,208.853L383.608,210.289L382.232,210.344L381.789,211.211L382.849,212.494L383.65,211.957L383.874,210.304L384.211,210.131L387.668,212.217L387.416,211.136L385.01,210.205L384.122,208.598L381.962,208.2L381.298,208.847L379.919,208.847L379.581,210.374L379.196,210.903L377.551,211.962L376.569,211.921L375.881,211.286L376.084,210.404L377.756,209.539L377.347,209.106L375.187,210.333L373.524,209.867L372.12,210.636L370.8,210.845L371.123,209.563L368.693,209.758L367.008,208.602L368.125,208.004L367.573,206.7L365.458,206.874L364.926,207.459L364.673,208.502L362.909,210.49L362.551,211.359L361.463,211.292L360.469,210.242L358.953,210.19L357.107,209.75L355.989,208.092L352.311,205.86L351.76,206.805L348.786,208.2L348.963,209.572L348.024,212.491L350.018,213.461L348.524,214.821L348.982,216.199L348.08,217.026L349.129,217.469L349.2,217.998L350.565,219.149L349.367,219.879L349.123,218.904L348.235,218.561L348.215,219.598L349.032,220.236L349.317,221.607L349.035,221.936L347.055,222.345L345.319,220.382L344.258,219.518L343.507,219.299L342.571,218.239L341.522,217.844L340.576,218.191L339.375,217.988L338.586,216.524L337.374,215.743L336.786,214.389L335.82,213.286L332.548,211.552L331.999,211.393L330.358,211.831L329.007,213.349L328.3,212.999L329.324,210.663L330.999,206.025L330.993,205.02L330.446,204.123L330.467,203.34L329.403,201.805L329.718,201.406L331.955,204.517L333.227,206.712L334.086,207.734L334.793,207.725L333.367,205.548L331.608,202.535L330.349,201.453L330.157,200.025L329.12,198.603L328.092,197.71L327.442,197.728L326.812,198.504L326.321,197.194L326.637,196.036L325.97,193.824L325.018,192.369L324.438,190.955L322.86,189.46L319.777,187.85L319.041,186.939L316.634,185.008L316.481,184.059L314.294,181.261L313.837,180.086L313.12,179.086L310.957,176.605L309.802,176.071L309.296,174.809L308.248,173.667L307.206,173.115L305.227,170.926L304.706,169.795L302.938,167.701L301.84,165.657L302.502,165.45L303.355,164.038L303.976,162.223L303.799,160.703L302.925,157.091L302.336,156.587L302.447,155.814L301.295,154.081L300.575,150.39L300.115,149.928L300.364,149.031L300.091,147.742L299.425,146.598L299.907,141.944L300.653,139.726L301.818,137.156L301.863,136.237L301.274,134.623L301.387,131.812L301.098,130.036L300.666,129.061L300.113,128.754L299.682,126.629L299.729,125.604L299.201,123.153L298.256,122.601L297.28,121.527L296.511,119.472L295.627,118.646L294.839,116.773L294.049,116.012L292.932,114.334L291.255,113.142L291.081,111.122L290.102,109.662L287.604,108.481L286.411,106.723L285.121,105.744L282.91,103.719L281.383,101.883L282.065,99.168L281.522,97.91L281.544,96.345L280.471,94.46L280.132,93.107L280.661,92.103L281.127,90.018L282.577,86.829L283.671,84.991L284.111,83.637L285.588,81.14L286.941,78.407L287.241,78.831L286.604,79.858L286.102,81.241L286.994,81.59L287.754,81.171L287.59,79.458L288.238,79.108L288.835,76.974L289.343,76.378L291.279,76.278L292.552,75.486L292.703,74.388L292.1,73.885L291.471,74.167L290.828,73.57L290.199,73.649L289.574,75.285L288.691,76.407L288.434,77.229L287.529,78.51L287.206,78.042L289.395,74.279L291.109,70.14L292.1,66.438L292.116,65.185L290.887,64.256L290.475,62.38L290.474,60.497L291.178,60.247L291.935,58.534L293.33,53.497L293.742,51.039L294.631,46.628L294.094,42.565L294.61,41.747L293.438,40.411L293.52,38.714L292.335,35.757L292.414,35.032L291.791,32.325L290.814,31.798L290.336,32.139L289.288,31.008L288.247,30.3L289.336,28.617L289.94,26.912L290.745,21.759L290.417,20Z"/>
</svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://unpkg.com/simplify-js@1.2.3/simplify.js"></script>
<script src="dijkstra.js"></script>
<script>
const svg = d3.select("svg").append("g");
// Chaining to illustrate the steps
Promise.resolve(drawPerimeter(document.querySelector("path")))
.then(drawVoronoi)
.then(clipVoronoi)
.then(findCenterline)
.then(simplifyCenterline)
.then(addLabel)
.then(animate);
// Turn an arbitrary path into a polygon of evenly-spaced points
function drawPerimeter(path) {
// More points = more precision + more compute time
const numPoints = 90;
const length = path.getTotalLength();
const polygon = d3
.range(numPoints)
.map(i => path.getPointAtLength(length * i / numPoints))
.map(d => [d.x, d.y]);
const dots = svg
.selectAll("circle")
.data(polygon)
.enter()
.append("circle")
.call(drawCircle);
return polygon;
}
// Get the voronoi edges for the perimeter points
function drawVoronoi(polygon) {
const [x0, x1] = d3.extent(polygon.map(d => d[0])),
[y0, y1] = d3.extent(polygon.map(d => d[1]));
const voronoi = d3.voronoi().extent([[x0 - 1, y0 - 1], [x1 + 1, y1 + 1]])(polygon);
const edges = voronoi.edges.filter(edge => {
if (edge && edge.right) {
const inside = edge.map(point => d3.polygonContains(polygon, point));
if (inside[0] === inside[1]) {
return inside[0];
}
if (inside[1]) {
edge.reverse();
}
return true;
}
return false;
});
svg
.selectAll(".edge")
.data(edges)
.enter()
.append("line")
.attr("class", "edge")
.call(drawLineSegment);
return { polygon, edges };
}
// Clip the Voronoi edges to the polygon
function clipVoronoi({ polygon, edges }) {
edges.forEach(edge => {
const [start, end] = edge;
const { intersection, distance } = polygon.reduce((best, point, i) => {
const intersection = findIntersection(start, end, point, polygon[i + 1] || polygon[0]);
if (intersection) {
const distance = distanceBetween(start, intersection);
if (!best.distance || distance < best.distance) {
return { intersection, distance };
}
}
return best;
}, {});
if (intersection) {
edge[1] = intersection;
edge.distance = distance;
edge[1].clipped = true;
} else {
edge.distance = distanceBetween(start, end);
}
});
svg
.selectAll(".clipped")
.data(edges)
.enter()
.append("line")
.attr("class", "clipped")
.call(drawLineSegment);
return edges;
}
// Construct a graph of the clipped edges
// For each pair of points, use Dijkstra's algorithm to find the shortest path
// We want the "longest shortest path" as the centerline
function findCenterline(edges) {
const nodes = [];
// Create links between Voronoi nodes in the least efficient way possible
edges.forEach(edge => {
edge.forEach((node, i) => {
if (!i || !node.clipped) {
const match = nodes.find(d => d === node);
if (match) {
return (node.id = match.id);
}
}
node.id = nodes.length.toString();
node.links = {};
nodes.push(node);
});
edge[0].links[edge[1].id] = edge.distance;
edge[1].links[edge[0].id] = edge.distance;
});
const graph = new Graph();
nodes.forEach(node => {
graph.addNode(node.id, node.links);
});
const perimeterNodes = nodes.filter(d => d.clipped);
const longestShortest = perimeterNodes
.reduce((totalBest, start, i) => {
// Check all nodes above index i to avoid doubling up
const path = perimeterNodes.slice(i + 1).reduce((nodeBest, node) => {
const path = graph.path(node.id, start.id, { cost: true });
if (!nodeBest.cost || path.cost > nodeBest.cost) {
return path;
}
return nodeBest;
}, {});
if (!totalBest.cost || path.cost > totalBest.cost) {
return path;
}
return totalBest;
}, {})
.path.map(id => nodes[+id]);
svg
.append("path")
.attr("class", "longest")
.attr("d", d3.line()(longestShortest));
return longestShortest;
}
// Simplify the centerline and smooth it with a basis spline
// Check a few tangents near the middle to guess orientation
// If the line is going generally right-to-left, flip it
function simplifyCenterline(centerline) {
centerline = simplify(centerline.map(d => ({ x: d[0], y: d[1] })), 12).map(d => [d.x, d.y]);
const smoothLine = d3.line().curve(d3.curveBasis);
svg
.append("path")
.attr("id", "centerline")
.attr("d", smoothLine(centerline))
.each(function(d) {
// Try to pick the right text orientation based on whether
// the middle of the centerline is rtl or ltr
const len = this.getTotalLength(),
tangents = [
tangentAt(this, len / 2),
tangentAt(this, len / 2 - 50),
tangentAt(this, len + 50)
];
if (tangents.filter(t => Math.abs(t) > 90).length > tangents.length / 2) {
centerline.reverse();
}
})
.attr("d", smoothLine(centerline));
}
// Draw a label at the middle of the smoothed centerline
function addLabel() {
svg
.append("text")
.attr("dy", "0.35em")
.append("textPath")
.attr("xlink:href", "#centerline")
.attr("startOffset", "50%")
.attr("text-anchor", "middle")
.text("CALIFORNIA");
}
// Cycling through the layers for illustration purposes
function animate() {
const steps = [
null,
"circle",
"circle, .edge",
".clipped",
".clipped, .longest",
".longest",
"#centerline",
"#centerline, text",
"text"
];
advance();
function advance() {
svg.selectAll("path, circle, line, text").style("display", "none");
if (steps[0]) {
svg.selectAll(steps[0]).style("display", "block");
}
steps.push(steps.shift());
setTimeout(advance, steps[0] ? 750 : 2000);
}
}
function drawCircle(sel) {
sel
.attr("cx", d => d[0])
.attr("cy", d => d[1])
.attr("r", 2.5);
}
function drawLineSegment(sel) {
sel
.attr("x1", d => d[0][0])
.attr("x2", d => d[1][0])
.attr("y1", d => d[0][1])
.attr("y2", d => d[1][1]);
}
// From https://github.com/Turfjs/turf-line-slice-at-intersection
function findIntersection(a1, a2, b1, b2) {
const uaT = (b2[0] - b1[0]) * (a1[1] - b1[1]) - (b2[1] - b1[1]) * (a1[0] - b1[0]),
ubT = (a2[0] - a1[0]) * (a1[1] - b1[1]) - (a2[1] - a1[1]) * (a1[0] - b1[0]),
uB = (b2[1] - b1[1]) * (a2[0] - a1[0]) - (b2[0] - b1[0]) * (a2[1] - a1[1]);
if (uB !== 0) {
const ua = uaT / uB,
ub = ubT / uB;
if (ua > 0 && ua < 1 && ub > 0 && ub < 1) {
return [a1[0] + ua * (a2[0] - a1[0]), a1[1] + ua * (a2[1] - a1[1])];
}
}
}
function tangentAt(el, len) {
const a = el.getPointAtLength(Math.max(len - 0.01, 0)),
b = el.getPointAtLength(len + 0.01);
return Math.atan2(b.y - a.y, b.x - a.x) * 180 / Math.PI;
}
function distanceBetween(a, b) {
const dx = a[0] - b[0],
dy = a[1] - b[1];
return Math.sqrt(dx * dx + dy * dy);
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment