Centerline label placement #2

README.md

A twistier test of this label placement method.

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)
});

index.html

<!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>

preview.png

thumbnail.png