Label Cache Performance

[Steve Lime]

Duh, good point...

The non-rectangular bounds are still problematic but perhaps there are
work arounds as 
suggested by Robert H...

Care to draft an RFC?

Steve

>>> Stephen Woodbridge <woodbri at SWOODBRIDGE.COM> 1/3/2007 9:35:26 PM
>>>
Steve Lime wrote:
> We use the loops for MINDISTANCE because we obviously are already
doing
> so for collisions.
> 
> I thought about a hash too. Trouble is it's based not solely on the
> label text, but
> also class and layer indexes. For example you wouldn't want to ommit
a
> road
> label 'Washington' because of it's proximity to 'Washington' lake.
> Those types of
> situations are not all that rare...

Sure, but if you do the bitmap collision detection and use the hash for

MINDISTANCE, the hash would only exist while you are processing a
single 
layer and then get dumped and a new hash created for the next layer. If

you need to keep hash entries unique by CLASS also, then you could 
either create an array of hashes and index by classnum or have a single

hash and prefix ot postfix the keys with the class like
"classnum:key".

This should be very straight forward and I think very, very fast 
compared to the way it works now. I'm sure there are other little 
adjustments that would need to be made, but I can't think of any show 
stoppers.

-Steve

> Steve
> 
> 
>>>> Stephen Woodbridge <woodbri at SWOODBRIDGE.COM> 1/3/2007 12:14:06 PM
>>>>
> 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/
|
>>>
+-----------------------------------------------------------------+