Label Cache Performance

[Stephen Woodbridge]

Frank Warmerdam wrote:
> Steve Lime wrote:
>> I did think of one other gotcha. The cache is not just used for physical
>> overlap, there
>> are other tests applied. For example, MINDISTANCE, which filters out
>> like labels based
>> on proximity. That requires direct comparison of the bounding polygons.
>> One might be
>> able to reduce that to a test on label points (in fact that might be
>> what's there now,
>> I'd have to check) but that still requires traversing placed labels
>> (albeit only those
>> within a particular layer)...
> 
> Steve(s),
> 
> Another approach that would address requirement is a spatial index
> (ie. quadtree, or just a grid) which would make it easy to find all the
> labels within a certain distance.
> 
> Best regards,

Yes, another good idea. But isn't a bitmap just a very fine grid? ;)

Well if someone is up to playing with these ideas, it would be 
interesting to compare the bitmap approach to the quadtree. My feeling 
is that the bitmap will be faster for collision detection, but that 
dealing with the MINDISTANCE issue will require maintaining another list 
and searching that and using a grid or quadtree might help with that 
part. At least then the search cost is only for when you are using that 
specific feature (like: MINDISTANCE) and the list only needs to be 
maintained through the life of the layer not the whole mapfile. This 
also means that the size of the search list will be smaller so searching 
will improve overall.

-Steve