Three-Dimensional Cost Distance Algorithm For Voxel Space And Its Application

Three-dimensional geographic information system(GIS)develops rapidly.Extending the common spatial analysis functions in two-dimensional GIS to threedimensional GIS and studying the spatial analysis algorithms suitable for true threedimension can enhance the spatial analysis capability of three-dimensional GIS and,thus,can promote the application of three-dimensional GIS.Cost distance analysis is an important spatial analysis function in GIS,which can integrate a variety of geographic information for analyzing the movement problems in the geographic space and guiding the plan and rational utilization of resources.However,existing related research mainly focuses on the improvement and applications of raster cost distance algorithm while research on three-dimensional cost distance analysis is still rare.Compared with the raster cost distance analysis,three-dimensional cost distance analysis need not be limited to a certain cost surface and can take three-dimensional spatial information into consideration to solve the true three-dimensional geographic problems.Therefore,a method for improving the accuracy of conventional raster cost distance algorithm is firstly proposed in two-dimension and then extended to threedimensional space.Three-dimensional cost distance algorithm specially for voxel space is proposed and an efficient data structure is designed to achieve a better calculation efficiency.The effectiveness and utility of the proposed algorithm have been verified via several practical applications.The main work and conclusions of this paper involve the following aspects:(1)A method for improving the accuracy of raster cost distance analysis.According to the problem of overestimating the cost distance in the conventional raster cost distance algorithm,propagation rules of moving in the cost raster are proposed to simulate the refraction,blockage,and rectilinear propagation of wave,which can break through the limitation of raster data structure on the movement direction and step size.The improved cost distance algorithm combined with propagation rules is verified using two typical kinds of cost raster data.The experimental results show that,comparing with conventional cost distance algorithm,extended neighborhood approach,and smoothing in the post-processing method,the improved algorithm can generate more accurate and reasonable results,which eliminates the unnecessary bends along the distorted travel path in the raster and reduces the overestimated cost distance to the target.(2)Three-dimensional cost distance algorithm for voxel space.Firstly,voxel model is used to represent the cost space and a corresponding weighted network is established based on the neighbor relationship among voxels.Then,a line rasterization algorithm for voxels is adopted to implement the propagation rules of moving in the voxel space.Combining the propagation rules with Dijkstra’s algorithm,the threedimensional cost distance algorithm is proposed to calculate the cost distance from every voxel to its nearest source.A comparison between the proposed algorithm and the unmodified cost distance algorithm(i.e.,simply extending the conventional raster cost distance algorithm to voxel space)is made.The results show that,in a homogeneous friction space,the error of unmodified algorithm is much larger in 3D than its counterpart in 2D while the proposed algorithm can calculate the accurate 3D cost distance.In a heterogeneous friction space,the proposed algorithm generates smaller cost distance than that generated by the unmodified algorithm and benefits more in a friction space with lower heterogeneity.(3)An efficient data structure for speeding up the addition,removal,and search of nodes.After analyzing the time-consuming operations in the proposed algorithm,a minimum heap,which enables the rapid addition and removal of nodes,is used to manage the nodes in the active voxel list.A hash table is adopted in order to help quickly search for nodes in the heap.The results show that,compared to the linked list,the proposed data structure(i.e.,a heap combined with a hash table)can improve the efficiency of the algorithm significantly and becomes more beneficial as the number of voxels increases.(4)Practical applications of three-dimensional cost distance analysis.The utility of the three-dimensional cost distance algorithm for voxel space is verified via three applications,including planning shortest drone delivery path and extracting service coverage of distribution centers in an urban environment,using cost distance to generate three-dimensional viewshed based on Digital Elevation Model(DEM),and calculating the minimum hydraulic resistance in a heterogeneous three-dimensional hydraulic conductivity field by three-dimensional cost distance analysis.The results show that,compared with the unmodified algorithm,the proposed three-dimensional cost distance algorithm can better meet the demands of applications that need to save cost or require higher calculation accuracy.