Home | Business News | Browse by Publication | C | Cartography and Geographic Information Science

Placing text and icon labels simultaneously: a real-time method.

Article Excerpt
Introduction

Current technology enables computers and mobile devices to communicate with remote databases. Using this technique, cartographic data in remote databases can be queried and displayed locally in real time. In this paper we denote these types of maps as "real-time maps." This paper concentrates on text and icon labeling in real-time maps.

Text and icon labels are essential elements of many maps. The labels help the map reader to understand the cartographic objects in the map. For example, in navigational maps, it is necessary to use text labels on roads, landmarks, and important buildings; and icon labels are necessary to highlight points of interest. A major difficulty is to determine where to place the labels. In traditional cartography this has been a manual skill honed by cartographers, a skill that is difficult to describe analytically or even in words. However, some of the basic rules are that the labels should (cf. Imhof 1975):

* Have the correct font and size;

* Be easily associated with the correct object; and

* Not obscure other cartographic objects.

Automated text labeling has been on the research agenda for several decades. Text labeling can be divided into point, line, and area labeling, and several methods have been proposed for all these types (see bibliography maintained by Wolff (2004)). Icon placement has received less attention. A few algorithms were specially designed for icon placement (e.g., Harrie et al. 2004). Other algorithms treated icon placement similar to that of text labeling. For example, Dorschlag et al. (2003) placed icons (diagrams) and text labels in areas of maps by one and the same algorithm. We treat icon placement as a special case of label placement. That is, we treat icons as horizontal labels, and neglect the difference between them.

In this paper we propose a method of combining text and icon labeling into a common process, based on the previous work of the authors on text placement (Zhang and Harrie 2004) and icon placement (Harrie et al. 2004). Our previous work presented methods for computing candidate positions of text and icon labels. In this paper, these two types of candidate positions are combined into a common set, and the best positions of text and icon labels are found simultaneously by means of combinatorial optimization.

Combinatorial optimization has been used frequently in label placement (e.g., by Christensen et al. 1995; Zoraster 1997; and van Dijk 2001). The main contribution of this paper is the discussion and evaluation of methods of decreasing the search space in connection with optimization. The reason for decreasing the search space is to find an acceptable solution within a limited number of iterations in the combinatorial optimization; thus to create acceptable maps with limited processing time.

This paper starts with a short review of previous work in automated label placement, followed by an outline of our method. The method is divided into four phases, and candidate positions are computed for the text and icon labels in the first two phases. A combinatorial optimization method is then proposed to find suitable positions of both the text and icon labels. When there is label overlap that combinatorial optimization has failed to solve, the fourth and final step is executed to remove some labels. Experimental results are presented in the last but one section. We end with a discussion of the existing problems and further developments, followed by conclusions.

Previous Work

Among point, line, and area labeling, point labeling has been most thoroughly studied (see bibliography maintained by Wolff (2004)). Jones (1989) implemented a point-labeling method using the Prolog programming language. He defined a number of candidate positions for the label for each point object. Then the candidate positions were classified according to whether cartographic objects would be hidden. The label was placed in the best possible location, and then the next label was considered. If the position of one label concealed a suitable position for another label, the method allowed backtracking.

Christensen et al. (1995), Zoraster (1997), and van Dijk (2001) defined point labeling as a combinatorial optimization problem, where an objective function is created based on label-label and label--symbol overlap. A search space is then constructed by the permitted positions of the labels. Finally, the minimum of the objective function (i.e., the optimal label positions in conformity with the constraints) is computed by using a minimizing strategy (simulated annealing, genetic algorithms, etc.). Combinatorial optimization techniques for text placement have also been implemented in commercial systems (ESRI 2004). van Kreveld et al. (1999) proposed an approximation algorithm to label points in continuous search spaces; the labels were allowed to be placed anywhere they touched the points. This model is called the slider model. Strijk and van Kreveld (2002) extended the slider model to avoid overlap between labels and line features. Their algorithms for point labeling in the slider model are computationally efficient, which allows implementations in a real-time computing environment.

With regard to line labeling, methods of placing both straight labels (Edmondson et al. 1997) and curved ones (Wolff et al. 1999) have been proposed. Edmondson et al. (1997) proposed an algorithm to search for a large number of discrete candidate positions along line features, and then place straight labels at one of these positions according to quality evaluation. Wolff et al. (1999) suggested a method of generating a strip along an input line feature, which is then used to select good candidate placements for a curved label, based on quality evaluation. As a special case of line labeling, street labeling has also been studied. Chirie (2000) implemented three rules in his algorithm: (i) the names must be written along and inside streets; (ii) names must not be upside down; and (iii) name lengths should be adjusted to street lengths.

Area labels need to be bent and stretched across the horizontal axis of the associated area to make the association clear (Imhof 1975). Barrault (2001) introduced an approach to extract a set of circular support lines (on which the label will lie) of an eroded area being labeled. The support lines were then assessed against their conformity to the shape, latitudinal and longitudinal fitness, and...

View this article FREE - Now for a Limited Time, try Goliath Business News
Free for 3 Days!