[mapserver-dev] Labelcache potential optimization using spatial index

[Stephen Woodbridge]

On 2/21/2013 10:04 AM, Daniel Morissette wrote:
> On 13-02-21 9:46 AM, Stephen Woodbridge wrote:
>> Daniel,
>>
>> I think I missing what the potential problem is or how you intent for
>> this to be used.
>>
>> If we use the logic we have today, we add a drawn label bbox to the
>> RTree index, when we want to check for a collision we check the next
>> label again the RTree index. This would be faster than the linear search
>> we do today, right? And this does not care about priority. Priority
>> comes into play when selecting the order of label drawing.
>>
>
> Well, at the moment the cached labels are in a chained list IIRC and
> within a given LABEL.PRORITY level we render them in a last in first out
> (LIFO) order.
>
> If we replace the chained list with a spatial index (Rtree or other)
> then we lose the sequential nature of the chained list and the LIFO
> ordering feature that users have come to rely on goes away.
>
> All that's left in this case to really control label rendering order is
> the LABEL.PRIORITY which is optional and probably not used very often by
> users. What I'm saying is that if we switch to a spatial index then
> users would be required to make better use of LABEL.PRIORITY.
>
>
ok, so what if we took this approach:

1. create 10 chained lists, one for each priority. This takes minimal 
additional memory and preserves the exiting behavior and avoids scanning 
the lists 10 times. We might want to assign all labels without priority 
a priority of 5.

2. create the rtree and only use it when labels are added to the image 
and to detect if the current label will collide with an existing label.

Seems like this works like it does today but gets all the benefits for 
the rtree performance and faster evaluation of the labels and avoids all 
the concerns you have expressed.

I do not see any value in preloading the rtree with the labels, just do 
it like we do today only use the rtree instead of the list of bboxes. 
and it will be much faster.

-Steve W