3.1.1 基于DP和VW算法的顶点层次结构
对于大数据量的数据可视化来说,虽然数据可以分布存储在集群中,数据仓库可以存储包含数十亿的表或记录,但是传统的数据可视化工具往往并不适用,这是因为数据可视化与分析在客户端进行,计算机内存中不能存放大规模数据。交互式数据可视化对查询效率的要求更高,数据简化是一种广泛使用的方法。在简化线对象的过程中,建立线对象的顶点层次结构,并将部分数据传输至客户端,在不影响显示效果的前提下,能够保持与原始数据相似的特性,并能提高查询的响应速度。
DP算法经过不断地拓展和完善,已成为GIS领域中线对象简化最为常用的算法之一。DP算法将线对象递归划分为两段,通过保存线简化算法中计算得到的中间结果数据,将线对象的输出复杂度降低到O(k)(k为输出数据量),对于简化所造成的视觉差异可交互控制。本节以DP算法与VW算法为基础说明线简化算法与层次结构的相关关系,探究两种线简化算法在地理要素近似与顶点选择策略中的差异。
为实现线对象及组合对象的近似查询,将顶点序列由线性结构转化为顶点层次结构,由此建立以层次结构表达的线对象、面对象及组合对象。将顶点序列转化为层次结构需要递归地将顶点序列不断地划分为互不覆盖的子序列,直到每段子序列中只包含一个顶点,这样一段递归划分的过程直接对应一个特定的层次结构,每个树节点对应一段顶点子序列。
空间对象L j＝{P 0,P 1,…,P n},由若干顶点P j(0≤i≤n)组成,对于任意的顶点P i(0＜i＜n),依据一定的判定准则对顶点逐步采样,形成中间顶点集合的采样顶点序列,并依据顶点源序列与采样顶点序列建立二叉树,该二叉树能够表现空间对象中存在的顶点层次结构,并可直接用于处理空间近似查询。以线对象为例,以现有的DP算法与VW算法作为顶点序的计算准则和判定依据,建立顶点序列层次结构表达。
在执行DP算法时不设置限定条件,即将阈值ε设置为0,这种不含限定条件的算法处理过程称为完全DP算法。完全DP算法将在线对象L 0的所有中间顶点被选择完成后终止,选点过程可视为在原始线对象上对顶点逐步采样形成采样顶点序列的过程。以图1-1中线对象为例,图3-1为基于完全DP算法的顶点递归采样,浅灰色方框为采样顶点。
图3-1 基于完全DP算法的顶点递归采样
在上述过程中,所有的顶点序列划分形成的层次关系能够直接采用二叉树进行表达,按二叉搜索树的构建方法,将这些顶点按照在DP算法中被选择的顺序建立二叉树,并在每个树节点上关联该顶点的误差值εi,h,其中i表示树节点在同一层中的序号,而h表示树节点离根节点的距离,即节点的高度。在这棵二叉树中,叶节点表示由2个相邻顶点所构成的序列,中间节点表示长度大于2的顶点序列。图3-2为基于完全DP算法的构建的顶点二叉树,可以看出二叉树中的每个节点为递归采样过程中选取的采样点。(https://www.daowen.com)
图3-2 基于完全DP算法构建顶点二叉树
同样地,若执行VW算法时,将阈值ε设置为正无穷,那么VW算法将在依次删除线对象中的除首尾点外所有顶点后终止。VW算法是逐次删除顶点的过程,若将顶点删除的顺序按照逆序排列,则可理解为是线对象逐步选点采样并形成顶点序列过程。图3-3为基于VW算法的顶点递归采样,浅灰色方框为采样顶点,即删除的顶点。然后,将采样顶点按照删除顺序的逆序建立二叉树,从树的根节点开始深度遍历每棵子树对应的顶点距其左右边界顶点基准线的距离,将最大值记录在对应节点上。图3-4为基于VW算法构建顶点二叉树。
图3-3 基于VW算法的顶点递归采样
图3-4 基于VW算法构建顶点二叉树
