构建 Delaunay 三角网的一种新型生长法——壳外插入法

摘要：

基于逐点插入法中影响域的概念,提出一种新的三角网生长算法——壳外插入法.该算法以三角网外围的凸包生长为基础,通过查找生长边、内蚀既有网、重构三角网3个基本操作,达到既有网在保持Delaunay特性的同时纳入新点,从而实现三角网的生长.该算法克服了传统生长法需要查找第3点的缺陷,也避免了逐点内插法大量三角形定位的操作,因而算法的平均复杂度达到O(NlogN).使用了大量的随机散点数据和常吉高速的实测地形点数据对算法进行测试,证实该算法快速有效.

关键词：三角剖分、Delaunay三角网、生长法、数字地面模型

所属期刊栏目：4

分类号：U412(道路工程)

资助基金：交通部西部交通建设科技项目2003-318-802-01;湖南省交通建设科技项目2006-8

在线出版日期：2008-05-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：67-72