Label Cache Performance

[Stephen Woodbridge]

Steve Lime wrote:
> Interesting idea. No, it's not been looked at before, not by me
> anyway. Frank might have some thoughts on performance. You'd still
> have to loop through the affected area to find collisions but I think
> your correct in that the search time would basically be constant
> (affected slightly by the size of the label).
> 
> Wouldn't be that hard to implement. I wonder if GD holding the cache 
> image could be useful or if a custom 2-D bit array would be faster-
> probably the latter...

I thin a 2-D bit array would be much faster and require significantly 
less memory, but would require writing a little additional code. The 
upside to this is that the code could be optimized for this specific 
task, unless there are other potential uses for this.

Another idea I had related to this scheme would be that you could 
implement a function could search for a placement position withing some 
number of pixels. Here the idea would be that you use the polygon to 
create a mask and see if the mask collides, if not you are done, 
otherwise you do a spiral search outwards from the anchor point for some 
number of pixels looking for a place the label will fit. This is easy to 
do in some nested loops and very fast.

This idea of a moving mask is fundamental to a lot of the raster 
manipulation algorithm and is easy to implement and very fast to execute.

-Steve W

> Steve
> 
>>>> Stephen Woodbridge <woodbri at SWOODBRIDGE.COM> 1/2/2007 9:46:46
>>>> AM
>>>> 
> HNY All,
> 
> Last year I spent a fair amount of time optimizing a bunch of
> mapfiles
> 
> for performance. One of the areas that seems to always be a
> performance
> 
> hog if processing the Label Cache. I have been successful are
> thinning
> 
> down the number of labels going into the cache, but I wondering if 
> there might be a more efficient way of dealing with it. Since I have
> been playing with rasters over the holidays I was wondering if it
> might be possible to implement the label cache as a bitmap mask and
> us a raster
> 
> OP to see if there is a collision?
> 
> OK, I'm sure it is possible, I guess my real question(s) are:
> 
> Has this approach been looked at before? Any thoughts on performance?
> 
> 
> My idea is:
> 
> 1) create an label cache image 2) to check a label, get its bbox
> polyon check if it overlaps and set pixels 3) polygon fill the bbox
> of a label into the label cache image when a label is rendered
> 
> we might be able to use a 2:1 or 4:1 reduced size label cache image 
> with some thought about how to work around the issues.
> 
> I would think that this would be much faster than searching a list of
>  drawn labels and checking for intersections. And it should be linear
>  with the number of labels in the cache.
> 
> -Steve