﻿ 不规则三角网数字水深模型缓冲面快速构建的滚动球加速优化算法
 文章快速检索 高级检索

1. 海军大连舰艇学院军事海洋与测绘系, 辽宁 大连 116018;
2. 海军大连舰艇学院海洋测绘工程军队重点实验室, 辽宁 大连 116018

TIN_DDM buffer surface construction algorithm based on rolling ball acceleration optimization model
DONG Jian1,2, ZHANG Zhiheng1,2, PENG Rencan1,2, LI Gaixiao1,2, WANG Mo1,2
1. Department of Military Oceanography and Hydrography & Cartography, Dalian Naval Academy, Dalian 116018, China;
2. Key Laboratory of Hydrographic Surveying and Mapping of PLA, Dalian Naval Academy, Dalian 116018, China
Abstract: In view of the fact that the TIN_DDM buffer surface existing in the construction and application of special data type and algorithm efficiency and precision are not matching, the paper applied the rolling ball model in the process of TIN_DDM buffer surface construction. Based on the precision limitation analysis of rolling ball model, the overall precision control method of rolling ball model has been established. Considering the efficiency requirement in TIN_DDM buffer surface construction, the influence principle of key sampling points and rolling ball radius to TIN_DDM buffer surface construction efficiency has been elaborated, and the rule of identifying key sampling points has also been designed. Afterwards, by erecting the numerical relationship between key sampling points and rolling ball radius, a TIN_DDM buffer surface construction algorithm based on rolling ball acceleration optimization model has been brought forward. The time complexity of the algorithm is O(n). The experiments show that the algorithm could realize the TIN_DDM buffer surface construction with high efficiency, and the algorithm precision is controlled within 2σ.
Key words: TIN_DDM    rolling ball model    buffer surface construction    algorithm precision    algorithm efficiency

1 滚动球模型在TIN_DDM缓冲面构建中的应用扩展及局限性分析 1.1 基于TIN_DDM的滚动球模型构建

(1)

1.2 滚动球模型在TIN_DDM缓冲面构建中的精度局限性分析

 图 1 TIN_DDM矢量缓冲面构建过程中的模型精度分析 Fig. 1 The situation of model precision analysis during the construction of TIN_DDM vector butter surface

(2)

(3)

 图 2 TIN_DDM矢量缓冲面三角网格化过程中的模型精度分析 Fig. 2 The situation of model precision analysis during the triangulation of TIN_DDM vector butter surface

(4)

(5)

(6)

1.3 滚动球模型在TIN_DDM缓冲面构建中的效率局限性分析

2 面向TIN_DDM缓冲面构建的滚动球加速优化模型 2.1 TIN_DDM缓冲面构建关键采样点判定准则及步骤

 图 3 TIN_DDM缓冲面构建关键采样点 Fig. 3 The situation of the key point during TIN_DDM butter surface construction

(1) 以r为滚动球半径，依次构建TIN_DDM中各水深采样点Qi的等距离球面。

(2) 判断各个等距离球面是否在水深采样点Qiz轴方向上形成极大(小)值。

(3) 以形成极大(小)值的等距离球面所对应的球心采样点标记为采样点Qi的上(下)缓冲面点所对应的TIN_DDM上(下)缓冲面构建关键采样点。

2.2 TIN_DDM缓冲面构建关键采样点与滚动球半径的数值关联性分析

 图 4 TIN_DDM缓冲面构建关键采样点与滚动球半径的数值关联性分析 Fig. 4 The situation of numerical correlation analysis between the key point during TIN_DDM butter surface construction and the roll radius

(7)

(8)

 图 5 TIN_DDM缓冲面构建关键采样点与滚动球半径的数值关联性数据链 Fig. 5 The situation of numerical correlation data link between the key point during TIN_DDM butter surface construction and the roll radius

3 试验结果与分析

 表面类型 空间三角网 5 m等深线图 原始海底地形表面 r=500 m的上缓冲面(算法Ⅰ或算法Ⅱ) r=1000 m的上缓冲面(算法Ⅰ或算法Ⅱ) r=1500 m的上缓冲面(算法Ⅰ或算法Ⅱ) 注：地图中相关要素及数值均为虚构。 r=2000 m的上缓冲面(算法Ⅰ或算法Ⅱ) r=2500 m的上缓冲面(算法Ⅰ或算法Ⅱ) r=3000 m的上缓冲面(算法Ⅰ或算法Ⅱ) r=500 m的下缓冲面(算法Ⅰ或算法Ⅱ) 注：地图中相关要素及数值均为虚构。 r=1000 m的下缓冲面(算法Ⅰ或算法Ⅱ) r=1500 m的下缓冲面(算法Ⅰ或算法Ⅱ) r=2000 m的下缓冲面(算法Ⅰ或算法Ⅱ) r=2500 m的下缓冲面(算法Ⅰ或算法Ⅱ) 注：地图中相关要素及数值均为虚构。 r=3000 m的下缓冲面(算法Ⅰ或算法Ⅱ) 注：地图中相关要素及数值均为虚构。

 m 缓冲半径 检查点最大差值 检查点最小差值 对比精度值 500 1.985 0.853 1.943 1000 1.904 0.647 1.541 1500 1.754 0.497 1.296 2000 1.423 0.308 1.107 2500 1.221 0.168 1.003 3000 1.096 0.086 0.788

 图 6 各算法耗时统计图 Fig. 6 The time loss of each algorithm

