[mapserver-dev] Auto Label Placement Algorithm

[Noel Peterson]

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?

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

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
>