One of the things holding me back most in making interactive diagrams is labeling points, curves, line segments, filled shapes, etc. (with labels consisting of either words or phrases, letters/symbols in the font used for mathematics in the text, mathematical expressions, etc. depending on context).
I’m probably perfectionistically overthinking it and should just try to get the simplest possible thing working and not worry whether it looks right in every possible configuration as a reader drags stuff around. But it would be great to use some kind of automatic label placement tool.
I’ve tried looking at the research literature about label placement a few times in the past, but it’s quite extensive and a bit intimidating. I haven’t seen any clear overview anywhere of what the trade-offs are involved with different techniques (e.g. speed, quality, flexibility, …).
Does anyone have any recommendation of places to look? Favorite techniques? Existing Javascript implementations? …
I’ve noticed that like myself e.g. @mbostock often makes interactive or animated diagrams of geometric algorithms without labels – is that a stylistic preference or is it just the most convenient choice when there’s no drop-in label library?
Maybe folks who have worked on cartography have some ideas?
If there aren’t good existing Javascript solutions I will probably spend at least a bit of effort on this at some point in the next year, as I need labeled diagrams for many of my projects and ideas. Maybe I’ll just resort to punting on doing anything fancy and just let the labels overlap if users drag labeled elements to an inconvenient configuration, we’ll see.
It’s a hard problem in general, but there are a few heuristic approaches that sometimes work well in practice. One is using a force layout for decollision with a bounding box constraint, such as the one implemented here. Another approach is to label some of the points using a Voronoi diagram like in the notebook in the reply above.
My coworker used a greedy approach implemented here for placing labels on a contour plot. I was stuck on how to do it “right”, but he just picked a cost function out of the sky and then did a bit of bisection searching to place labels one after another. It’s not sophisticated but allowed balancing a number of things (proximity to edges, rotation from horizontal, proximity to other labels).
The main downside is preventing things from jumping around discontinuously when things are dragged, though if the function actually has a minimum and bisection finds it, maybe this would be manageable. Nevertheless, it seemed like a good example to me of a fairly ugly solution that worked perfectly well in practice.
edit: oh, also, this was a 1d problem since the labels were along the contours. that’s not so simple in 2d, though maybe a black box 2d minimizer and an arbitrary cost function could still work. the other thing we had going for us is that we didn’t have to place many labels so that the minimization didn’t have to be blazing fast.
I don’t care too much about having things jump around occasionally, as long as they don’t glitch out and jump back and forth repeatedly.
At least some kind of real-time result (in response to dragged points) would be good, but if an algorithm starts with an instant guess based on the previous state and takes a little while to converge to its final optimized set of positions after elements are dragged around that’s okay with me.