Label Cache Performance

[Frank Warmerdam]

Stephen Woodbridge wrote:
> 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...

Folks,

I do believe that some variation on the bitmap for collision testing
would resolve the current n-squared performance of the collision testing.
(ie. doubling the number of labels quadruples the time).

Stephen Woodbridge wrote:
> 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.

It can be relatively expensive to pull individual bits out of a bit
array.  I would be tempted to use a byte array with one byte per pixel.
Even though it wastes memory, it makes indexing and access significantly
easier.  Also we might be able to use something fast like memcmp() to
compare each "scanline" of the mask to zeroed empty mask.

> 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.

I'm not really clear on how this would be done efficiently, but it might
be an interesting experiment.

Best regards,
-- 
---------------------------------------+--------------------------------------
I set the clouds in motion - turn up   | Frank Warmerdam, warmerdam at pobox.com
light and sound - activate the windows | http://pobox.com/~warmerdam
and watch the world go round - Rush    | President OSGeo, http://osgeo.org