Centerline label placement #2

A twistier test of this label placement method.

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

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

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>

https://d3js.org/d3.v4.min.js

https://unpkg.com/simplify-js@1.2.3/simplify.js