张小望
(广东省电力设计研究院 510600)
【摘 要】 本文在研究现有的自动绘制等值线算法的基础上,提出了一种改进的基于点的构网算法,由此形成新的网形结构,并针对这种网形结构设计出了等值线的追踪方案。和传统的三角网法绘制等值线相比,该方法不仅提高了联网和追踪的速度,新的网形结构还为非线性内插等值点创造了条件。
一、引 言
计算机自动绘制等值线是一个重要的研究课题。就目前来说,建立数字地面模型,自动绘制等值线常用的方法有网格法和三角网法。网格法的基本思想是利用局部区域内的离散高程数据点,建立一个逼近于地形表面的曲面模型,并在这个曲面模型上内插出网格点的高程值,形成一组规则的矩形网格数据,然后在每个网格边上通过线性内插,计算出某高程值各条等值线所有等值点的平面位置,并按一定的方案,把这一高程值每条开、闭曲线的所有等值点全部追踪出来,最后将追踪排列好的等值点联结成光滑曲线。三角网法则是直接利用原始离散高程点联结三角形网,建立数字地面模型,在三角形的边上线性内插出某高程值各条等值线的所有等值点,然后按一定的方案,将每条开、闭曲线的全部等值点依次追踪出来,最后联成光滑曲线。同网格法相比,三角网法保持了原始数据的精度,避免了网格法中容易出现的点线不符以及丢失部分等值线的情况,现有的大比例尺数字测图系统多采用这种方式。
迄今为止,建立三角网数字高程模型的算法有多种,比较流行的算法是以D elaunay三角形法逐边扩展。其基本思想是先以两个距离较近的离散点组成一条基边扩展三角形,然后再依次以已经形成的三角形的各边为基边向外扩展三角形,直至所有的三角形都不能向外扩展为止。由于使用这种方法在逐边扩展三角形的过程中,需要不断地进行三角形的重复和交叉检查,随着已经形成的三角形数量的增多,联网速度将会越来越慢。再者,这种逐边扩展所输出的结果,也只是一个个相对的三角形,既不利于引入更多的地形信息,实现等值点的非线性内插,也不利于提高等值线的追踪速度。
二、基于点的构网算法
1.原始数据的预处理
原始数据预处理的目的是进行数据的错误检查,如离散点的重点错误等,同时建立栅格索引,即以适当的步长,将整个离散点的分布区域划分为若干大小相等的栅格,每个栅格内的点作为一组,按栅格来建立离散点的索引方式。在逐点联网的过程中,只对该点所在栅格以及相邻栅格内的点搜索判断,而无需对整个构网区域内的所有离散点进行判断,以提高联网速度。
2.基于点的构网算法
假设绘图区域中有离散点若干,划分在n个栅格内,每个栅格内的点数分别为N i,我们可以从第一个栅格中的第一点开始联网。首先搜索出该点所在栅格以及相邻栅格内的所有点,组成一组数据,从该组数据中找出距离该点最近的点构成第一条基边,然后从这条基边开始以逆时针或顺时针环形扩展三角形。
如图1所示的一组数据,B即是距离
A点最近的点,若以逆时针环形扩展三角形,则位于A B边右侧的点应被排除,这一点我们可以通过两向量的向量积来判别:
A B
—→
=(x B-x A)i+(y B-y A)j
A P
—→
=(x P-x A)i+(y P-y A)j
A B
—→
×A P
—→
=∃・k
其中,
∃=(x B-x A)(y P-y A)-(y B-y A)(x P-x A)
图1
显然,
∃>0 P 点位于直线A B 左侧
=0 P 点位于直线A B 上
<0 P 点位于直线A B 右侧
式中,(x A ,
y A ),(x B ,y B ),(x P ,y P )分别为A ,B ,P 三
点的数学坐标。
我们知道三点构成D elaunay 三角形的充要条件是过这三点的外接圆内不含有离散点集合中除这三点之外的任何其他点,判别三点是否满足D elaunay 三角形条件的算法有多种,这里不再详细讨论。将上述数组中的其余离散点分别用两向量的向量积进行判断,在所有满足∃>0的点中,找出满足D elaunay 三角形条件的第三
点,构成第一个三角形。
如图2(a )所示,若找到基边A B 左侧一点C 满足
D elaunay 三角形条件,然后以A C 为基边逆时针扩展三
角形,若找到其左侧D 点满足条件
,再以A D 为基边扩展,如此推进至重新回到第一条基边A B 为止,这样就形成了以A 点为中心,由多个三角形组成的一个封闭的环形网状结构;A 点联网结束后,再从第一个栅格的第二点开始联网,一直到这个栅格内的点全部完成联网;然后从第二个栅格开始,搜索该栅格及相邻栅格内的所有点组成一组数据,由该栅格中的第一点开始联网,直至最后一点,就这样依次到所有栅格内的离散点都联网完毕。
图2
这里需要说明的是:当某点从第一条基边开始逆时针环形扩展三角形至某边,用D elaunay 法判别其左侧所有点却没能形成有效的三角形,或者其左侧根本就再没有其他点时,则表明此点即为绘图区域的边界点,这时应重新回到该点的第一条基边反向环形扩展三角形,直到不能再形成有效的三角形为止,将反向扩展的三角形进行逆排序,再把两次联结的三角网合二为一,同样可形成以该点为中心,由多个三角形组成的非闭合的扇形网状结构(如图2(b )中G 点)。
依据上述的原理和方法,基于点的构网算法的程序设计流程如图3所示。
三、等值线追踪方案设计
1.环形网上等值点平面位置的确定
由于每个离散点联网后,都形成一个以它自身为中心,闭合或非闭合的环形网状结构,就单个三角形而言,被以其端点为中心点的3个环形网共联结了3次,而单就每条边来说,则被相互之间部分重叠的4个环形网共连接了4次(边界边共连接了3次),然而内插等值点却都是在这一条条边上进行的,因此,必须作出某种约定,以保证等值点的内插和等值线的追踪得以顺利完成。在环形网状结构中,我们把与中心点相连的边称为这个环
形网的“径边”,而把不与中心点相连的边称为环形网的“界边”。只有当等值线通过环形网,并且连续穿过两条
以及两条以上相邻的径边时,我们才在这个环形网的径边上计算等值点的平面位置,这样就可以确保每个等值点最多只会被内插两次,而不会出现不必要的重复,因为每条边只会成为两个环形网的径边,且这两个环形网必定是由连接这条边的两个端点联成的。
要确定环形网的径边上是否有等值线通过,可以用一个简单的式子来加以判断。设等高线的高程值为Z ,环形网径边两端点的高程分别为Z 1、Z 2,则其判别式为:
∃=(Z -Z 1)(Z -Z 2)
只有当∃≤0时,该径边上才有等高线通过;否则,就没有等高线通过。当判别式∃=0时,说明等高线正好通过环形网径边的端点,为了便于处理,在精度允许的范围内将端点的高程加上一个微小值,使其值不等于Z 。
这样,在等值线追踪方案设计中就可不必考虑等值线恰好通过离散点本身这种情况。
在确定了环形网中至少有两条相邻的径边上存在等值点后,就可用线性插值法求得其等值点的坐标,线性内插的公式很简单,不再赘述。然而,每个离散点联网后形成的这种环形网状结构,使我们很容易在径边的两
图3
计算机自动联网流程图
否
是
是
是
是
否
否否
否
是
是
否
J =J +1I =I +1
结束
I =n ?
J =N i ?
输出环形网
三角网逆排序、合二为一
形成有效三角形否组成新基边
环形网是否闭合反向形成有效三角形否组成新基边
以Delaunay 法判别数组中位于基边右侧的点
以Delaunay 法判别数组中位于基边左侧的点
是否反向环形扩展三角形
找出数组中距离J 点最近的点
构成第一条基边
FOR
J =1
T O N
i
搜索I 号栅格及相邻栅格内的所有点,形成数据组
FOR
I =1
T O n
输入离散数据点,删除其中的
重复点,并建立栅格索引
开始
个端点间,采用曲线来拟合地形的垂直剖面线,实现等值点的非线性内插。首先,可在径边两端点间的垂直剖
B CD E FG 是以A 为中心点的环形网,A ′是径边A
C 反向延长线与界边E F 的交点,在界边E F 上内插出A ′的高程值,取
A ′A C 垂直剖面线上对应的三点a ′
,a ,c ,建立顶点位于中间点的抛物线,以此计算A 点处的斜率。同样,C 点处的斜率可在以C 为中心点的环形网中算出
图4
面线上,简易建立一个抛物线方程来计算每个端点处的斜率(如图4所示)。显然,如果两端点导数已知,那么对于每条径边两端点间的垂直剖面线,就有四个条件,即通过两端点,且两端点处的导数为已知值。从而可以唯一确定一个次数不大于三次的多项式曲线,这条曲线相对来说就比较符合天然地形垂直剖面线的实际情况,并且拟合曲线在这条径边所在的区间上,对应介于两端点之间的高程值,只有唯一一组解。
2.等值线追踪方案设计
为了能将内插的等值点顺序追踪排列,绘出等值线,还必须找出相互重叠的环形网内所计算的等值点间的平面位置关系。因每个环形网都是由多个三角形组成
的,我们先简单分析一下单个三角形中存在等值点的情况。由于不必考虑等值线穿过端点,如果一个三角形的边上存在等值点的话,只可能在某两条边上存在等值点,而不可能三条边上同时都有。也就是说,只要三角形一边上存在等值点,则其余的两条边中必有一边存在等
值点。
根据上面的约定,我们再研究等值线穿过任一环形网中两条及两条以上相邻的径边时,可能出现的几种情形:
①等值线不通过环形网的界边。在这个环形网中,必然所有的径边上都存在等值点,如果这个环形网由非边界点联结而成,内插的等值点就可顺序连接为一条闭合曲线(图5(a ));若此环形网由边界点联成,那么这些等值点则连成一条开口曲线(图5(b ))。
②等值线通过环形网的界边,且次数不超过两次。这是最常见的一种情形,如图5(c )、5(d )所示。相邻径边上内插的等值点顺序排列,点数至少为两个,其起点为环形网的入口点,终点为环形网的出口点。
③等值线四次通过环形网的界边。环形网中内插的等值点分为两部分顺序排列,每个部分都包括一个入口点和一个出口点,
这个网所在的位置应该是地形的鞍部
(如图5(e )所示)
。
图5
由于离散点环形联网是沿同一方向(逆时针)进行的,环形网中相邻径边上内插的等值点所排列的顺序,也相应围绕中心点位逆时针旋转。从对图形的分析中,我们还注意到,如果等值点不是位于边界上的话,那么一个环形网的入口点,必然是另一个环形网的入口点;一个环形网的出口点,也必然是另一个环形网的出口点;而内插入口点(或出口点)的径边的两个端点,就是联结这两个环形网的中心点。利用这个原理,我们就可以成功地设计出等值线的追踪方案,且在追踪等值线时,只需将各环形网中内插的等值点进行单向比较,即入口点对入口点比较,出口点对出口点比较。
联网结束后,凡是没能联成闭合环形网的离散点,即为绘图区域的边界点,而在两个边界点连接的边上内插的等值点,就是开曲线的线头。找到线头后,根据上述原理,就可顺序追踪出各条开曲线的全部等值点。对于闭曲线来说,任一环形网中内插等值点中的起点都可作为线头,按上述方法追踪,直至又回到该点为止。等值线追踪完成后,即可进行曲线的光滑输出。目前,等值线光滑的数学方法有多种,其中以张力样条函数法和斜轴抛物线法效果较好。
四、结束语
基于点的构网算法,采用栅格索引法来组织数据,逐点联网只需对该离散点所在栅格以及相邻栅格内的点进行判断,这比对绘图区域内的所有离散点进行判断要快得多,同时对于一次参与构网的点数也可放
宽。若将离散点位的分布理想化,即所联结的环形网全部由正三角形组成,则一个离散点(非边界点)就可联结六个三角形,而每个三角形又都被联结了三次,也就是说每个离散点一次环形联网,平均可形成两个三角形。而传统的三角形法逐边扩展,因为重复和交叉的缘故,一次搜索还不一定能形成一个有效的三角形,单从这一点上来说,改进后的基于点的构网算法,和传统的三角形构网算法相比,联网速度有了显著提高。若绘图区域内高程点位分布均匀,则每个离散点联网所用时间大致相等,其速度不会随着已经形成环形网数量的增加而减慢。如果我们将环形网打散,按某种的规律输出三角形的话,同样可以形成互不重复和交叉的三角息。然而,在新的网形结构下,追踪等值点只需进行单向比较,并且每追踪成功一次可增加一个或一个以上的等值点,这比传统的追踪算法速度明显加快。至于非线性内插等值点,笔者曾经做了有益的尝试,也取得了满意的效果。
参考文献
[1]刘岳,梁启章.专题地图制图自动化.北京:测绘出版
社,1981
[2]潘正风,杨德麟,黄全义,罗年学.大比例尺数字测
图.北京:测绘出版社,1996
[3]王来生,鞠时光,郭铁雄等.大比例尺地形图机助绘
图算法及程序.北京:测绘出版社,1993
[4]同济大学数学教研室.高等数学.北京:高等教育出
版社,1988下载本文
