Repository navigation
Label Placement Algorithm? #3
Description
I'm searching for implementations or descriptions of a label placement algorithm that maximizes text size and finds an optimal location for labels, similar to Figure 10 from the original paper:
Do you know of any resources for this? Thank you.
Activity
leebyron commentedon Jul 24, 2017
A brute force technique was used for these labels, assuming a single line of text a size of the bounding box for text can be known, then a largest box of the same proportion is searched for within the labeled shape by looking at many possible locations and using the largest found, then the text is drawn in those coordinates
curran commentedon Jul 25, 2017
Thanks for your response!
Do you know of any Open Source implementation available? I'm not able to track down the Listening History project code with the labeling, is it available?
There's still a lot to infer from your description. I think you're suggesting an algorithm like this to label a single area (StreamGraph layer):
There are a number of constants involved:
There's also the problem of implementing the rectangle-in-polygon test (which may be simplified by the fact that the bounding lines are monotonic in X and nonintersecting).
Does this match with your description?
There could be an approach using randomness as well, rather than a grid. Another thought is that maybe simulated annealing could work.
I think there's a great opportunity here for introducing a new library. All of the StreamGraph examples with D3 don't have labels, except this one by @veltman, which implements a label position search for a fixed font size.
http://blockbuilder.org/search#text=streamgraph
I'd argue that the lack of an Open Source solution to StreamGraph label placement is the primary factor that's limiting mainstream adoption of the StreamGraph visualization technique.
leebyron commentedon Jul 25, 2017
As far as I'm aware, there's no open source implementation of this labeling strategy.
Your algorithm sounds like it will work, though I can think of a couple ways to speed it up:
First, the aspect ratio of a label will be the same regardless of font size, so rather than stepping through font sizes, just find the largest rectangle of the aspect ratio that fits and derive the font size from there. That also allows for setting some padding against the edges of the shape, or centering a label if you want a maximum label size.
Second, rather than using a grid of starting points, just use points along the top edge of the shape, assuming a largest fitting rectangle would always have corners that touch the edges of the containing shape.
Those should reduce the search from N^3 points to N points
curran commentedon Jul 25, 2017
Cheers! Fantastic ideas. Thank you so much for your suggestions.
I dug a little deeper and here's what I've found in terms of prior art:
Will report back here if I get anything working.
curran commentedon Aug 3, 2017
Greetings,
I've implemented a label placement algorithm and released it as a library.
https://github.com/curran/d3-area-label
It uses the Bisection Method and Linear Interpolation to search for the maximum label scale.
Here are some results using it:
It might be cool to add a link to this page http://leebyron.com/streamgraph/
leebyron commentedon Aug 3, 2017
Nice work! If you add a small pull request to do so I'd be happy to take a look https://github.com/leebyron/streamgraph/tree/gh-pages
curran commentedon Aug 4, 2017
@leebyron Thanks for welcoming the addition! I've submitted two PRs: