Centerline label placement

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)