User:Esscue/Labelling

Here I would like to present my attempt to create a label placement optimizer for Osmarender. I like the basic idea of Osmarender to transform the osm xml data via a xslt stylesheet directly to a svg file. However, this approach has a fundamental disadvantage: Xslt is perfect for transforming xml data, but it is not designed for doing complex calculations. But even if we use an own xslt processor (e.g. orp) optimal label placement is hard to implement. This is because you need to know how a label will be rendered in the final svg file. For creating a more or less generic solution it is necassary to have a implementation of the svg standard which is accessible via an API.

Fortunately there exists a very nice designed and powerful API for rendering and dynamically changing svg files: http://xmlgraphics.apache.org/batik/

Having solved the pure technical problem of how to access the svg files created by Osmarender, I was able to start coding a java postprocessor for Osmarender.

An algorithm for optimal label placements

The problem of finding the optimal label placement is a complex task. However there are many ideas how to solve this. Most of the algorithms reduce the problem to a combinatorial optimization. In my opinion, one of the nicest among them is simulated annealing. The paper A General Cartographic Labelling Algorithm of Shawn Edmondson, Jon Christensen, Joe Marks and Stuart M. Shieber describes in an excellent way how one could use simulated annealing for finding an optimal label placement which also satisfies aesthetic needs. This paper founds the basis of my implementation.

Features

There are already some interesting features implemented:

Generic and extendable code: It should be possible to implement all kinds of cartographic knowledge that can be somehow quantified.
Extendable preprocessor
- preprocessor for connecting part of streets belonging to the same street
Optimize labels
- Extendable position generator where all possible label positions are created before the optimization starts
- Try to avoid overlapping labels
- Try to avoid an overlap of labels and point features (e.g. symbols on the map, housenumbers)
- Optimize street labels
  - Try to figure out the optimal number of labels for large streets
  - Try to find an uniform placement of the labels belonging to a street
- Optimize point feature labels
  - Try different label positions around the point feature

Todos

As you'll see if you have a look at the examples there is still room for improvements:

Optimize area feature labels
- Find the area in the svg file where the label belongs to
- Find a set of possible positions for the label
Create a preprocessor for splitting and reversing streets if otherwise labels would be printed upside down
Try to avoid having parts of labels cut off at the edge
Line wrap for point feature and area feature labels (thanks to Frederik Ramm for this idea)
Avoid placing street labels into bends (see "Soldhofstraße" on the top of the example renderings)
Avoid label positions that lie partly outside the visible part of the map.

Examples

You can access the subversion repository (http://svn.openstreetmap.org/applications/rendering/OSMLabelOptimizer/) and test OSMLabelOptimizer. The repository contains a INSTALL file which describes how to get the application running.

Here are some pictures created with OSMLabelOptimizer: