This section presents the capabilities and functionalities of a labeling engine implemented in MapSurfer.NET.

Automated label placement is known as one of the most difficult and complex problems in computer cartography. Therefore, it is normally split up into smaller and simple independent sub-problems, or sub-tasks. These sub-tasks (see figure below) are defined as:

  • Candidate-position generation: A method that generates a set of label candidates for each map feature, using its spatial characteristics and taking into account its type (e.g., point, line or area). The generated label positions (candidates) are considered as the search space for the position selection procedure.

  • Position evaluation: A process of scoring each label candidate using a quality function, which measures how well a label is positioned with respect to the geographic object it tags as well as to other labels and features on the map. In general, the quality function should consider and reflect formal cartographic guidelines (see works by Imhof, 1975 and Wood, 2000) applied to a certain type of designation.

  • Position selection: A process of choosing only one label position from each set of candidates so that the total sum of labels scores is globally maximized. The higher the score, the more superior level of cartographic quality of the resulting labeling.

Candidate-position generation

In cartography, geographic features are labeled using three classes of label placement (or designations). They are position (e.g., settlements, peaks, etc.), linear (e.g., rivers, streams, mountain ranges, paths, etc.) and areal (e.g., countries, islands, lakes, valleys, etc.) designations. Each type of designation has its own principles and requirements.Furthermore, every type of designation can have different forms of presentations, for example, an island can be labeled using either a horizontally aligned text or a curve text. For more information, we refer to a fundamental work by Eduard Imhof (1975).

In MapSurfer.NET framework, the type of designation (or label placement type) is specified in LabelPlacement property of a corresponding symbolizer. LabelPlacement property can take one of the following values:

A diagram of label placement types available in MapSurfer.NET is presented in the following figure.

Quality evaluation

The quality function computes a single numerical score by using a function that is normally expressed through a weighted sum of single metrics van Dijk et al., 2002. These metrics reflect, in one way or another, the formalized cartographic precepts (Imhof, 1975; Wood, 2000). According to van Dijk et al. (2002), this function can be expressed as:.

where L is a set of labels on the map, F is a set of non-textual map features, wi, i = 1,2, . . . ,5 are the weights that define the contribution of each metric to the overall quality value. The functions q*, or metrics, correspond to cartographic criteria summarized by the cartographers in various textbooks and scientific articles.

MapSurfer.NET's labeling engine has partial implementation of quality metrics given in the above-mentioned equation. The list of supported quality metrics is:

Position selection

Position selection task is treated as a mathematical optimization (or mathematical programming) problem which can be solved using one of the existing algorithms, for example, greedy algorithm, discrete gradient descent method, simulated annealing algorithm, genetic algorithm or tabu search heuristic. Note that the selection is an NP-hard problem in general. Therefore, all listed algorithms, often called solvers, try to find a feasible near-optimal solution for label placement.

At the moment, the following solvers are implemented and available in MapSurfer.NET:

You can find more details about solvers and their parameterization in Section Solvers.