计算机科学 ›› 2014, Vol. 41 ›› Issue (10): 317-320.doi: 10.11896/j.issn.1002-137X.2014.10.066
毕硕本,陈东祺,颜坚,郭忆
BI Shuo-ben,CHEN Dong-qi,YAN Jian and GUO Yi
摘要: 提出了一种基于并行二维凸壳算法的平面点集的Delaunay三角网生成算法。该算法基于颜坚等在文献[20]中提出的并行二维凸壳算法,在构建凸壳时记录被替换的边和被删除的点,形成一个初始三角网;再在初始三角网的各个三角形内部,采用逐点插入法构建局部的Delaunay三角网;最后,对各个局部Delaunay三角网的边界边进行局部优化,得到原点集的Delaunay三角网。文中给出了算法的正确性说明,实验结果也表明该算法稳定高效。
[1] Brassel K E,Reif D.A Procedure to Generate TIN Polygons[J].Geographical Analysis,1979,11(3):289-303 [2] McCullagh M J,Michael J,Ross C G.Delaunay Triangulation of a Random Data Set for its Arithmic Mapping [J].The Cartographic Journal,1980,17(2):93-99 [3] 吴佳奇,徐爱功.Delaunay三角网生长法的一种改进方法[J].测绘科学,2012,37(2):103-187 [4] Shamos M I,Hoey D.Closest-point Problems [C]∥Proceeding of the 16th Annual IEEE Symposium on Foundation of Computer Science.LosAngeles,California:IEEE,1975:151-162 [5] Lewis B A,Robinson J S.Triangulation of Planar with Applications [J].The computer Journal,1978,21(4):324-332 [6] Lee D T,Schacher B J.Two Algorithms for Constructing aDelaunay Triangulation [J].International Journal of Computer and Information Sciences,1980,9(3):219-242 [7] 谢增广.平面点集Delaunay三角剖分的分治算法[J].计算机工程与设计,2012,33(7):2652-2658 [8] 李小丽,陈花竹.基于格网划分的Delaunay三角剖分算法研究[J].计算机与数字工程,2011,39(7):57-59 [9] 刘永和,冯锦明,郭维栋,等.Delaunay三角网通用合并算子及分治算法的简化[J].中国图象图形学报,2012,17(10):1283-1291 [10] Lawson C L.Generation of a Triangular Grid with Application to Contour Plotting [C]∥Proceeding of Technical Memorandum,California institute of technology.Jet Pollution Laboratory,1972:299 [11] Johnstone J K,Sloan K R.Tensor Product Surfaces Guided by Minimal Surface Area Triangulations[C]∥Proceedings of IEEE Conference on Visualization.1995:354-361 [12] 李水乡,陈斌,赵亮.快速Delaunay逐点插入网格生成算法[J].北京大学学报:自然科学版,2007,43(3):302-306 [13] Loffier M,Snoeyink J.Delaunay Triangulation of ImprecisePoints in Linear Time after Preprocessing [J].Computational Geometry,2010,43(3):234-242 [14] Lo S H.Parallel Delaunay Triangulation in Three Dimensions [J].Computer Methods in Applied Mechanics and Engineering,2012,237(1):88-106 [15] Qi M,Cao T-t,Tan T S.Computing 2D constrained Delaunaytriangulation using the GPU [J].IEEE Transactions on Visualization and Computer Graphics,2013,9(5):736-748 [16] Nasre R,Burtscher M,Pingali K.Morph Algorithms on GPUs [C]∥Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming(PPoPP’ 13).2013:147-156 [17] 李根,邹志文,鞠时光.结合二叉树和Graham扫描技术的高效Delaunay三角网构建算法[J].计算机应用研究,2010,27(3):894-896 [18] 鲍蕊娜,李向新,麻明,等.基于凸壳技术的Delaunay三角网生成算法研究[J].科学技术与工程,2011,11(4):764-767 [19] 陈学工,黄晶晶.基于最优凸壳技术的Delaunay三角剖分算法[J].计算机工程,2007,33(17):93-95 [20] 颜坚,毕硕本,汪大,等.多核架构下计算凸壳的并行算法[J].计算机科学,2013,40(2):16-19,57 [21] Lawson C L.Software for C1 Surface Interpolation[M]∥Mathematical Software III.New York:Academic Press,1977 [22] 武晓波,王世新,肖春生.一种生成 Delaunay 三角网的合成算法[J].遥感学报,2000,4(1):32-35 |
No related articles found! |
|