Label Cache Performance

[Steve Lime]

Remember also that you're not dealing strictly with bounding boxes (e.g.
rects) but
actual polygons whenever rotation is applied. This is so you get
relatively tight fits
around labels and can cram labels on a map.

>>> Stephen Woodbridge <woodbri at swoodbridge.com> 1/2/2007 10:25:49 AM
>>>
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