Research On Parallel Algorithm Of Cost Distance For Complex Geometric Features In Obstacle Space

As the basic of spatial measurement, distance is the start of various measurements that defined in geographical space, and it is also the basic of geographic analysis. Much information can be achieved by distance analysis, especially by cost distance analysis, to guide the plan and use of resource. They are also widely used in ecological protection, landscape pattern planning. It is more suitable when cost distance is used in obstacle space, and it is of obviously scientific and technological significance.As cost distance analysis based on raster data refers to large quantities of data and computation, Chinese and foreign scholars have carried out comprehensive and elaborate researches in this region, and a lot of feasible algorithms were proposed and tending perfect and maturity. But these algorithms are optimized and improved based on serial algorithms. With the development of parallel computation technology and multi-core platform, we can use the multi-thread parallel program to improve the traditional serial algorithm, to improve the efficiency of cost distance analysis.Cost distance analysis calculates the least accumulative cost of each raster cell to its nearest source. A spread algorithm is adopted commonly, which building the node-link model by using the Queen pattern, and then calculate the least accumulative cost value based on the theory of Dijkstra. When meeting the barriers, we can align the barriers'cell with a maximum value to let the distance spread avoid the barriers. But it is found that the distance can find a shortcut to pass the cracks of barriers sometimes, so that affects the analysis results. The traditional solutions are buffering or filling the barriers, but they may also affect the calculation accuracy. An algorithm of cracks identification was proposed in this article, which can make the distance spreading avoid the cracks, and not affects the analysis result. To solve the problem of complicated geometric source features, this article proposed a method that extracting the cells round the features to reduce the computation.This article improved the traditional serial cost distance analysis algorithm by the method of data decomposition, and the algorithms of crack identification and complicated geometric feature processing were mixed in. Technology of Windows thread API and C++ language were used to carry out the algorithm, and a spatial accessibility analysis of public landscape was taken by example of Nanshan, Shenzhen, to analyze the feasibility and practicality. Three groups of tests were taken to test the performance of the algorithm.Test result shows that, (1) this algorithm can do the cost distance analysis rapidly, and it can avoid the barrier cracks in obstacle space, which is more useful than the traditional algorithms. (2) This parallel algorithm performs well in case of big raster and multiple sources, especially when it is supported by the multi-core platform and multi-thread technology.