Point Labeling with Sliding Labels in Interactive Maps
Point Labeling with Sliding Labels in Interactive Maps
复制标题
DOI：
10.1007/978-3-319-03611-3_17
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
N. Schwartges;J. Haunert;A. Wolff;Dennis Zwiebler
中科院分区：
文献类型：
--
作者：
N. Schwartges;J. Haunert;A. Wolff;Dennis Zwiebler
我们认为，在交互式地图中，用户可以平移和缩放连续的标记点对象的问题。我们允许标签沿其标记的点沿着滑动。我们假设每个点都有一个优先级;优先级越高，标记该点就越重要。给定一个动态的场景与用户交互，我们的目标是保持一个无遮挡的标签，这样，平均随着时间的推移，标记点的优先级的总和是最大化的。即使是问题的静态版本也是NP难的。我们提出了一个高效和有效的启发式标签点滑动标签在真实的时间。我们的启发式算法是渐进式的;它尝试一次插入一个标签，可能会推开已经放置的标签。为了快速预测哪些标签必须被推开，我们使用了一种划分屏幕空间的几何数据结构。使用这种数据结构，我们能够在渲染具有许多标签的地图时将帧速率加倍。
We consider the problem of labeling point objects in interactive maps where the user can pan and zoom continuously. We allow labels to slide along the point they label. We assume that each point comes with a priority; the higher the priority the more important it is to label the point. Given a dynamic scenario with user interactions, our objective is to maintain an occlusion-free labeling such that, on average over time, the sum of the priorities of the labeled points is maximized. Even the static version of the problem is known to be NP-hard. We present an efficient and effective heuristic that labels points with sliding labels in real time. Our heuristic proceeds incrementally; it tries to insert one label at a time, possibly pushing away labels that have already been placed. To quickly predict which labels have to be pushed away, we use a geometric data structure that partitions screen space. With this data structure we were able to double the frame rate when rendering maps with many labels.