Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster.
翻译:在地理空间点数据中,广泛研究的制图和地理信息系统特征标签是一个典型的问题。与此同时,字云是一个流行的可视化工具,用来显示文本数据中最重要的字词,该工具也扩大到地理空间数据的可视化(Buchin等人,Pacific Vis 2016年)。在本文中,我们研究一种混合的可视化,将字云和点标签的各方面结合起来。在考虑的设置中,输入数据包含一组按类别分类分类的点,我们的目标是将每个代表一个类别的多组脱节和轴对齐矩形排列,从而在自然质量限制下覆盖相同类别的点。因此,我们把注意力放在计算成的矩形内,在计算覆盖全球主要类别(以字圈式方式)的覆盖点时标上,同时在当地避免对点作过度的曲解(即保留点标签的精确度),我们的目标是将最小的矩形矩形组计算得更快。因此,我们把注意力转向了(主要)同一类别的点点点点,我们把注意力放在计算中,我们所制作的视觉质量和数字分析的模型上,我们用来测量的模型,我们用来测量和计算。