Has anyone else extended SharpMap v.0.9 to make pretty linestring labels?

Topics: Algorithms, SharpMap v0.9 / v1.x
May 30, 2008 at 2:10 AM
Hi all,

I've used SharpMap to develop a prototype application for rendering map tiles for a VE/ Google-like mapping app.

One of the challenges in writing the prototype was to enhance the labelling to a quality level similar to google and VE.  For example, multiple label layers that do not clash, have an appropriate density and level of repetition, linestring labels that follow the path of roads etc.

I wrote a set of patches to SharpMap v.0.9 to add the extra functionality that I needed including some new classes (e.g. a LabelLayersCollection class that manages label clashes across a set of label layers, and a LabelFragment class that represents a substring of the label text, rotated to fit the underlying linestring; a set of LabelFragments make up a complete label).

Now that I've finished the prototype, I'm not completely happy with the code that rotates label fragments along a linestring.

Some of the problems I have encountered include handling closely-spaced vertices at high zoom levels, and coping with adjoing label fragments with very acute interior angles causing overlaps of the text of the two fragments.

The closely-spaced vertex problem I have handled by generalizing the line data in NetTopologySuite to suit the zoom level.

The overlapping fragments problem I have very roughly-handled using some heuristics to turn problem labels off.  A better solution might be to shift the labelling points of the label fragments so that the bounding boxes of the labels do not intersect, whilst maintaining alignment with the underlying linestring.

I would be interested to hear from others that have tried to solve some of these problems to hear if they were successful and what approaches were used.

Cheers.


Coordinator
May 30, 2008 at 8:56 AM
Hi toreapango, the labelling was definately something on my list of things to look at in the future.
My initial thoughts are:
The closely spaced verticies problem I think has to be solved by generalizing the line strings - preferrably up front not on the fly.

With the overlapping fragments - i'm not sure if you mean overlapping fragments of the same label clashing - or of fragments of nearby labels clashing?
Thinking out loud: could you represent each label as a multi-polygon using NTS where each label fragment is a polygon, then run intersection tests on the resulting collection of multipolygons - culling based on label priority and intersections. You could even put them into a quad tree first so that you do not need to compare objects that you know would not clash. This is not likely to be very fast so it would require some kind of caching mechanism - or taking a leaf out of googles' book - pre generate them all up front.. 

I'd be very interested to hear your progress.. jd
Jun 3, 2008 at 8:54 PM
Hi John,

Thanks for the reply, and sorry for the late response (public holidays etc):

>The closely spaced verticies problem I think has to be solved by generalizing the line strings - preferrably up front not on the fly.
Yes, I have generalized the data prior to rendering using NTS.

>With the overlapping fragments - i'm not sure if you mean overlapping fragments of the same label clashing - or of fragments of nearby labels clashing?
Yes, I did mean overlapping fragments of the same label, but overlapping fragments from nearby labels are equally undesirable.

I really like your suggestion of using a quadtree to spatially index the labels.  Currently I'm using a simple List for storing labels, but due to the smallish size of my dataset  (one small city of 300,000 or so people), performance hasn't been too much of a problem, but we all want something to work fast, right...:-)

I've also been using NTS polygons to represent the bounding box of each label fragment, and the bounding box of the complete label fragment.  Fragments are culled according to intersection tests and priority as you suggest.  The intersestion tests are done in two stages; a coarse test using the label bounding box, and a fine test using the fragment bounding boxes.

Currently I'm looking at calculating the minimum translation vector to move two overlapping label fragments, belonging to the same label, so that they touch rather than overlap.  The trick is that the minumum translation vector is constrained by the underlying linestring; I only want to be able to move label fragments along the linestring.  I don't know how well this approach is going to work, but I think it's worth a try; the idea being to shuffle the labels around so that a minimum of clashing labels get culled.

Cheers,

Ben.
Coordinator
Jun 4, 2008 at 10:21 AM
Sounds like you are on to a winner... good luck.. jd