Label Cache Performance

[Stephen Woodbridge]

Frank Warmerdam wrote:
> Stephen Woodbridge wrote:
>> Yes, another good idea. But isn't a bitmap just a very fine grid? ;)
> 
> Steve,
> 
> The distinction is that a bitmap doesn't give the identity of the object
> you find, so you can't easily do "feature" oriented comparisons like
> the mindistance one.

Right I got that, and I think I addressed this issue in follow up email 
which I assume you have not gotten to yet.

Currently because we make one label cache for the whole map, we are 
using it to also process the MINDISTANCE handling. This in fact requires 
you to look at a lot of additional entries because MINDISTANCE is 
localized to a LAYER or CLASS, but the label cache has entries for the 
whole mapfile.

If we split the processing of the collision detection to use a bitmap 
and then use a hash to track the MINDISTANCE processing at the LAYER or 
CLASS level, both of these should speed up significantly.

If there is no MINDISTANCE, then there is no additional processing, if 
you need to process it, it will have significantly less entries, like 
1-3 orders of magnitudes less entries that need to be looked at for any 
given MINDISTANCE label.

Likewise, collision detection is simply comparing a small bitmap 
positioned over a large bitmap by doing a logical AND of the bits and 
you fail on the first AND that return true. There is NO list to search. 
Yes there is some cost to render the label bbox into the small bitmap, 
but that is just a polygon fill.

Steve, This week is mostly gone for me, and I will be traveling all next 
week. I will take a shot at summarizing this discussion into an email 
that you can copy/paste into an RFC. I am happy to defend the RFC as 
much as is needed. I have not had a chance to look at the mapserver 
code, and will probably leave that up to you or whomever will be doing 
the implementation.

-Steve W