Opened 18 years ago

Closed 17 years ago

#1619 closed enhancement (fixed)

Establish a mechanism to prioritize labeling.

Reported by: sdlime Owned by: dmorissette
Priority: high Milestone: 5.0 release
Component: MapServer C Library Version: 4.8
Severity: minor Keywords:
Cc:

Description (last modified by dmorissette)

At the moment labeling uses a last in first out (LIFO) mechanism to plot labels
on a map. The results in excessive use of ANNOTATION layers to make certain
labels more prominent. It would be desireable to be able to prioritize LABEL
objects for layers in place. One idea might be to create a new layer or class
parameter called LABELPRIORITY with values from 1 (lowest) to 10 (highest). LIFO
would still be used to prioritize labels within a priority class but all the
class 10s would be drawn first, 9's next and so on. Default priority would be
something like a 5. 

I think this could be done by maintaining 10 cache lists in the label cache.
This would add one extra loop to the label cache processors (there are a bunch
of them, a most one for each output driver). The increased overhead would be
offset by not having to process layers multiple times. Cache counters would make
skipping empty priority classes very simple.

Collision avoidance would be the same as always.

Dan mentioned he has some ideas in this area as well so I've added him to the CC
list...

Steve

Change History (10)

comment:1 by dmorissette, 18 years ago

Actually, the LABELPRIORITY was exactly the idea that I had in mind too, except
that I would have accepted any arbitrary number as the priority level instead of
limiting to 10 values. Thinking about it now, limiting to 10 levels of priority
would simplify the implementation and should be enough for most uses.

We should probably run that 10 levels limit by some power users to see what they
think of it.

comment:2 by sdlime, 18 years ago

Any idea who those power users might be: Bart, Tom K., Steve W., 
somebody at DMSG?

Steve

comment:3 by dmorissette, 18 years ago

Probably more Steve W and Jeff. Bart and Tom are more into the OGC stuff that
into the fancy map styling. The best might be to email the -dev list, power
users interested in this stuff would be listening there.

comment:4 by sdlime, 18 years ago

With regards to an arbitrary priority number. Were you thinking of doing
something like a bubble sort on the cache based on that number and then
processing the cache as normal? There might be some benefit there depending on
how fast a cache can be sorted. Just wondering...

Steve

comment:5 by dmorissette, 18 years ago

No, sorting would be a waste of processing time. I was thinking of maintaining
multiple cache lists, the same way that you suggest, except that instead of
using an array of 10 cache lists (which is probably what you had in mind), I
would have used another mechanism such as a hash table or a chained list to
maintain the list of cache lists (I had not really fully thought about that).

After reading your proposal above I realized that limiting to 10 (or say 20?)
levels would be sufficient for most uses and much more efficient since finding
the right cache list to insert a label would just be a matter of accessing the
array index... instead of searching a chained list or a hash table, or whatever.

So I'm with you on the fixed number of levels. Perhaps let's make it a
configurable parameter in map.h, with a default of 10, and if users find that
they need more, they can always increase the value to 20, or even 50 and
recompile, and the cost of increasing the value would not be that big.

comment:6 by dmorissette, 17 years ago

Description: modified (diff)
Milestone: 5.0 release
Owner: changed from sdlime to dmorissette

Taking this ticket. Preparing RFC 27 for this: http://mapserver.gis.umn.edu/development/rfc/ms-rfc-27

(Note that the RFC proposes the addition of a PRIORITY parameter inside the LABEL object instead of LABELPRIORITY inside LAYER/CLASSES as was initially discussed in this bug)

comment:7 by dmorissette, 17 years ago

Status: newassigned

I have committed in r6261 a first round of changes to support label priority as described in RFC 27.

Here are some implementation details:

  • The current version in SVN supports priority properly only for GD output. The other output drivers work fine for a single priority level and still need to be updated to do the right thing for multiple priority levels. However because of the scary amount of copy/pasted code in all output drivers, I am going to update them in a separate commit and will at the same time extract some of the label collision logic into functions shared by all output drivers.
  • Here are the new labelCacheObj and labelCacheSlotObj definitions:
    typedef struct {
      labelCacheMemberObj *labels;
      int numlabels;
      int cachesize;
      markerCacheMemberObj *markers;
      int nummarkers;
      int markercachesize;
    } labelCacheSlotObj;
    
    typedef struct {
        /* One labelCacheSlotObj for each priority level */
        labelCacheSlotObj slots[MS_MAX_LABEL_PRIORITY];
        /* numlabels is deprecated, maintained only for backwards compatibility
         * between MS 4.10 and 5.0 and should be removed in a future release.
         * The slots[].numlabels are the real values to rely on.
         */
        int numlabels;
    } labelCacheObj;
    
  • The logic from mapObj.getLabel(int i) (mapscript/swiginc/map.i) has been moved to a msGetLabelCacheMember() function in maplabel.c
  • labelCacheObj.numlabels is deprecated, maintained only for backwards compatibility of SWIG MapScript between MS 4.10 and 5.0 and should be removed in a future release. The slots[].numlabels are the real values to rely on.

comment:8 by dmorissette, 17 years ago

Added support for binding label priority to an attibute in r6262.

comment:9 by dmorissette, 17 years ago

All output driver implementations of msDrawLabelCacheXX() have been updated to fully support the label priority logic by using the new msTestLabelCacheCollisions(), saving lots of copy/paste'd code by the same way (but there is still room for improvement on that front).

The last thing left to do will be to update docs with the new PRIORITY parameter. We'll keep this ticket open until that's done.

comment:10 by dmorissette, 17 years ago

Resolution: fixed
Status: assignedclosed

Closing. I have created ticket #2292 for the doc updates.

Note: See TracTickets for help on using tickets.