An algorithmic study of practical map labeling

Abstract

Label placement is a challenging task in map production, both manual and automatic, and is crucial for the overall map quality. While practical label placement algorithms are typically fast and can compute overlap-free positions of thousands of labels within seconds, the resulting maps usually do not meet the high quality standards. To build a more “intelligent” labeling process, we address the following two problems. Firstly, the existing labeling process isolates the automatic process and human involvement. An ideal labeling process should combine the computational power of algorithms with the human involvement. This can be achieved by a human-in-the-loop label placement process with the interactive collaboration between humans and algorithms. We propose a framework for semi-automatic labeling placement. Moreover, we investigate dynamic labeling approaches, which could be embedded in such an interactive framework to handle the changes efficiently and robustly. Secondly, the classic map labeling model in computational geometry is ill-defined. Given a set of label candidates, one usually aims for a set of pairwise overlap-free and hence legible labels such that the number of labeled features is maximized. This model is based on the assumption that all of the features are from one category. However, maximizing the size or total weight of the labeling does not reflect the aim of selecting a good mixture of different object types. Motivated by this, we study map labeling problems with categorical information. As our first step, we investigate the category-aware labeling problem whose goal is labeling with a balanced mixture of categories. Then, we devise a novel labeling layout aggregating labels of the same category. We study its theoretical model and develop heuristics and exact solvers to compute our visualizations.