Polyline labeling algorithm

Hi all,

I am developing a pocketPC based mapping application and need to label
polyline data (mostly roads). I have seen various other mapping
applications, which label a polyline with and "anchor point " on the
polyline and its label in normal left to right direction. Further, it
is apparent that given N polylines, this labeling algo should satisfy:

1) labels do not overlap each other
2) they are "anchored" on a visible area of the polyline (curerntly
visible to the user in the viewport)

3) they do not seem "cluttery" (!)

I do not expect ArcGIS like "curved" "creeping along the polyline" kind
of algo, something simpler and less computationally intesive..

I could hardly find any algorithms/implmentations for this on the net,
however I did find this link: http://www.cs.dal.ca/news/def-1122.shtml

be glad if someone could give me some pointers on this.

Thanks
Suraj

suraj wrote:

As noted in the paper you cite, in general this is an NP-hard problem
(i.e., intractably difficult), but the good news for you is that (from
my
personal experience), I can verify that simple approaches seem to
work pretty well when you're annotating things like road networks,
utility lines, rivers, etc. E.g., if you have a street that has ten
"intersections", just randomly choose one of the centerlines between
intersections and place your annotation so that it's centered on the
midpoint of that centerline. If that annotation collides with another
one that was previously placed, chose another centerline of that
street. If there's no other centerline to choose from, then move the
previously placed annotation.

It will help if you consider the labels as rectangles rather than text
when you're trying to detect collisions. Then once you've resolve
the collisions, you can just place the text within each box so that
it's generally upright. Since the kinds of things GIS features
represent are static in nature (streets stay put for years at a time),
you can store the annotation as part of the feature -- i.e., you don't
have to dynamically figure out the best placement each time you
generate the display -- and just turn it on or off at various zoom
levels.

Bob