[mapserver-dev] Auto Label Placement Algorithm

[Lime, Steve D (DNR)]

Just got back from vacation, let me know if you need additional detail. Steve hit
the high points. Collisions are detected using minimum bounding polygons for labels
and, if necessary, an associated marker. All the AUTO keyword does is rotate between
possible positions (the list of candidate positions differs depending on feature type)
while the collision avoidance is the same if you use AUTO or a fixed position.

Steve

-----Original Message-----
From: mapserver-dev-bounces at lists.osgeo.org [mailto:mapserver-dev-bounces at lists.osgeo.org] On Behalf Of Stephen Woodbridge
Sent: Sunday, April 04, 2010 9:12 PM
To: Noel Peterson
Cc: mapserver-dev at lists.osgeo.org
Subject: Re: [mapserver-dev] Auto Label Placement Algorithm

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
_______________________________________________
mapserver-dev mailing list
mapserver-dev at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/mapserver-dev