Integral ear elimination and virtual point-based updating algorithms for constrained Delaunay TIN

作     者：WU LiXin1,2,WANG YanBing2,3 & SHI WenZhong2,4 1 Institute for Geo-informatics & Digital Mine Research,Northeastern University,Shenyang 110004,China 2 Institute for GIS/RS/GPS & Subsidence Engineering Research,China University of Mining & Technology,Beijing 100085,China 3 Laboratory of 3D Information Acquisition & Application,Capital Normal University,Beijing 100037,China 4 Center for Advanced GIS Research,LSGI,Polytechnic University Hong Kong,Hong Kong,China 

作者机构：Northeastern Univ Inst Geoinformat & Digital Mine Res Shenyang 110004 Peoples R China China Univ Mining & Technol Inst GIS RS GPS & Subsidence Engn Res Beijing 100085 Peoples R China Capital Normal Univ Lab Informat Acquisit & Applicat Beijing 100037 Peoples R China Hong Kong Polytech Univ LSGI Ctr Adv GIS Res Hong Kong Hong Kong Peoples R China 

出 版 物：《Science China(Technological Sciences)》 (中国科学（技术科学英文版）)

年 卷 期：2008年第51卷第S1期

页      面：135-144页

核心收录：

学科分类：081603[工学-地图制图学与地理信息工程] 081802[工学-地球探测与信息技术] 07[理学] 08[工学] 070503[理学-地图学与地理信息系统] 0818[工学-地质资源与地质工程] 0705[理学-地理学] 0816[工学-测绘科学与技术] 

基　　金：the National Natural Science Funds of China for Outstanding Youth (Grant No. 50525414) the National Natural Science Foundation of China (Grant Nos.10172090, 40771171) the National Hi-Tech Research and Development Program of China (Grant No. 2006AA12Z216) Science Development Plan Awarded by Beijing Municipal Commission of Education Science (Grant No. KM200710028014) 

主　　题：Delaunay TIN spatial constraint data updating spatial modeling polymorphism digital mine 

摘      要：Constrained Delaunay Triangular Irregular Networks (CD-TIN),a kind of special data structure,have many practical applications in Geoinformatics,especially in the representation of linear constrained triangulation for DTM and DSM,such as in digital city and digital mine. Past researches on D-TIN mainly focused on point in-sertion and deletion without consideration of constraint,and that on CD-TIN usu-ally paid more attention to the insertion algorithms for points and edges,but little to the deletion algorithms. The presented algorithms are far insufficient for the dy-namic updating of CD-TIN. In this paper,the constraint edge in CD-TIN is consid-ered to be any set of broken lines,i.e.,polygon edges,broken lines and simple segments. The constraint edge may be composed of one or more constraint seg-ments,and it is allowed to be in any form: Open or close,intersection or self-in-tersection. By improving to present insertion and deletion algorithms for D-TIN,two new algorithms for CD-TIN updating are presented. According to the polymorphism of the constraints in CD-TIN,virtual point is adopted to represent the crossing node between constraint edges when a constraint edge is inserted in CD-TIN. Two new algorithms named as Integral Ear Elimination (IEE) and Influence Domain Retrian-gulation for Virtual Point (IDRVP) are presented,the former is for constraint point deletion,while the later is for the insertion and deletion of constraint edge. The principle of IDRVP is that to divide the influence domain of a virtual point into some parts by the constraint-keeping edges,and to retriangulate each part of the influ-ence domain individually referring to the constraint visible property and constraint empty circle (CEC) criterion. Finally,a prototype system is developed with VC++,one case on the integration of 3D terrain and buildings is demonstrated to test the correctness of new algorithms. It shows that the new algorithms are effective for the updating of CD-TIN.