基于图的任意域内点集的Delaunay三角剖分算法  

A GRAPH BASED ALGORITHM FOR GENERATING THE DELAUNAY TRIANGULATION OF A POINT SET WITHIN AN ARBITRARY 2D DOMAIN

作　　者：潘志庚[1] 马小虎[1] 董军[1] 石教英[1] 

机构地区：[1]浙江大学CAD&CG国家重点实验室

出　　处：《软件学报》1996年第11期656-661,共6页Journal of Software

基　　金：国家自然科学基金

摘　　要：本文提出了一种基于图的二维任意域内点集的Ｄｅｌａｕｎａｙ三角剖分算法．该算法首先求出任意域内点集的约束最小生成树，然后逐次加入一边构造三角形网格，最后通过局部优化变换，得到二维任意域内点集的Ｄｅｌａｕｎａｙ三角剖分．A graph based algorithm for generating the delaunay triangulation of a point set within an arbitrary 2D domain (denoted as DTAD for short) is presented in this paper. The basic idea is to calculate the CMST(constrained minimum spanning tree) of the given points within an arbitrary 2D domain. The CMST is then augmented to triangle mesh. Finally the DTAD is obtained by local optimal transformation. The actual application of the algorithm in the automatic finite element mesh generation is also shown in the paper.

关 键 词：任意域 三角剖分 DT 计算机图形学 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]