[mapserver-dev] Auto Label Placement Algorithm

[Stephen Woodbridge]

Noel Peterson wrote:
> Thank you both for your quick replies!
> 
> I appreciate the clarification about the AUTO keyword. However, since
> it is separate from collision avoidance, I will need to incorporate
> details about both of those algorithms into my paper. How does the
> collision avoidance work? That is, if a collision is detected, how
> exactly is the decision of where to shift that label to made? Are
> labels ever dropped completely?

Each label has a bounding box about it and possibly and associated image 
or marker. When it is time to place a marker its bounding box is 
compared against the labels that have already been placed. If it 
collides then it is skipped. If a label has multiple placement points 
like the AUTO case then each is checked in turn until one can be placed. 
If none of placement points can be used without a collision, or there is 
only one placement point and it is a collision, then it is totally skipped.

As mentioned before the PRIORITY feature lets you have some control to 
place some labels with a higher priority than others and obviously if 
there are less labels already placed there is less probability of 
collisions.

> Also, if it's not too much trouble, I really would appreciate being
> pointed to any relevant sections of the source code.

Looking quickly at the source, I think most of the code is in maplabel.c

-Steve W

> Thanks again!
> 
> -- Noel
> 
> 
> On Mon, Apr 5, 2010 at 12:33 PM, Lime, Steve D (DNR)
> <Steve.Lime at state.mn.us> wrote:
>> 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
>>