基于分治算法构建Delaunay三角网的研究  

Study on Divide-and-conquer Algorithm of Generating Delaunay Triangulation

作　　者：蒋红斐[1] 

机构地区：[1]中南大学土木建筑学院,长沙410075

出　　处：《计算机工程与应用》2003年第16期81-82,117,共3页Computer Engineering and Applications

基　　金：铁道部资助项目(编号:97G23-F)

摘　　要：提出了一种构建Delaunay三角网的分治算法,该算法利用方格网管理离散点数据,仅需分别对每格中的点进行排序;此外,通过对凸包顶点数据进行分区管理,在搜寻凸包支撑线时,能预先确定出支撑点的范围,减少了搜索工作量,提高了三角网的合并速度。A divide-and-conquer algorithm to build Delaunay triangulation is presented,it uses square grids to manage disoedered points so that sorting of the disordered points only be done in grid.Moreover,the algorithm utilize subarea to control the vertices of convex hull so that the range which support points locate in can be predefined when searching support lines,the work of searching support points can be reduced and the speed of merging two triangulations is raised.

关 键 词：分治算法 凸包 DELAUNAY三角网 

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