search

MapServer / MapServer-import

3 stars 2 forks source link

Establish a mechanism to prioritize labeling. #1619

Open tbonfort opened 12 years ago

tbonfort commented 12 years ago

Reporter: sdlime Date: 2006/01/19 - 04:59

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
tbonfort commented 12 years ago

Author: dmorissette Date: 2006/01/26 - 04:12

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.
tbonfort commented 12 years ago

Author: sdlime Date: 2006/01/26 - 17:06

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

Steve
tbonfort commented 12 years ago

Author: dmorissette Date: 2006/01/26 - 18:02

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.
tbonfort commented 12 years ago

Author: sdlime Date: 2006/01/26 - 21:36

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
tbonfort commented 12 years ago

Author: dmorissette Date: 2006/01/26 - 23:17

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.
tbonfort commented 12 years ago

Author: dmorissette Date: 2007/05/22 - 21:20 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)

tbonfort commented 12 years ago

Author: dmorissette Date: 2007/07/05 - 17:11 I have committed in 41f04b656feb7d5df4c6553be69893c65ffc2604 (r6261) a first round of changes to support label priority as described in RFC 27.

Here are some implementation details:

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;
tbonfort commented 12 years ago

Author: dmorissette Date: 2007/07/05 - 17:38 Added support for binding label priority to an attibute in e721987aa4d1b8580efa0c53a65b3d4fa99435bb (r6262).

tbonfort commented 12 years ago

Author: dmorissette Date: 2007/07/05 - 23:40 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.

tbonfort commented 12 years ago

Author: dmorissette Date: 2007/09/05 - 17:45 Closing. I have created ticket #2292 for the doc updates.