Dynamic Map Labeling
Dynamic Map Labeling
复制标题
DOI：
10.1109/tvcg.2006.136
复制
发表时间：
2006-09
影响因子：
5.2
通讯作者：
K. Been;Eli Daiches;C. Yap
中科院分区：
文献类型：
--
作者：
K. Been;Eli Daiches;C. Yap
我们解决的问题，过滤，选择和放置标签的动态地图，其特点是连续缩放和平移功能。这包括两个相互关联的问题。第一个是避免标签弹出和其他导致混乱和中断导航的工件，第二个是以交互速度标记。在大多数公式中，静态地图标记问题是NP难的，快速近似可能具有O（n log n）复杂度。即使在交互过程中，当显示的标签数量可能比地图中的数量少几个数量级时，这也太慢了。在本文中，我们介绍了一组“一致”的动态地图标注，这具有理想的导航质量的desiderata。我们开发了一个新的框架，实现了desiderata的动态标签，并允许通过移动到预处理阶段的所有选择和放置决策的快速交互式显示。这个框架是通用的，足以容纳各种选择和布局算法。使用以前的框架似乎不可能实现我们的期望。在本文之前，没有动态地图或动态标签的正式模型，我们的论文介绍了这两个。我们制定了一个一般的动态地图标注优化问题，并给出了一个简单版本的问题的解决方案。简单的版本是基于标签优先级和一个通用的和直观的动态标签放置类，我们称之为“不变点放置”。尽管有这些限制，我们的方法提供了一个有用和实用的解决方案。我们的实现被纳入G-Vis系统，这是一个完整的细节动态地图的美国大陆。此演示可通过任何浏览器使用
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