Label Cache Performance

[Stephen Woodbridge]

If I were dealing with the MINDISTANCE issue in Perl I would create a 
hash where the key was the label text, because that is what MINDISTANCE 
is restricting, and make the hash value an array of locations. This 
would much faster than any search algorithm and you would narrow the 
search to the array of placed text items of the same name.

There is no reason this approach could not be used for the MINDISTANCE 
case in mapserver. Using this and the bitmap collision detection should 
remove most of the overhead of the label cache processing and make it 
very scalable with respect to number of items to be processed.

-Steve

Steve Lime wrote:
> 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/ |
>> +-----------------------------------------------------------------+