[mapserver-dev] Labelcache potential optimization using spatial index

[Stephen Woodbridge]

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.

Does the RTree give us some other option(s) for organizing the label 
cache initially?

-Steve W

On 2/21/2013 9:12 AM, Daniel Morissette wrote:
> On 13-02-21 9:11 AM, Daniel Morissette wrote:
>> Devs,
>>
>> I came across the following article yesterday:
>>
>> http://mapbox.com/osmdev/2013/02/12/labeling-id/
>>
>> All very interesting stuff relating to OSM editing, but the bit that
>> caught my attention as MapServer dev is this paragraph:
>>
>> """
>> Because labels are updated with each redraw of the map, they need to be
>> extremely fast. iD calculates label bounding boxes based on estimated
>> text length, since it’s slow to use browser-calculated bounds. We use
>> RTree to optimize collision detection and proximity searches, a
>> technique inspired by kothic.js.
>> """
>>
>> Using a spatial index to optimize collection detection. Of course!
>>
>
> Err... typo:
>
> "Using a spatial index to optimize _ collision_ detection..."
>
>
>> As you all know, the labelcache processing can sometimes account for a
>> significant part of the rendering time in MapServer, even more than 50%
>> in some maps with lots of labels, and this idea of using a spatial index
>> to manage the collision detection could really help improve that.
>>
>> There would be one drawback though: at the moment the order in which the
>> labels enter the cache defines their rendering priority, and a
>> side-effect of using a spatial index would be to lose that feature.
>> However, one could deal with this issue with proper use of the
>> LABEL.PRIORITY in all their layers.
>>
>> An interesting idea to keep in mind anyway...
>>
>
>