不规则三角网数字水深模型缓冲面快速构建的滚动球加速优化算法
|
摘要
针对TIN_DDM缓冲面构建与应用中存在的数据类型特殊、算法效率与模型精度不匹配的问题,本文将滚动球模型应用扩展至TIN_DDM缓冲面的构建过程。在分析滚动球模型构建精度局限的基础上,建立了滚动球半径关联的滚动球模型整体精度控制方法;结合大数据量TIN_DDM缓冲面多次构建的应用效率需求,阐明了关键采样点与滚动球半径对TIN_DDM缓冲面构建效率的影响规律;设计了TIN_DDM缓冲面构建关键采样点的判定准则,建立了关键采样点与滚动球半径的数值关联关系;提出了一种基于滚动球加速优化模型的TIN_DDM缓冲面快速构建算法,算法时间复杂度为O(n)。试验结果表明:本文算法可实现任意缓冲半径条件下TIN_DDM缓冲面的多次快速构建,且算法精度控制在2σ内。
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σ.
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σ.
引文
[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.
[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.
[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.
[9] 吴华意,龚健雅,李德仁.缓冲曲线和边约束三角网辅助的缓冲区生成算法[J].测绘学报,1999,28(4):355-359.DOI:10.3321/j.issn:1001-1595.1999.04.015.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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[9] 吴华意,龚健雅,李德仁.缓冲曲线和边约束三角网辅助的缓冲区生成算法[J].测绘学报,1999,28(4):355-359.DOI:10.3321/j.issn:1001-1595.1999.04.015.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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.