1.3.2 顶点采样方法
顶点作为一个最小单位,是要素模型中一个极其重要的特性。矢量数据中线对象、面对象及组合对象的近似是对要素逐步化简的过程,通过顶点采样方式,将地理要素划分为不同长度的子序列,进而获得地理要素的近似对象。以顶点为基本粒度,采用近似方法来进行顶点序列划分,揭示和划分顶点层次并对其进行分析是了解现实生活中各种地理要素组织结构的一种重要思想。
本节通过总结几种常用的顶点序列采样策略,获得一般性的顶点采样与线划分的过程。设线对象L由顶点序列(P 0,P 1,…,P n)组成,顶点序列构成的线无自交。对任意i≠j则P i≠P j,且S P i,P i+1∩S P j,P j+1∈{P k},k＝0,1,…,n,所有的相邻顶点组成的线段没有内部交点。顶点序列的处理过程如下:首先将L＝(P 0,P 1,…,P n)化简至最简单形式即L′＝(P 0,P n)即只包含两个顶点的序列,然后计算L与L′的差值,即ε0,0＝d(L,L′),并将此误差关联至L′。假设每次采样选择一个顶点,依据顶点采样策略选择顶点P i,将L进行二分以形成2个子序列,分别记为L 0,1＝(P 0,P 1,…,P i)与L 1,1＝(P i,P i+1,…,P n),将L 0,1与L 1,1分别化简至最简单形式,即
(P 0,P i)及
,并计算两者的误差
与ε1,1＝
,将ε0,1关联至
,将ε1,1关联至
,继续这一迭代过程,直至所有的序列都被划分至只包含两个顶点为止。
划分点的选择策略是要素数据预处理的关键点之一,本节介绍几种朴素的顶点采样方法:随机采样、等间隔采样、Douglas-Peukcer(DP)算法与Visvalingam-Whyatt(VW)算法。DP算法和VW算法是线状要素抽稀的经典算法,在大规模线要素中使用,既可以精简数据量,也可以在很大程度上保留几何形状。在地图综合中,也称作地图数据的概化算法。
(1)随机采样
随机采样是一种简单的地理要素简化方法,除起止点外,随机选择采样点,采样点将线对象划分为两个子线段,递归执行采样与划分,直到所有的中间节点均被采样。如图1-1所示,给定线对象L＝{P 0,P 1,…,P 8},除起止点外,随机选择P 1,P 2,…,P 7的任意一点进行划分,若选择P 2,线对象L被划分为L 1＝{P 0,P 2}和L 2＝{P 2,P 8};继续对L 1和L 2进行划分,随机选择L 1和L 2中任意一点,若选择P 1和P 6,则L被划分为L 3＝{P 0,P 1}、L 4＝{P 1,P 2}、L 5＝{P 2,P 6}、L 6＝{P 6,P 8};重复上述过程,直至子线段不可划分。
图1-1 随机采样示例
(2)等间隔采样
等间隔采样设置间隔值,依据特定间隔选点对线对象进行递归划分,直到遍历到每个顶点为止。如图1-2所示,给定线对象L＝{P 0,P 1,…,P 8},设置采样间隔为1,每间隔1个顶点选择采样点,L被划分为L 1＝{P 0,P 2}、L 2＝{P 2,P 4}、L 3＝{P 4,P 6}和L 4＝{P 6,P 8};继续以间隔k＝0划分,L被划分为L 5＝{P 0,P 1}、L 6＝{P 1,P 2}、L 7＝{P 2,P 3}、L 8＝{P 3,P 4}、L 9＝{P 4,P 5}、L 10＝{P 5,P 6}、L 11＝{P 6,P 7}、L 12＝{P 7,P 8}。
简化后的对象与原始对象之间的差异与使用的采样方法和简化程度有关,随着简化程度逐渐减小,差异逐渐变小,当采用随机采样和等间隔采样将顶点全部遍历后,两者间的差异缩小为0。本节将逐步简化后的对象与原始对象所围成的面积值作为误差值,衡量地理对象的简化程度。
(3)Douglas-Peukcer算法(https://www.daowen.com)
图1-2 等间隔采样示例
图1-3为DP算法的示意图。DP算法的基本思路如下:①首先设定距离阈值ε,将待处理线对象L 0＝{P 0,P 1,…,P n}的首末端点虚连一条直线S P 0,P n;②求L 0上任意中间顶点P k,0＜k＜n与直线段S P 0,P n的距离d(P k,S P 0,P n),找出最大距离的顶点P m,最大距离值d(P m,S P 0,P n)满足d(P m,S P 0,P n)≥d(P k,S P 0,P n),0＜m,k＜n;③将最大距离值与阈值相比较,若d(P m,S P 0,P n)＜ε,这条线上的中间点全部舍去,算法结束;若d(P m,S P 0,P n)≥ε,则以P m为分割点将线对象分为两条子曲线;④对两部分子曲线重复上述步骤,直至所有的点都被处理完成。
图1-3 DP算法示例
设定εk＝d(P k,S P i,P j),0＜i＜k＜j＜n,εk表示顶点P k与线对象子曲线L 0＝{P i,P i+1,…,P j}的基准线S P i,P j的偏离距离。通过距离阈值ε,可以保证线对象的简化结果与原始线对象的最大位置误差保持在一定范围之内,从而实现误差控制。
(4)Visvalingam-Whyatt算法
图1-4为VW算法的示意图。VW算法的基本思路如下:①首先设定距离阈值ε,对于线对象L 0＝{P 0,P 1,…,P n}中的任意中间节点P k,0＜k＜n,计算所有中间节点与其相邻的两点P k-1、P k+1所包围的三角形面积SΔP k-1P k P k+1;②找出面积最小的顶点P m,面积值为SΔP m-1 P m P m+1,满足SΔP m-1P m P m+1≤SΔP k-1P k P k+1,0＜k,m＜n;③将最小面积值与阈值相比较,若SΔP m-1 P m P m+1＞ε,则所有的中间节点都保留,算法结束;若SΔP m-1P m P m+1≤ε,则删除该点,连接P m-1、P m+1;④对新生成的曲线循环执行选点与删点操作,直至所有的面积均大于阈值。
图1-4 VW算法示例
在一些情况下,中间顶点与其相邻两顶点之间所构成的三角形面积可能很小但形成的空间距离较大(即角度很小的锐角),也可以作为重要顶点保留,但VW算法根据面积判断很可能将其删除,而DP算法中不会出现这种情况。因此,两种算法在简化结果上会存在视觉差异。
