[Mapserver-users] label placement, how shape's center is determined

[Steve Lime]

It's not that simple...

It's a two step process. First, since we want to be as fast as possible we
look at the shape's bounding box and take it's center point. If that point
falls in the feature then it's used. In most cases this works very well. If
that doesn't work then I use a sampling technique to find points in 
the polygon. I never did find a good algorithm for finding a point in a polygon
so I developed something based on scanline conversion of polygons for
rendering them. That process busts the feature into a series of line
segements that are then drawn in the image. I took the same approach
to finding a label point in arbitrary polygons (with multiple parts and islands).
The code samples the polygon at various y values and does a scanline
conversion at each value. Throughout that process the center point
of the longest scanline segement (a horizontal line) is kept and eventually
becomes the label point. Draw it on paper and you'll see how it works.
It's quick, guarantees that the label point is IN the polygon and generally 
works ok. It is just a sample though so it's  not optimal. You could increase 
the sampling interval (look in mapprimative.c to change it) for better results.

The position switches are useless for polygons since there's really no frame 
of reference for the label. What are you UR or LR of? For points you have 
a feature you're orienting to so position makes sense. For lines only UC/LC/CC 
make sense.

Steve

Stephen Lime
Data & Applications Manager

Minnesota DNR
500 Lafayette Road
St. Paul, MN 55155
651-297-2937

>>> richard hornsby <rhornsby at io.osuedc.org> 02/07/03 04:11PM >>>

I'm looking through the maplabel.c file, trying to understand better how
the placement of labels within a shape is determined.

>From my tiny bit of C background, and from observing output, it seems like
mapserv is drawing a rectangle big enough to surround the shape, and then
finding the center of that rectangle.  Please correct me if this is not
how it works.

Using several different position switches (CL, CC, AUTO, etc) in the label
declaration of the map file doesn't seem to make any significant
difference in how labels are placed in oddly shaped polygons, such as
those for state senate districts.

Going with the above assumptions, my thought is that finding the largest
possible square (or rectangular) area *within* the shape would seem to be
a "better" (if slower, and far more difficult) method of determining where
to place the label...?  Conceptually this makes sense to me, but certainly
not in terms of how it would be done syntacially in C.

-rj
osuedc systems



--
Information Center, n.:
        A room staffed by professional computer people whose job it is to
        tell you why you cannot have the information you require.

rj hornsby . systems engineer . www.osuedc.org 
human and community resource development
p 614 688 8761 . f 614 688 8762


_______________________________________________
Mapserver-users mailing list
Mapserver-users at lists.gis.umn.edu 
http://lists.gis.umn.edu/mailman/listinfo/mapserver-users