生成Delaunay三角网的改进算法  

An Improved Algorithm for Building Delaunay Triangulation

作　　者：贺全兵[1] 黎贵友[2] 文进[3] 杨萌[1] 

机构地区：[1]西南石油学院,成都610500 [2]重庆邮电学院,重庆400065 [3]中石油西南油气田分公司,成都610051

出　　处：《计算机与数字工程》2006年第5期50-52,64,共4页Computer & Digital Engineering

摘　　要：算法以原“改进的自连接Delaunay三角网生成算法[1]”为基础。其主要方法仍是三角网生长法[2],但同时采用了逐点插入法中的凸壳。在原封闭点的基础上提出了封闭的边界点的概念,并增加了对边界点和边界边的识别和处理,从而进一步提高了构网效率。另外,采用的用边的法向量对边的某侧的点进行判断[4]的方法也简单实用。This algorithm is based on the original paper of ＂An Improved Algorithm for Auto Connected Delaunay Trianglation＂ In this paper, the main method we take is triangulation growth still, but also adopt Convex- Frame in incremental insertion method. We propose the notion of dosed - border - point on the base of dosed - paint, and also improve the way of recognizing and handling to border - point and border- edge （because border- edge can build triangulation only once）. For this, it enhances efficiency of building triangulation. Additional, the way in this paper to determine which side of an edge points in using edge＇s normal is very simple and practicality.

关 键 词：DELAUNAY三角网 封闭点 封闭的边界点 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]