Skip to content

Instantly share code, notes, and snippets.

@veltman
Last active March 13, 2018 06:38
Show Gist options
  • Save veltman/13a7234c4ea073bd7caaa11abb1f7b5d to your computer and use it in GitHub Desktop.
Save veltman/13a7234c4ea073bd7caaa11abb1f7b5d to your computer and use it in GitHub Desktop.
Centerline label placement #2
(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)
});
<!DOCTYPE html>
<meta charset="utf-8">
<link href="https://fonts.googleapis.com/css?family=Spectral" rel="stylesheet">
<style>
text {
font: 32px Spectral;
letter-spacing: 0.1em;
fill: #333;
}
line, path {
stroke-width: 1px;
fill: none;
}
circle {
fill: #f0f;
}
.edge, .clipped {
stroke: #999;
}
.original {
stroke: #333;
}
.longest,
#centerline {
stroke: #f0f;
stroke-width: 3px;
stroke-dasharray: 6,6;
}
</style>
<svg width="960" height="500">
<path class="original" d="M303,325c2,13.9,35.5,28.9,54,16c15.1-10.6,15-36.1,8-52c-14.8-33.8-69-44.9-109-36c-31.4,7-74.6,30.9-80,67
c-9,60.4,95,110.8,112,119c26.9,13,131.9,63.8,219,7c8.8-5.7,67-45,75-116c9.7-86.1-62.7-144.8-76-155c-42.6-32.8-90.5-40.1-111-43
c-73.4-10.4-115.3,15.6-142-12c-12.9-13.4-20.9-37.9-12-53c23.2-39.4,170.8-31.5,266,44c40.6,32.2,55,63.6,98,69
c46.5,5.9,98.1-22.2,98-45c0-18.1-32.4-31.3-97-57c-57.8-23-103.5-34.8-112-37C408.2,19.1,353,5,281,11c-52.7,4.4-104.2,8.7-120,42
c-18.2,38.3,15.8,104.7,65,129c56.8,28,93.8-19.9,166,5c6.8,2.3,79.7,28.8,99,99c10.3,37.4,7.3,94.7-31,125
c-54.4,43.1-135.4-3.3-154-14c-15.4-8.8-66.8-38.2-61-71c3.6-20.2,27.7-35.1,47-39c12.5-2.5,30.5-1.9,33,5
C328.3,301.2,301,311.7,303,325z"/>
</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] })), 8).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("A RATHER CURVED LABEL");
}
// 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