A practical map labeling algorithm utilizing morphological image processing and force-directed methods

Automatic placement of text corresponding to graphical objects is an important issue in several applications such as geographical information systems (GIS), cartography, and graph drawing. We focus on realistic data and present a hybrid algorithm for labeling both line and point features. The first step of the method works on the discretized map and uses tools from morphological image processing. It leads to an initial placement of all labels in allowed (i.e., non-overlapping) position. The second step works on the continuous map and uses a force-directed iterative algorithm to improve this initial placement. In a comprehensive study on realistic data sets the strengths of the method (e.g., its flexibility and simple implementation) as well as its limitations (e.g., on dense maps the force-based method is only capable of small adjustments) are discussed.