计算机科学 ›› 2020, Vol. 47 ›› Issue (11): 137-141.doi: 10.11896/jsjkx.191100051
陈士杰, 张森林, 刘妹琴, 郑荣濠
CHEN Shi-jie, ZHANG Sen-lin, LIU Mei-qin, ZHENG Rong-hao
摘要: 在对水下地形进行三维表面重建时,常用的方法是将点云数据投影到二维平面,用Delaunay三角剖分算法生成三角形格网,然后结合水深高程值还原到三维空间中。但是此方法效率较低,同时在投影时舍去了水深高程值信息,在三维空间内易生成狭长三角形,不利于地形地貌的三维展示效果。因此在采用逐点插入法的基础上,对其中的插入点定位和局部优化过程分别进行了改进,提出了一种融合定位算法,计算三角形矢量面积后,找到搜索前进方向并进行定位,保证了定位路径的唯一性且提高了效率;同时在局部优化过程中引入了水深高程值,计算三维空间内三角形的角度标准差,并将其作为与正三角形相似程度的衡量标准,替换空外接圆准则,使得三维空间内的网格更加均匀化。实验结果表明,该方法在水下地形三维重建的模型质量和构建效率上均优于传统的Delaunay三角剖分算法。
中图分类号:
[1] FAN M,SUN Y,XING Z,et al.Seafloor high precision terrain reconstruction based on multi-source water depth data fusion [J].Journal of Oceanography,2017,39(1):130-137. [2] ZHAI J S,ZHANG C,LI Z X,et al.The representation and calculation of the complexity of submarine topography [J].Journal of China Ocean University (Natural Science Edition),2019,49(S1):143-147. [3] HU J X,PAN N,MA Z T,et al.Research on the algorithm of constructing Delaunay triangulation digital terrain model efficiently [J].Journal of Peking University (Natural Science Edition),2003,39(5):736-741. [4] XU J Z,MA L Z.An improved algorithm for incremental insertion of Delaunay triangulation [J].Computer Engineering,2008(17):254-256. [5] KONG D W.Triangulation and 3D reconstruction of point cloud data [J].Journal of Southwest Normal University (Natural Science Edition),2019,44(7):87-92. [6] JIA J H,HUANG M,LIU X L.Surface reconstruction algorithm based on three-dimensional Delaney triangulation [J].Journal of Surveying and Mapping,2018,47(2):281-290. [7] YUAN Q L,WU X Q.3D surface reconstruction algorithm combining Delaunay triangulation method and search ball strategy [J].Journal of Graphics,2018,39(2):278-286. [8] YU J,LV P,ZHENG C W,et al.Comparative study on the construction methods of Delaunay triangulation network [J].Chin-ese Journal of Image Graphics,2010,15(8):1158-1167. [9] LAWSON C L.Generation of a triangular grid with application to contour plotting[M].California:Jet Propulsion Laboratory,Pasadena,1972. [10] CHEN M J,FANG Y M,LI G Z,et al.An improved generation algorithm of Delaunay triangulation network[J].Journal of Kunming University of Science and Technology (Natural Science Edition),2016(5):33-38. [11] LIU S H,WU D S,LUO X L,et al.Research on fast positioning algorithm of point target in Delaunay triangle network [J].Surveying and Mapping Science,2007,32(2):69-70. [12] ZOU Y G,ZHANG T.Improved Delaunay triang- ulation algorithm in plane domain [J].Computer Engin Eering and Application,2013,49(20):171-174. |
[1] | 华茂,余世明. 一种改进的混沌伊藤算法求解车辆配送问题 Modified Chaotic ITO Algorithm to Vehicle Routing Problem 计算机科学, 2016, 43(3): 266-270. https://doi.org/10.11896/j.issn.1002-137X.2016.03.049 |
[2] | . 约束三角剖分研究 计算机科学, 2008, 35(8): 6-9. |
[3] | 贺一 刘光远 雷开友 贺三 邱玉辉. 多层前向神经网络的自适应禁忌搜索训练 计算机科学, 2005, 32(6): 118-120. |
|