基于空间索引与数据权重的可视化文字自适应剔除方法与流程

摘要: 本发明涉及计算机数据可视化的,具体涉及基于空间索引与数据权重的可视化文字自适应剔除方法。背景技术:1、随着大数据可视化、地理信息系统与交互式图表技术的快速发展,...
基于空间索引与数据权重的可视化文字自适应剔除方法与流程

本发明涉及计算机数据可视化的,具体涉及基于空间索引与数据权重的可视化文字自适应剔除方法。

背景技术:

1、随着大数据可视化、地理信息系统与交互式图表技术的快速发展,可视化场景中待展示的文字标签规模持续增长,文字标签作为数据信息的直接承载要素,其展示效果直接决定了可视化内容的可读性与信息传递效率。如何在有限的画布空间内实现海量文字标签的合理排布与自适应剔除,已成为可视化领域的核心技术问题之一。

2、目前主流的文字标签剔除方案存在以下不足:其一,标签剔除的优先级设计不合理。现有方案多按照数据默认顺序或随机顺序执行碰撞判定与剔除,未结合标签的交互状态、数据稳定度进行权重分级,导致处于选中、悬停等交互状态的标签,以及入库早、稳定性高的核心数据标签,容易被普通标签遮挡,无法保障高价值标签的优先展示,难以满足交互式可视化场景的使用需求。其二,碰撞检测的运行效率偏低。传统方案多采用暴力两两比对的方式实现标签重叠判定,时间复杂度为o(n2),即当标签数量持续增加时,标签两两比对的次数呈平方级增长,当标签数量达到万级以上时,计算开销呈指数级上升,无法满足实时交互场景的帧率要求。部分引入空间索引的方案存在索引结构单一、适配性差的问题,无法针对标签分布特征动态选择最优索引结构,且在相机平移缩放、标签状态变更等动态场景下需频繁执行全量重算,进一步加剧了性能损耗,容易造成交互卡顿。其三,判定精度与性能难以平衡。部分方案为压缩计算量简化了碰撞判定逻辑,仅通过轴对齐包围盒执行重叠校验,对旋转标签的判定误差较大,易出现包围盒相交但实际标签未重叠的误判;若全部采用精确几何判定,则又会大幅提升计算复杂度,无法适配大规模标签场景。

3、综上,现有可视化文字标签剔除技术难以同时兼顾展示优先级、判定精度与运行效率,无法适配海量标签下的动态交互场景需求。

技术实现思路

1、本发明提供了一种基于空间索引与数据权重的可视化文字自适应剔除方法解决上述提到的技术问题,具体采用如下的技术方案:

2、一种基于空间索引与数据权重的可视化文字自适应剔除方法,包含以下步骤:

3、根据待显示文字标签的交互状态评分与稳定入库顺序评分计算综合权重,对待显示文字标签按综合权重降序,并在综合权重相同时按预设的决胜键依次排序,得到全局处理队列;

4、根据当前相机变换矩阵计算待显示文字标签在屏幕空间中的轴对齐包围盒,并根据预设的画布边界,剔除完全位于画布外的标签,得到待检测集合;

5、建立空间索引实例,用于存储已被判定为显示的标签的轴对齐包围盒,并提供基于轴对齐包围盒相交性的范围检索接口;

6、依据全局处理队列的顺序,依次遍历待检测集合中的当前标签,以当前标签的轴对齐包围盒检索空间索引实例,得到候选标签集合;

7、若当前标签与候选标签集合中的任一候选标签存在真实重叠,则标记当前标签为隐藏,否则标记为显示,并将其轴对齐包围盒插入空间索引实例;

8、遍历完成后,将标记为显示的标签提交至绘制管线进行渲染。

9、进一步地,对待显示文字标签按综合权重降序,并在综合权重相同时按预设的决胜键依次排序,得到全局处理队列,包括:

10、以综合权重作为主排序键,对待显示文字标签进行降序排列;

11、当综合权重相同时,依次按照决胜键确定相对次序:

12、以交互状态优先级为第一决胜键,根据标签当前激活的交互状态类型按照预设层级顺序确定;

13、以稳定入库序号为第二决胜键,根据所述稳定入库序号的数值升序排列;

14、以稳定标识符为第三决胜键,根据所述稳定标识符的字典序或数值序升序排列。

15、进一步地,根据当前相机变换矩阵计算待显示文字标签在屏幕空间中的轴对齐包围盒,包括:

16、基于当前相机变换矩阵,将待显示文字标签的场景坐标映射至屏幕空间,得到待显示文字标签在屏幕空间中的锚点坐标;

17、根据待显示文字标签的宽度、高度及预设的锚点归一化位置,确定待显示文字标签在未旋转状态下四个角点相对于锚点坐标的偏移向量;

