节点文献

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

A Hybridized Method for Building Delaunay Triangulation

  • 推荐 CAJ下载
  • PDF下载
  • 不支持迅雷等下载工具,请取消加速工具后下载。

【作者】 武晓波王世新肖春生

【Author】 WU Xiao\|bo,\ WANG Shi\|xin,\ XIAO Chun\|sheng (Institute of Remote Sensing Applications, Chinese Academy of Sciences,\ Beijing\ 100101, China)

【机构】 中国科学院遥感应用研究所!北京100101

【摘要】 经过20 多年的研究,自动生成Delaunay 三角网的算法已趋于成熟。它们基本上可分为分治算法、逐点插入法、三角网生长法等3 类。其中前两类较第3 类在应用上更加广泛。但即使这两类算法也分别存在着时间和空间效率上的缺陷,使它们的应用受到了一定的限制。提出了一个融以上两类算法优点于一体,兼顾空间与时间性能的合成算法。经测试,它的运算效率大大高于逐点插入法,在大多数情况下,也高于分治算法,在分割阈值约为总数据量的十分之一时,效率最高。

【Abstract】 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.

【基金】 “九五”国家攻关!“95759 国土资源环境和区域经济信息系统及空间信息基础设施关键技术研究”
  • 【文献出处】 遥感学报 ,JOURNAL OF REMOTE SENSING , 编辑部邮箱 ,2000年01期
  • 【分类号】O241
  • 【被引频次】133
  • 【下载频次】736
节点文献中: