36　　　　　　　　　　　　　　　中　国　公　路　学　报　　　　　　　　　　　　　　2000年为保证算法的稳定性,应注意当P落在三角形边上的情况,即当(△yp3△xp2-△yp2△xp3)=0时可不交换对角线。

号95205201207)有着运行速度快、对数据量无限制、整体建立地表模型的特点。参考文献:

[1]　LEEDT,SCHACHTERBJ.Twoalgorithmsforcon2

structingadelaunaytriangulation[J].242.

[2]　LAWSONCL.SoftwareforC1SurfaceInterpolation

[M].MathematicalSoftware .J.Rice,Ed.NewYork:AcademicPress,1977.161—194.

[3]　SLOANSW.Afastalgorithmforconstructingdelau2

nay

triangulation

in

theplane[J].Advanced

EngineeringSoftware,1987,9(1):34—55.

[4]　SHAMOSMI,HONYD.Closest2pointproblems[J].

Proceedingsofthe16thSymposiumontheons,1975:151—162.[,,.三角网的生成算法

Int.J.of

ComputerandInformationScience,1980,9(3):219—

5　算法分析和应用

现对上述算法原理做一简要的分析。

在LOP过程中,其主要工作是交换对角线及空外接圆检测,而在数值计算时,无论采用何种检测方法,对每一三角形而言,其运算工作量相同,因而这一过程是一常量。同时在维护拓扑关系时,动态维护算法无须进行全局或局部的三角形比较,故该过程

是一线性执行过程,其时间复杂度为0(N)。

每插入一点,其所在三角形的定位工作是比较费时的,理论上可以证明,笔者所给查找方法其平均

4

),而最坏情况为0(N2),因时间复杂度约为0(N1 而对所有点,其复杂度为0(N

5 4

),最坏为0(N2)。设

若对数据点或三角形建立了索引关系,则其时间复杂度还可减少,故可认为该部分的变化亦为常量变化。当数据量比较大时,的,即具有0(N)的复杂度。

的C++程序量,因而采用了Ws的文件映射技术调度和管理数据,即所有数据不进入内存,故比起数据在内存时,其运算要稍慢些,但依表6还是不难看出:基于上述原理的程序,其执行效率还是较高的。

表6　程序执行效率

点　　数

26030515651614771896966

J].,1999,28(1):28—35.

],,周建华.CAD软件设计[M].北京:北

京航天航空大学出版社,1996.174—183.

[7]　扬　钦,徐永安,陈其明,谭建荣.任意平面域上离散点

的三角化方法[J].软件学报,1998,9(1):241—245.

[8]　胡恩球,等.有限元网格生成方法发展综述[J].计算机

辅助设计与图形学学报,1997,9(4):378—383.

[9]　putingthen2dimensiondelaunay

tessellationwithapplicationtovoronoipolytopes[J].ComputerJournal,1981,24(2):167—172.

[10]　GREENPJ,putingdirichlettesse2

lationsintheplane[J].ComputerJournal,1978,21(2):168—173.

[11]　putingdirichlettesselations[J].Co2

mputerJournal,1981,24(2):162—166.

[12]　TSUNGPAOFANG,LESAPIEGL.Delaunaytri2

angulationusingauniformgrid[J].IEEE,ComputerGraphicsandApplication,1993,(5):34—47.

[13]　ANDREWJH,PETERLL.Onconformingdelau2

naymeshgeneration[J].AdvancesinEngineeringSoftware,1992,(14):129—135.

[14]　LARRYL.Schumaker.TriangulationinCAGD[J].

IEEE,ComputerGraphicsandApplication,1993,(1):47—52.

[15]　刘学军,符锌砂.TIN点单位算法及网形优化[J].中

三角形数

37005700582629542662893

CPU时间 s

12301261600

　　注:机型为奔腾MMX166,32M内存。

6　结　语

笔者系统地研究了逐点插入算法中的制约因素,提出了动态维护三角网拓扑关系的原理与算法。而正是在该算法维护下的三角网拓扑关系,得以保证了插点算法的线性执行效率。同时出于执行效率的要求,笔者还对在三角形拓扑关系下的三角形定位问题和数值计算问题做了探索研究,得出了有使用价值的结论。基于本文算法而研制的公路数字地

面系统HDTM(交通部九五科技攻关课题,合同编

国公路学报,1997,10(2):24—31.

[16]　符锌砂.基于航测数模的公路测设一体化系统[J].中

国公路学报,1997,10(2):31—38.

[17]　符锌砂.公路计算机辅助设计[M].北京:人民交通出

版社,1998.55—67.