第13卷　第2期2000年4月

文章编号:100127372(2000)0220031206

中　国　公　路　学　报

ChinaJournalofHighwayandTransport

Vol113　No12Apr.2000

三角网数字地面模型快速构建算法研究

刘学军,符锌砂,赵建三

(长沙交通学院路桥系,湖南长沙　410076)

摘　要:系统地研究了三角网数字地面模型TIN构建中的几个关键问题,提出了动态创建和维护三角形拓扑关系的方法,建立了快速确定点在三角形中的算法原理及空外接圆判断法则的简易表达式,所设计的逐点插入算法有着较高的执行效率,算法复杂度与点数几乎成线性关系。关键词:数字地面模型;三角不规则网;算法;拓扑关系中图分类号:U41216　　　文献标识码:A

AStudyofalgorithmforfastcontriangulation(LIUXue2jun,2san

(DepartmentofHighwayandBonsUniversity,Changsha410076,China)

Abstract:Thisproceduresthatholduptheefficiencyofconstructing

triangulatiTIN).AwayandalgorithmfordynamicallyrenewingthetopologicalrelationsinTpresented.ThepaperalsostudiesthewayoffindingtrianglethatcontainagivenpointinTINandtheformulaofemptycircum2circletest.TheincrementalinsertionalgorithmofconstructingTIN,hasatimecomplexitythatisaboutlineartothenumberofpointsset.

Keywords:digitalterrainmodel(DTM);topologicalrelation

triangulationirregularnet(TIN);algorithm;

　　三角网数字地面模型(TriangulationIrregularNet简写为TIN)作为地表(地貌和地物)的数字化表现手段和分析工具,以其几何结构良好、数据结构简单、地表重构精度高及对不规则区域和数据点分布密度适应能力强等特点,并在地学领域如公(铁)路勘测设计一体化、地理信息系统等得到了广泛的应用。其核心技术—散点的三角剖分算法,近十几年来一直是众多学者研究和关注的焦点。迄今为止出现了不少成熟算法,如以BOWYER和GREEN等人为代表的Voronoi图法[9,11]、SHAMES及HOEY的分割—合并算法[1,4]、LAWSON的逐点插入算

[9]法[2,3]、WATSON的空外接圆算法及GREEN和

[10,11]

等。其中较有代表SIBSON的三角网生成算法

性的是LAWSON的逐点插入算法和WATSON的空外接圆算法。

编程易LAWSON的逐点插入算法原理简单、实现。研究结果表明[6],逐点插入算法占用内存资源较少,但时间复杂度差。SHANES和HOEY已证明[4],对N个数据点建立Delaunay三角剖分网,至少需0(NlgN)的时间。笔者对逐点插入算法进行了详细的研究,分析了该算法中效率的制约因素,提出了动态建立和更新三角网拓扑关系的算法,建立了快速三角形定位方法原理及运行次数更少的空外接圆判断公式。基于本文原理所编制的逐点插入算

收稿日期:1999207206

基金项目:交通部“九五”科技攻关项目(95205201207)

作者简介:刘学军(19652),男,陕西合阳人,长沙交通学院副教授,工学博士研究生.