三角网数字地面模型快速构建算法研究_刘学军(2)

　32　　　　　　　　　　　　　　　中　国　公　路　学　报　　　　　　　　　　　　　　2000年法程序,有着较高的执行效率。借助于Windows的文件映射技术,能一次性处理上千万个点。试验结果表明,时间复杂度与数据量基本成线性关系。

1　逐点插入算法介绍及分析

逐点插入法基本思想是:在一已存在的三角网中插入一点,该点与其所在的三角形三顶点形成新的三个三角形,然后用对角线交换法来优化新形成的三角形,从而保证所建三角网为Delaunay三角网。

逐点插入算法的基本步骤为:

(1)建立包含所有数据点的初始多边形,该多边形可为一个正三角形或两个直角三角形组成的矩形。

(2)从数据域中取出一点P,做如下工作:①找出包括点P的三角形T,设T的三顶点为V1、V2、V3;②P与T三顶点相连,形成三个新的三角形T1、T2、T3;

③对所有新形成的三角形,化。

(3)LOP局部算法(LocalOptimizationProcedureLOP)保证了所生成的三角形为Delaunay三角形。它利用了Delaunay三角形的空

图2　LOP优化过程

形数与点数的关系为:三角形数=边界点数+2×内点数-2)。无论是建立格网索引还是全局搜索,基于点在多边形中判断的过程是一个很费时的过程。该问题也是TIN数模应用中经常碰到的问题。112　LOP局部优化过程(拓扑更新)

LOP局部优化过程是基于具有公共边的两个

三角形进行的,LOP时,要快速,虽说可以通过拓,但由于逐点插入算,因而如何在动态过程中创建和,直接影响到算法的执行效率。113　数值计算问题

对每一次LOP过程都需要进行空外接圆检测,该过程在整个算法过程中的执行频率极高,故空外接圆检测方法的好坏对程序效率影响很大。空外接圆检测过程是一个数值分析与计算过程,因而应在计算稳定可靠的前提下,尽量减少计算次数和较费时的函数计算,从而提高执行效率。

外接圆特性,即一个三角形为Delaunay三角形,该三角形外接圆中不含有其余任何数据点(图1)。方法为:对个有公共边的两个三角形组成的四边形进行判断,如果其中一个三角形的外接圆中包含有另一三角形除公顶点外的第三顶点,则交换公共边,图2表示了该过程

。

[1]

2　点在三角形中查找(定位问题)

在三角剖分和应用中,经常碰到的问题是定位一个点在哪个三角形中,一般做法是扫描整个或局部三角形网格,利用点在多边形中原理判断计算。当三角形数目较大时,这是一个很费时的过程,如果建立了三角形网络的拓扑关系,则可利用三角形面积坐标和拓扑关系来解决这一问题。211　三角形面积坐标

如图3所示,三角形△V1V2V3的三顶点坐标为V1(x1,y1)、V2(x2,y2)、V3(x3,y3),任给点为P(x,

图1　Delaunay三角形空外接圆特性

y),按有限元理论,P在三角形△V1V2V

3

内的面积

(1)

对上述算法的研究分析可知,影响算法执行效率主要有以下几个因素:

111　点在三角形中的查找(定位问题)

坐标L1、L2、L3定义为

L1=A1 A;L2=A2 A;L3=A3 A

式中:A为△V1V2V

3

面积;A1、A2、A

3

分别为

算法中每插入一点,首先要定位该点在哪个三

角形中,随着点数增加,三角形数量成倍增加(

三角

△V2V3P、△V3V1P、△V1V2P的面积。

面积坐标(L1、L2、L3)与直角坐标的关系为