Centerline label placement
Forked from https://gist.github.com/veltman/403f95aee728d4a043b142c52c113f82
Implementing a variation of Joachim Ungar’s curved label placement method described here. The basic process is:
- Turn the shape into a polygon of evenly-spaced points.
- Generate a Voronoi diagram of those points.
- Clip the edges.
- Turn the edges into a graph.
- Find the “longest shortest path” between any pair of perimeter nodes.
- Smooth/simplify that path a bit.
- Place text along the smoothed centerline with a
Some potential optimizations:
- Don’t check every pair of points when pathfinding, you could probably safely skip 90% of the operations with some sort of heuristic.
- 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.
- 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.
- 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.
- 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)