Label Cache Performance

[Paul Spencer]

This would need to work for 'curved' labels too.  Would it work to do  
things per-character?

Paul

On 2-Jan-07, at 12:40 PM, Steve Lime wrote:

> 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

+-----------------------------------------------------------------+
|Paul Spencer                          pspencer at dmsolutions.ca    |
+-----------------------------------------------------------------+
|Chief Technology Officer                                         |
|DM Solutions Group Inc                http://www.dmsolutions.ca/ |
+-----------------------------------------------------------------+