一种生成Delaunay三角网的合成算法  

A Hybridized Method for Building Delaunay Triangulation

作　　者：武晓波[1] 王世新[1] 肖春生[1] 

机构地区：[1]中国科学院遥感应用研究所,北京100101

出　　处：《遥感学报》2000年第1期32-35,共4页NATIONAL REMOTE SENSING BULLETIN

基　　金：九五"国家攻关!"95759 国土资源环境和区域经济信息系统及空间信息基础设施关键技术研究

摘　　要：经过２０ 多年的研究，自动生成Ｄｅｌａｕｎａｙ 三角网的算法已趋于成熟。它们基本上可分为分治算法、逐点插入法、三角网生长法等３ 类。其中前两类较第３ 类在应用上更加广泛。但即使这两类算法也分别存在着时间和空间效率上的缺陷，使它们的应用受到了一定的限制。提出了一个融以上两类算法优点于一体，兼顾空间与时间性能的合成算法。经测试，它的运算效率大大高于逐点插入法，在大多数情况下，也高于分治算法，在分割阈值约为总数据量的十分之一时，效率最高。A wide variety of algorithms have been proposed to construct triangulation. They fall into three broad categories: divide\|and\|conquer, incremental insertion and triangulation growth. The first two groups of the methods have been extensively applied to many disciplines because of their easiness in implementation. They are, however, constrained either by their computational inefficiency or by their stringent demand on computer memory. In this paper a hybridized method is proposed to take advantage of both algorithms' strengths so that these limitations could be overcome. In a test of 2533 points, the computation efficiency of the hybridized method is much higher than that of incremental insertion method in all cases, and is also higher than that of divide\|and\|conquer method in most cases. The best efficiency is achieved when the data points are partitioned into one\|tenth of the original size.

关 键 词：DELAUNAY 三角网 合成算法 分治算法 遥感 

分 类 号：O241[理学—计算数学]