[mapserver-dev] Auto Label Placement Algorithm

[Stephen Woodbridge]

Noel Peterson wrote:
> Hello,
> 
> I am currently in the process of writing a research paper about
> dynamic feature labeling (specifically of point features) in web
> mapping applications, to avoid label collisions, etc.  I have been
> looking at the MapServer source code, trying to figure out what
> algorithm is used to implement the AUTO label placement option, but
> have not had any luck so far. My knowledge of C is quite minimal.
> 
> I would be extremely grateful if someone could take the time to
> explain how the algorithm works or, if nothing else, point me toward
> the appropriate section of the source code so that I can attempt to
> figure it out for myself. Thanks!
> 

Noel,

There are a few pieces to the placement algorithm.

1. the generation of candidate positions where the label might be placed 
at UL, UC, UR
    CL, CC, CR
    LL, LC, LR
candidate positions. These are then placed in the label cache.

2. labels are then pulled from the label cache in a last in first out 
manner and placed on the map if they do not collide with other labels. 
Once an AUTO label is placed based on one of the candidate positions be 
accepted the rest are skipped.

3. We have recently added the ability to set a label PRIORITY, which in 
effect splits the label cache into 10 queues based on PRIORITY 1-10 and 
processes the higher PRIORITY queues before the lower ones. I think by 
default unprioritized labels have a priority of 1 (one).

So you can see from this that the processing is somewhat distributed 
between the adding labels to the label cache in the draw functions and 
then post processing the label cache after all the layers have been drawn.

-Steve W