Dynamic map labeling

Ken Been, Eli Daiches, Chee Yap

Research output: Contribution to journalArticle

Abstract

We address the problem of filtering, selecting and placing labels on a dynamic map, which is characterized by continuous zooming and panning capabilities. This consists of two interrelated issues. The first is to avoid label popping and other artifacts that cause confusion and interrupt navigation, and the second is to label at interactive speed. In most formulations the static map labeling problem is NP-hard, and a fast approximation might have O(n log n) complexity. Even this is too slow during interaction, when the number of labels shown can be several orders of magnitude less than the number in the map. In this paper we introduce a set of desiderata for "consistent" dynamic map labeling, which has qualities desirable for navigation. We develop a new framework for dynamic labeling that achieves the desiderata and allows for fast interactive display by moving all of the selection and placement decisions into the preprocessing phase. This framework is general enough to accommodate a variety of selection and placement algorithms. It does not appear possible to achieve our desiderata using previous frameworks. Prior to this paper, there were no formal models of dynamic maps or of dynamic labels; our paper introduces both. We formulate a general optimization problem for dynamic map labeling and give a solution to a simple version of the problem. The simple version is based on label priorities and a versatile and intuitive class of dynamic label placements we call "invariant point placements". Despite these restrictions, our approach gives a useful and practical solution. Our implementation is incorporated into the G-Vis system which is a full-detail dynamic map of the continental USA. This demo is available through any browser.

Original languageEnglish (US)
Pages (from-to)773-780
Number of pages8
JournalIEEE Transactions on Visualization and Computer Graphics
Volume12
Issue number5
DOIs
StatePublished - Sep 2006

Keywords

  • Computational cartography
  • Dynamic maps
  • GIS
  • HCI
  • Human-computer interface
  • Label consistency
  • Label filtering
  • Label placement
  • Label selection
  • Map labeling
  • Preprocessing
  • Realtime

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Dynamic map labeling'. Together they form a unique fingerprint.

  • Cite this