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

Abstract

Automatic placement of text corresponding to graphical objects is an important issue in several applications such as Geographical Data Systems (GIS), Cartography, and Graph Drawing. While usually only a finite number of possible placements is available, in this paper we allow for an infinite number of placements and only require the label to be as close as possible to its corresponding feature. We focus on realistic data and present a hybrid algorithm for labeling both line and point features. In the method’s first step that works on the discretized map image processing tools are used to obtain 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 we investigate the performance of our method.