【摘要】 散点图中数据点重叠现象会严重影响可视分析效率.现有散点图去重叠算法主要通过调整部分数据点的位置来完全去除重叠,但普遍存在画布面积增长、轮廓保持不自然、迭代时间较长等问题.认为完全去除重叠是非必须的,通过实验发现:用户能够在散点图有轻微重叠的情况下,快速、准确地完成数据点选取和区域密度估计等可视分析任务.因此,提出了一个非完全的散点图去重叠算法,该算法通过结合虚拟点临时占位、Voronoi网格划分、数据点选择性移动和重叠率快速计算等方法,实现分布紧凑、轮廓自然、高效迭代的散点图去重叠效果.通过客观实验和主观实验评估了算法性能.实验结果表明,该算法在移动距离、面积增长、形状保持、正交顺序、邻域保持这5个客观指标和形状相似性、类簇稳定性这2个主观指标上都优于现有算法.更多还原

【Abstract】 Data point overlapping frequently occurs in scatterplots, resulting in visual clutters to interfere visual analysis. Some overlapping removal algorithms have been proposed to remove data point overlapping completely, however, they have some common shortcomings, mainly including the increasing of canvas size, distortion of data distribution, and dissatisfaction of time consumption. This work proposes that the complete removal of data point overlapping is non-essential, while slight overlapping is acceptable in some data analytical scenarios. Therefore, an incomplete overlapping removal algorithm is designed for scatterplots. First, the algorithm generates virtual data points in the blank areas in a scatterplot by using a semi-random generation method. Second, the algorithm uses a Voronoi diagram to divide each data point into an irregular grid, and then moves data points to grid centers to reduce the rate of data point overlapping and maintain the natural contour of data distribution. At last, the algorithm iteratively runs the step of Voronoi meshing and data point moving until that the rate of data point overlapping reaches a preset threshold. A series of objective and subjective experiments are conducted to evaluate the performance of the proposed algorithm and reference algorithms. The results show that users can quickly and accurately accomplish visual analysis tasks, including data point selection and regional density estimation, in scatterplots with a slight data point overlapping. The results reflect that the proposed algorithm is superior to all of the reference algorithms in the objective and subjective indicators.更多还原