[mapserver-dev] Labelcache potential optimization using spatial index

[Lime, Steve D (MNIT)]

I think Steve's on the right track with his thinking.

The problem is that label collision isn't a bbox computation. If you want to tightly pack things you have to use
a polygon to represent a label. So storing the bbox of placed labels would get you candidates to do a more
exhaustive test against. Each bbox in the index (more likely a quadtree if the existing code could be used)
would have to be tied to the chained list record.

I wonder how many labels one would have to be dealing with for this overhead and complexity to be worth it.

Steve 

________________________________________
From: mapserver-dev-bounces at lists.osgeo.org [mapserver-dev-bounces at lists.osgeo.org] on behalf of Stephen Woodbridge [woodbri at swoodbridge.com]
Sent: Thursday, February 21, 2013 9:26 AM
To: mapserver-dev at lists.osgeo.org
Subject: Re: [mapserver-dev] Labelcache potential optimization using spatial index

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
_______________________________________________
mapserver-dev mailing list
mapserver-dev at lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/mapserver-dev