As Gary announced in his last post, I'm one of the students accepted for Google's Summer of Code program. During the summer I'm going to work on better label placement capabilities. Since the application form is not publicly available, I put here the interesting part that briefly describes the main areas I'm going to address. If you have any suggestions, please leave me a note in the comments. In the next few days I'd like to refine the ideas and prepare a roadmap for the implementation in form of a Request For Comment (RFC).

Introduction

Quantum GIS has currently only limited functionality for labeling of vector layers. It's possible to turn on labeling of vector features and specify the field containing the label. User can set label style (font, color, buffer) and alignment (offset, rotation). Additionally, these properties can be defined for every feature by its attributes, allowing e.g. different color for every feature.

The labeling however lacks other important features. There's no detection of collisions between labels, so the labels overlap each other, producing often unreadable results (especially in cases with many features on screen). In situations where labels overlap, it's necessary to choose only one of them.

For polylines and polygons, QGIS uses a simple centroid alignment of the label. In many cases, labels for lines should follow the shape of the geometry or should be rotated and placed on a straight part. When labeling polygons, sometimes centroid isn't the right place for the label (e.g. polygon with holes).

Finally, there are situations where automatic label placement needs some manual improvements. GUI should be provided to help the user to edit the placement - hide/show some labels or change the positions.

The idea

My target is to implement improved automated label placement with possibility for manual tweaks of the placement. There have been quite some research about the map labeling problem and many methods have been developed (an introduction to the topic [1]). I like the combinatorial approach for labeling at most: a set of candidate labels is produced for every map feature, a collision graph is created from the candidates and a heuristic is used for deciding which labels are to be displayed.

Recently, an open source library PAL [2] has been created that implements several label placement algorithms. It would be good to use this library within QGIS to determine which label candidates to render. The placement should be common to all layers, so even labels for features in different layers shouldn't overlap.

I'd like to add the possibility to rotate (or even bend) the labels to follow lines and a smarter algorithm for polygon labels (to avoid situations when label is not contained in polygon). For multi-part features user should decide whether to use just one label or every part should be labeled.

I have in my mind two approaches: a) fast, simple placement that would be calculated every time the map gets rendered. Suitable when the user just wants to see some labels, not really concerned about the quality. b) placement that is recalculated only on request. This can be used when preparing a map for some output. There's also a need for tools where the user could modify such placement - by either changing priorities for candidate labels or by manually setting the visibility, alignment and appereance of label.

When using b) placement method, the placement result should be saved in the project file or in a separate "label placement" file - not yet sure what's better.

[1] http://i11www.ira.uka.de/~awolff/pub/w-alptp-99.pdf
[2] http://geosysin.iict.ch/pal-trac