摘要
提出了一种构建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.
出处
《计算机工程与应用》
CSCD
北大核心
2003年第16期81-82,117,共3页
Computer Engineering and Applications
基金
铁道部资助项目(编号:97G23-F)
关键词
分治算法
凸包
DELAUNAY三角网
Divide-and-conquer algorithm,Convex hull,Delaunay triangulation
