delaunay三角网生成算法的研究与实现(1)

《delaunay三角网生成算法的研究与实现(1)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果Delaunay三角网生成算法的研究与实现(1)摘要Delaunay三角网作为一种主要的数字地形模型表示法，经过二十多年来的研究，它的生成算法已趋于成熟。本文在简单回顾和评价了分割—归并法、逐点插入法、三角网生长法等三类主流算法的基础上，介绍并实现了一个融以上算法优点于一体，兼顾空间与时间性能的合成算法。关键字数字地层模型；三棱柱；Delaunay；三角网；生成算法0引言计算机图

2、形学是利用计算机研究图形的表示、生成、处理、显示的学科。经过30多年的发展，科学可视化已成为计算机图形学中最活跃的分支之一，并得到了广泛的应用。在地质领域,由于大量珍贵的地层钻探数据需要用有效的方式进行直观地表达，因而致使可视化技术成为地质研究和工程勘查领域必不可少的手段。在建模中，维的分析处理由DTM(数字地形模型)模型进行。DTM主要由栅格与TIN两种数据格式来表示[1，2]，而以后者更为重要。TIN的生成算法中，最终有三种为普遍接受和采用，它们是分割—归并法、逐点插人法和逐步生长法。本文在简要分析了上述算

3、法所有缺点的基础上，实现了一种合成算法。1Delaunay三角网生成算法回顾课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果Tsaj根据实现过程，把生成Delaunay三角网的各种算法分为三类：分治算法；逐点插入法；三角网生长法。Tsai为比较算法性能，给出了一张各种算法的时间复杂度对照表，如表1所示。表中，N为数据

4、点数。0(f(N))表示算法的时间复杂度，它以算法中频度最大的语句频度f(N)来度量。上述三类算法中，三角网生长法在80年代中期以后就很少用到，较常见的是分治算法和逐点插入法，而这两类算法又各有其长处和短处。逐点插入法虽然实现过程相对简单，所需内存较小，但它的时间复杂度高。所以从时间复杂度方面看，分治算法最好。但由于算法中存在递归，它需要较大内存空间。在普通的计算机平台上，运行速度慢和占用较大内存都是应该尽量避免的。本次设计中，我们引入并实现了一种合成算法，将逐点插入法植入到了分治算法中，互相取长补短，从而达到

5、了较好的时空性能，也很好地体现了两者的优势。表1几种Delaunay三角网生成算法的时间复杂度[3]算法一般情况最坏情况分Lewis和Robinson(1987)O(NlogN)O(N2)治Lee和Schachlter(1980)O(NlogN)O(NlogN)算Dwyer(1987)O(NloglogN)O(NlogN)法Chew(1989)O(NlogN)O(NlogN)逐Lawson(1977)O(N4/3)O(N2)点Lee和Schachlter(1980)O(N3/2)O(N2)插Bowyer(198

6、1)O(N3/2)O(N2)入Watson(1981)O(N3/2)O(N2)法SloanO(N5/4)O(N2)三Green和Sibson(1987)O(N3/2)O(N2)角课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果Brassel和REif(1979)O(N3/2)O(N2)网MaCullagh和Ross(

7、1980)O(N3/2)O(N2)生Mirante和WEIgarten(1982)O(N3/2)O(N2)成法注：表中N表示数据量2合成算法的研究与实现算法基本思想和步骤把分治算法与逐点插入法结合起来的具体做法是,以分治算法为主体,当递归分割数据集的过程进行到子集中的数据量小于一个预定值——分割阈值时终止,然后用逐点插入法在子集中生成子三角网。我们把这一新的算法称为合成算法。合成算法的基本步骤是【4】：Begin把点集V以横坐标为主，纵坐标为辅按升序排序，然后递归地执行以下步骤：ifV中数据量大于一给定值，把V

8、分为近似相等的两个子集VL和VR在VL和VR中用合成算法生成三角网；找出连接VL和VR中两个凸壳的底线和顶线；由底线至顶线合并VL和VR中两个三角网；else生成基本三角网；算法的实现主要模块基本三角网的生成模块：(1)生成凸壳过程。(2)生成初始三角网过程。(3)点插入过程。(4)局部优化过程。三角网归并模块：寻找要归并的两个相邻子三角网的上下顶线与底线。两个子三角网归并过程。涉及到