TIN_DDM Buffer Surface Construction Algorithm Based on Rolling Ball Acceleration Optimization Model

doi:10.11947/j.JGGS.2020.0309

Abstract

Abstract:

In view of the TIN_DDM buffer surface existing in the construction and application of special data type, 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 of 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 with in 2σ.

Key words: TIN_DDM; rolling ball model; buffer surface construction; algorithm precision; algorithm efficiency

Jian DONG, Zhiheng ZHANG, Rencan PENG, Gaixiao LI, Mo WANG. TIN_DDM Buffer Surface Construction Algorithm Based on Rolling Ball Acceleration Optimization Model[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(3): 88-103.

Figures/Tables 11

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Tab.1

Tab.2

Fig.9

References 25

[1]	LI Zhilin, ZHU Qing. Digital elevation model[M]. 2nd ed. Wuhan: Wuhan University Press, 2003: 78-91.
[2]	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]	TIAN Fengmin, XU Dingjie, ZHAO Yuxin . An interpolation method for constructing undersea grid DEM[J]. Navigation of China, 2009,32(3):61-65.
[5]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	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]	LI Fangyu . Research on raster-based buffer analysis in 3D GIS[J]. Computer Engineering, 2007,33(21):6-8.
[24]	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]	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.

Surface type	Delaunay triangular network	Bathymetric contour of 5m
Original seabed topography
Upper buffer surface with r=500m (algorithm I or algorithm Ⅱ)
Upper buffer surface with r=1000m (algorithm I or algorithm Ⅱ)
Upper buffer surface with r=1500m (algorithm I or algorithm Ⅱ)
Upper buffer surface with r=2000m (algorithm I or algorithm Ⅱ)
Upper buffer surface with r=2500m (algorithm I or algorithm Ⅱ)
Upper buffer surface with r=3000m (algorithm I or algorithm Ⅱ)
Lower buffer surface with r=500m (algorithm I or algorithm Ⅱ)
Lower buffer surface with r=1000m (algorithm I or algorithm Ⅱ)
Lower buffer surface with r=1500m (algorithm I or algorithm Ⅱ)
Lower buffer surface with r=2000m (algorithm I or algorithm Ⅱ)
Lower buffer surface with r=2500m (algorithm I or algorithm Ⅱ)
Lower buffer surface with r=3000m (algorithm I or algorithm Ⅱ)
Footnote:relevant elements and values in this map are fictitious.

Buffer radius	Maximum difference of checkpoints	Minimum difference of checkpoints	Contrast precision
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