4 结论

﻿

 [1] 李志林, 朱庆. 数字高程模型[M]. 2版. 武汉: 武汉大学出版社, 2003: 78-91. LI Zhilin, ZHU Qing. Digital elevation model[M]. 2nd ed. Wuhan: Wuhan University Press, 2003: 78-91. [2] 张立华, 贾帅东, 元建胜, 等. 一种基于不确定度的水深控浅方法[J]. 测绘学报, 2012, 41(2): 184–190. ZHANG Lihua, JIA Shuaidong, YUAN Jiansheng, et al. A method for controlling shoal-bias based on uncertainty[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(2): 184–190. [3] PORATHE T. 3-D nautical charts and safe navigation[D]. Eskilstuna: Malardalen University, 2006: 4-6. [4] 田峰敏, 徐定杰, 赵玉新. 一种建立海底格网数字高程模型的插值方法[J]. 中国航海, 2009, 32(3): 61–65. TIAN Fengmin, XU Dingjie, ZHAO Yuxin. An interpolation method for constructing undersea grid DEM[J]. Navigation of China, 2009, 32(3): 61–65. DOI:10.3969/j.issn.1000-4653.2009.03.014 [5] 张立华, 贾帅东, 吴超, 等. 顾及不确定度的数字水深模型内插方法[J]. 测绘学报, 2011, 40(3): 359–365. ZHANG Lihua, JIA Shuaidong, WU Chao, et al. A method for interpolating digital depth model considering uncertainty[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(3): 359–365. [6] 田峰敏, 赵玉新, 李磊, 等. 由矢量电子海图构建海底TIN DEM方法研究[J]. 哈尔滨工程大学学报, 2009, 30(2): 143–147, 153. TIAN Fengmin, ZHAO Yuxin, LI Lei, et al. A method of constructing undersea TIN DEM based on vector nautical chart[J]. Journal of Harbin Engineering University, 2009, 30(2): 143–147, 153. [7] 彭认灿, 王家耀. 基于地球椭球体的缓冲区构建技术研究[J]. 测绘学报, 2002, 31(3): 270–273. PENG Rencan, WANG Jiayao. A research on creating buffer on the earth ellipsoid[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(3): 270–273. DOI:10.3321/j.issn:1001-1595.2002.03.017 [8] 朱熀, 艾廷华, 王洪. 基于条带扫描思想的线目标缓冲区快速构建[J]. 测绘学报, 2006, 35(2): 171–176. ZHU Huang, AI Tinghua, WANG Hong. The buffer construction of line object based on the geometric scan idea[J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(2): 171–176. DOI:10.3321/j.issn:1001-1595.2006.02.015 [9] 吴华意, 龚健雅, 李德仁. 缓冲曲线和边约束三角网辅助的缓冲区生成算法[J]. 测绘学报, 1999, 28(4): 355–359. WU Huayi, GONG Jianya, LI Deren. Buffer curve and buffer generation algorithm in aid of edge-constrained triangle network[J]. Acta Geodaetica et Cartographica Sinica, 1999, 28(4): 355–359. DOI:10.3321/j.issn:1001-1595.1999.04.015 [10] 李芳玉, 潘懋, 朱雷. 三维缓冲体生成栅格算法研究[J]. 计算机辅助设计与图形学学报, 2005, 17(9): 1928–1932. LI Fangyu, PAN Mao, ZHU Lei. Research on the algorithm for 3D raster buffer-generation[J]. Journal of Computer-Aided Design & Computer Graphics, 2005, 17(9): 1928–1932. DOI:10.3321/j.issn:1003-9775.2005.09.006 [11] 董箭, 彭认灿, 郑义东, 等. 基于滚动球模型的单值曲面缓冲体边界生成算法[J]. 计算机辅助设计与图形学学报, 2013, 25(7): 996–1004. DONG Jian, PENG Rencan, ZHENG Yidong, et al. An algorithm of 3D-buffer boundary generation for singular value surface based on rolling ball model[J]. Journal of Computer-Aided Design & Computer Graphics, 2013, 25(7): 996–1004. DOI:10.3969/j.issn.1003-9775.2013.07.009 [12] 卢新明, 王红娟. 基于高效布尔运算的三维矢量缓冲区算法[J]. 中国矿业大学学报, 2012, 41(3): 481–487. LU Xinming, WANG Hongjuan. An algorithm for 3D vector buffer based on efficient Boolean operation[J]. Journal of China University of Mining & Technology, 2012, 41(3): 481–487. [13] 李楠, 肖克炎, 阴江宁, 等. 表面模型缓冲区分析方法[J]. 计算机辅助设计与图形学学报, 2015, 27(9): 1625–1636. LI Nan, XIAO Keyan, YIN Jiangning, et al. A method of 3D buffer analysis of boundary representation[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(9): 1625–1636. DOI:10.3969/j.issn.1003-9775.2015.09.005 [14] 徐能雄, 何满潮. 褶皱岩体三维可视化构模技术及其工程应用[J]. 岩土工程学报, 2003, 25(4): 418–421. XU Nengxiong, HE Manchao. 3D visual modeling technique of folded rock-mass and its engineering application[J]. Chinese Journal of Geotechnical Engineering, 2003, 25(4): 418–421. DOI:10.3321/j.issn:1000-4548.2003.04.007 [15] 董箭, 彭认灿, 郑义东. 三维完全欧氏距离变换的改进算法[J]. 海洋测绘, 2013, 33(1): 5–8. DONG Jian, PEN Rencan, ZHENG Yidong. Improved algorithm of complete three-dimensional Euclidean distance transform[J]. Hydrographic Surveying and Charting, 2013, 33(1): 5–8. DOI:10.3969/j.issn.1671-3044.2013.01.002 [16] 毋河海. 关于GIS缓冲区的建立问题[J]. 武汉测绘科技大学学报, 1997, 22(4): 358–366. WU Hehai. Problem of buffer zone construction in GIS[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1997, 22(4): 358–366. DOI:10.3321/j.issn:1671-8860.1997.04.013 [17] 董箭, 彭认灿, 张立华, 等. 滚动球变换的数字水深模型多尺度表达[J]. 地球信息科学学报, 2012, 14(6): 704–711. DONG Jian, PENG Rencan, ZHANG Lihua, et al. Multi-scale representation of digital depth model based on rolling ball transform[J]. Journal of Geo-Information Science, 2012, 14(6): 704–711. [18] 艾廷华, 成建国. 对空间数据多尺度表达有关问题的思考[J]. 武汉大学学报(信息科学版), 2005, 30(5): 377–382. AI Tinghua, CHENG Jianguo. Key issues of multi-scale representation of spatial data[J]. Geomatics and Information Science of Wuhan University, 2005, 30(5): 377–382. [19] 杨族桥, 郭庆胜, 牛冀平, 等. DEM多尺度表达与地形结构线提取研究[J]. 测绘学报, 2005, 34(2): 134–137. YANG Zuqiao, GUO Qingsheng, NIU Jiping, et al. A study on multi-scale DEM representation and topographic feature line extraction[J]. Acta Geodaetica et Cartographica Sinica, 2005, 34(2): 134–137. DOI:10.3321/j.issn:1001-1595.2005.02.008 [20] SAITO T, TORIWAKI J I. New algorithms for Euclidean distance transformation of an n-dimensional digitized picture with applications[J]. Pattern Recognition, 1994, 27(11): 1551–1565. DOI:10.1016/0031-3203(94)90133-3 [21] MAURER C R, RAGHAVAN V, QI R S. A linear time algorithm for computing the Euclidean distance transform in arbitrary dimensions[C]//INSANA M F, LEAHY R M. Lecture Notes in Computer Science: 2082. Berlin: Springer, 2001: 358-364. [22] 诸葛婴, 田捷, 王蔚洪. 三维欧氏距离变换的一种新方法[J]. 软件学报, 2001, 12(3): 383–389. ZHU Geying, TIAN Jie, WANG Weihong. A new method of three-dimensional Euclidean distance transform[J]. Journal of Software, 2001, 12(3): 383–389. [23] 李芳玉. 基于栅格的三维GIS缓冲体分析研究[J]. 计算机工程, 2007, 33(21): 6–8. LI Fangyu. Research on raster-based buffer analysis in 3D GIS[J]. Computer Engineering, 2007, 33(21): 6–8. DOI:10.3969/j.issn.1000-3428.2007.21.003 [24] 董箭, 彭认灿, 郑义东, 等. 局部动态最优Voronoi图的NNI算法及其在格网数字水深模型中的应用[J]. 测绘学报, 2013, 42(3): 284–289, 303. DONG Jian, PENG Rencan, ZHENG Yidong, et al. An algorithm of natural neighbor interpolation based on local dynamic optimal Voronoi diagram and its application in grid digital depth model[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(3): 284–289, 303. [25] 董箭, 彭认灿, 郑义东. 利用局部动态最优Delaunay三角网改进逐点内插算法[J]. 武汉大学学报(信息科学版), 2013, 38(5): 613–617. DONG Jian, PENG Rencan, ZHENG Yidong. An improved algorithm of point-by-point interpolation by using local dynamic optimal Delaunay triangulation network[J]. Geomatics and Information Science of Wuhan University, 2013, 38(5): 613–617.
http://dx.doi.org/10.11947/j.AGCS.2019.20180455

0

#### 文章信息

DONG Jian, ZHANG Zhiheng, PENG Rencan, LI Gaixiao, WANG Mo

TIN_DDM buffer surface construction algorithm based on rolling ball acceleration optimization model

Acta Geodaetica et Cartographica Sinica, 2019, 48(5): 654-667
http://dx.doi.org/10.11947/j.AGCS.2019.20180455