Label Cache Performance

[Steve Lime]

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

>>> Stephen Woodbridge <woodbri at swoodbridge.com> 1/2/2007 1:27:47 PM
>>>
Yes, it works for all cases. You have to think about the problem as a 
raster problem not a vector or character problem.

So you do this by creating an image the size of rectangular bbox of the

label. Then you render the the character or label polygons boxes into 
the image. The image now becomes a mask representing the pixels of
where 
the label will fall if it was rendered.

the test: Logical AND this mask image with the map label image given
its 
position in that image. You have a collision on the first AND result
the 
it true.

to update the map label image, just OR this label mask with the map 
label image given its position in that image.

if you want to test another location, ie: you are searching for an 
location nearby that the label will fit, then change the position by a

pixel and repeat the test. This is more costly than just a test, but is

still pretty efficient. I don't think you would want to apply this to 
every label, but having it as an option for a layer might be 
interesting. You could constrain this to say search up/down or 
right/left 10 pixels and then something like lot labels could easily be

staggered. This is just an idea and it might not farm out to be useful,

but once the machinery is in, it falls out as a simple variation on the

theme.

-Steve

Paul Spencer wrote:
> 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/ |
> +-----------------------------------------------------------------+