|
Article Excerpt
Introduction
Annotating realistic maps with pieces of text is an important problem in information visualization (see also the ACM Computational Geometry Task Force Report (Chazelle et al. 1999). Among others, it occurs frequently in automated cartography, i.e., in automated drawings of clear maps from geographic information systems (GIS) data or state diagrams in technical drawings. Manual placing of map labels in visualizing systems yields optically appealing label arrangements, but this task is very laborious and thus usually too time consuming. Because the data that have to be visualized proliferate rapidly, efficient algorithms for automatic label placements are imperative. For an overview of the current state of research for automatic map labeling, we refer to the map labeling bibliography maintained by Wolff (2006).
There are many variants of labeling problems such as fixed position models with or without scalable labels, slider models, label number, or size maximization problems. Complexity analysis reveals that the most interesting variants of these problems are NP-hard (e.g., Neyer 2001; Klau and Mutzel 2003; Wolff 1999). NP-hardness refers to the fact that no method is known to solve the problem in a time that only grows with a polynomial rate with respect to the size of the problem. Thus, to deal with these problems in practice, we must rely on good heuristic methods. This is especially the case if one has to deal with realistic problems arising in applications where both point and line features have to be labeled.
Due to the large number of different problem formulations, several algorithms for map labeling can be found in literature. Comprehensive surveys of algorithms for map labeling include Christensen et al. (1995) and Wagner and Wolff (1997). The methods usually rely on techniques such as greedy, exhaustive or rule-based search, methods based on combinatorial optimization models (such as simulated annealing) and methods from integer programming. We refer to the papers mentioned above and to Christensen et al. (1995), Doerscher and Freeman (1992), Ebner et al. (2003), Edmondson et al (1997), Freeman and Ahn (1987), Hirsch (1982), Klau and Mutzel (2003), Ruas (1998), Wolff et al. (2000) and Zoraster (1997).
In this paper, we aim at an automatic map label-ing algorithm that is able to deal with maps arising from GIS applications or automated cartography. Using a force-directed method allows us to consider an infinite number of possible label placements. In the problems with which we are dealing, both point and polygonal line features must be labeled, taking into account the following well accepted basic rules for map labeling:
Unambiguity: Each label can be easily identified with exactly one graphical feature of the layout. It should be intuitively apparent to the reader of the map which label belongs to which point or line feature.
Avoidance of overlaps: Labels should not overlap with other labels or other graphical features of the layout.
Unlike in synthetic maps, in the practical applications we consider in this paper, several additional requirements and adaptations of these basic rules have to be taken into account:
* All labels have to be placed, and no scaling of labels is admissible;
* Possibly several labels can belong to the same graphical feature;
* Each feature has an infinite set of possible label positions. The labels shall be placed as close as possible to the point features in order to maximize legibility of the maps;
* Point features are represented by rectangular boxes; only in special cases can these boxes degenerate and become non-expanded boxes;
* Both label and point boxes are of different sizes;
* Besides point and line features, other features may occur that shall not overlap with labels as well, i.e., the regions for possible label placements might be further restricted; and
* Preferred label positions (e.g., left or right to the object) have to be taken into account.
In this paper, we present a hybrid approach for automatic label placing that consists of two steps. First, we work on a discretization of the map to obtain a collision-free initial position for each label. Then, this initial position is iteratively improved using a continuous force-based method.
To obtain an initial configuration, we utilize techniques from morphological image processing (see Sonka et al. 1999). The starting position is generated on a discrete map generated from pixelizing the map as a binary image. To avoid overlaps, regions around line and point features are excluded before a label is placed. In order to find feasible regions for labels, we use a dilation technique for both point and line labels. This first step of our method results in a feasible configuration,...
|
