[Qgis-user] Dropping the extra label placement algorithms?

[Martin Dobias]

Hi Nyall

On Fri, Jul 26, 2019 at 4:40 AM Nyall Dawson <nyall.dawson at gmail.com> wrote:
>
> Hey lists
>
> This was first discussed back in 2016 (see
> http://osgeo-org.1560.x6.nabble.com/Removal-of-labeling-search-methods-td5262743.html),
> but would anyone object if the different labeling solution algorithms
> eg "chain" / "pop music" / "falp" / etc were dropped, and we just
> leave the existing default (chain)?

As stated in the earlier email, I would not mind if we remove those.
Are you thinking about removing the option in GUI or to get rid of the
code in PAL for other methods too?


> I don't think ANYONE knows what these mean, and it's a heck of a lot
> of code (which needs fixes) to cart around for no compelling reason
> that I can see.
>
> I have no particular preference to any of the methods, so would
> happily accept a different default if anyone out there can point to
> which method is best!
>
> Googling pop music / tabu / chain only gives a handful of results
> relating to QGIS labeling engine. And googling for "falp" sounds like
> something that would get you flagged on your company's firewall.

To shed some light on the methods for those interested... a good
starting point is PAL docs [1] with links to papers, unfortunately
most links there are broken, but this paper is a good start:
Laurent et al: From Point Feature Label Placement to Map Labelling (2009)

The paper is available here [2] and gives an overview of the whole
process of labeling with PAL. Generally the idea is to turn labeling
into a general combinatoric problem and then apply some heuristic. The
paper also covers the various optimization techniques. FALP seems to
be the most basic initial solution. "Tabu" seems to be a
meta-heuristic method from 1980's [3], "chain" stands for "ejection
chains" concept somehow related to Tabu search. And finally Popmusic
is a search method co-authored from one of the authors of PAL.

I remember there was a paper with quite extensive testing of the
methods, but can't find it anymore. From what I remember, one would
higher amount of labeled features with a slower method (e.g. Popmusic)
or fewer labels with a faster method. If we decide to stick with a
single method, it may be interesting to get the opinion of original
PAL authors on what method to choose... I don't know enough about
those methods to decide.

Cheers
Martin


[1] http://pal.heig-vd.ch/index.php?page=support
[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.472.4491&rep=rep1&type=pdf
[3] https://en.wikipedia.org/wiki/Tabu_search