18、按照待显示文字标签的旋转角度,对偏移向量施加旋转变换,得到各角点相对于锚点坐标的旋转偏移量;

19、将锚点坐标分别与各角点的旋转偏移量叠加,得到四个角点的屏幕坐标;

20、将四个屏幕坐标在屏幕空间x轴方向的最小值与最大值分别作为轴对齐包围盒的minx和maxx,将四个屏幕坐标在y轴方向的最小值与最大值分别作为轴对齐包围盒的miny和maxy。

21、进一步地,空间索引实例采用四叉树或r树实现,四叉树或r树均通过统一的抽象适配接口接入;

22、抽象适配接口至少提供插入、删除、范围检索、清空及批量装载功能。

23、进一步地,四叉树的构建与检索方式为:

24、以屏幕画布坐标范围为根节点区域,配置节点容量上限和最大递归深度;

25、插入轴对齐包围盒时,若当前节点未分裂则直接存入,若已分裂,则将待插入的轴对齐包围盒下沉至完整落入的子节点,跨越子节点边界的保留于当前节点;

26、当任一节点存储的轴对齐包围盒数量达到节点容量上限且当前深度小于最大递归深度时,将该节点等分为四个子节点;

27、检索时,递归访问与当前标签的轴对齐包围盒相交的节点,合并该节点及所有相交子树中存储的轴对齐包围盒作为候选标签集合。

28、进一步地,r树的构建与检索方式为:

29、将轴对齐包围盒以最小外接矩形的形式插入r树中,每个树节点存储其所有条目的最小外接矩形;

30、插入时,从根节点开始选择使节点空间范围扩张最小的子节点作为插入路径,直至叶子节点,并沿路径更新各节点的最小外接矩形;

31、检索时,从根节点开始递归判断:若当前节点的最小外接矩形与当前标签的轴对齐包围盒不相交则跳过该节点及其子树,否则递归访问其子节点,直至叶子节点返回存储的轴对齐包围盒作为候选标签集合。

32、进一步地,真实重叠的判定具体包括:

33、若当前标签与候选标签均未旋转,则分别获取二者在屏幕空间x轴方向的第一投影区间和在y轴方向的第二投影区间;当两个标签在x轴方向和y轴方向的投影区间均存在正长度交集时,判定存在真实重叠;

34、若当前标签或候选标签存在旋转,则分别以各自的有向包围盒表征其几何范围,并基于分离轴定理进行判定:获取两个有向包围盒各边方向的法向量,去重合并后形成候选分离轴集合;对于候选分离轴集合中的每一分离轴,分别将两个有向包围盒的全部顶点投影至该轴,得到两个投影区间;当全部候选分离轴上两个投影区间均存在正长度交集,则判定存在真实重叠。

35、进一步地,在遍历完成并将标记为显示的标签提交至绘制管线之后,还包括帧间复用步骤:

36、若当前帧相对于上一帧未发生数据源变更、标签样式变更、交互状态变更、相机变换及画布尺寸变更,则直接复用上一帧的显示结果及空间索引实例,跳过全部碰撞检测流程;

37、若当前帧相对于上一帧仅发生相机变换,则复用全局处理队列,重新执行轴对齐包围盒计算、画布边界剔除、空间索引检索和真实重叠判定;

38、若当前帧相对于上一帧发生交互状态变更或标签尺寸变更,则执行局部增量更新。

39、进一步地,局部增量更新包括:

40、确定受变更影响的目标标签,获取目标标签的旧轴对齐包围盒与新轴对齐包围盒,以二者的并集扩张生成影响区域;

41、通过空间索引实例查询落入影响区域的当前显示标签,并通过预存的冲突关联表获取因与目标标签碰撞而被隐藏的标签;

42、将目标标签、当前显示标签及被隐藏的标签整合为受影响集合;

43、删除受影响集合在空间索引实例中的旧记录,对受影响集合重新执行排序和真实重叠判定,并根据判定结果更新空间索引实例及冲突关联表。

44、进一步地,执行局部增量更新时,当受影响集合中标签数量超过预设数量阈值、或影响区域面积与画布总面积之比超过预设面积阈值、或本次局部更新累计耗时超过预设时间阈值时,回退至全局重新计算。

45、本发明的有益之处在于,通过综合权重排序构建全局处理队列,能够保障高交互关注度、高业务价值的文字标签优先展示。在此基础上,依托空间索引完成宽相筛选,将全量标签比对压缩为局部候选标签比对,有效降低碰撞检测计算开销,提升海量标签场景下的运行性能。与此同时,结合轴对齐包围盒宽相过滤与真实重叠窄相校验,兼顾了运算效率与碰撞判定精度,能够适配旋转标签场景,从整体上有效解决动态可视化场景下文字标签重叠遮挡、高价值标签易被遮挡、运算效率低下的问题。