一种非完全的散点图去重叠算法
作者:
作者单位:

作者简介:

赵颖(1980-),男,博士,教授,CCF专业会员,主要研究领域为可视化,可视分析;秀昱宏(1997-),男,硕士生,主要研究领域为可视化,可视分析;唐涛(2001-),男,本科生,主要研究领域为可视化,可视分析;文陈飞宇(2001-),男,本科生,主要研究领域为机器学习,可视化;陈晓慧(1983-),女,博士,副教授,主要研究领域为可视化,可视分析;尤旸(1982-),女,设计总监,主要研究领域为营销分析,软件工程,数据可视化;周芳芳(1980-),女,博士,教授,主要研究领域为可视化,虚拟现实

通讯作者:

周芳芳,zff@csu.edu.cn

中图分类号:

TP391

基金项目:

国家重点研发计划(2018YFB1700403);国家自然科学基金(61872388,62072470)


Incomplete Overlapping Removal Algorithm for Scatterplots
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    散点图中数据点重叠现象会严重影响可视分析效率.现有散点图去重叠算法主要通过调整部分数据点的位置来完全去除重叠,但普遍存在画布面积增长、轮廓保持不自然、迭代时间较长等问题.认为完全去除重叠是非必须的,通过实验发现:用户能够在散点图有轻微重叠的情况下,快速、准确地完成数据点选取和区域密度估计等可视分析任务.因此,提出了一个非完全的散点图去重叠算法,该算法通过结合虚拟点临时占位、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.

    参考文献
    相似文献
    引证文献
引用本文

赵颖,秀昱宏,唐涛,文陈飞宇,陈晓慧,尤旸,周芳芳.一种非完全的散点图去重叠算法.软件学报,2023,34(2):945-963

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-09-24
  • 最后修改日期:2022-02-10
  • 录用日期:
  • 在线发布日期: 2023-02-10
  • 出版日期: 2023-02-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号