Strength Feature Representation And GPU Parallelization Of Vector Polygon Overlay Computation Based On Vatti Algorithm

With the rapid development of earth observation technology,people’s ability and means to collect and obtain spatial data are increasingly enriched,and geospatial data presents exponential and explosive growth,which puts forward higher requirements for the scale and efficiency of traditional overlay analysis algorithms in processing data.Due to the computationally intensive nature of overlay analysis algorithms,more and more scholars are attempting to use GPU devices to handle high intensity computing tasks in overlay analysis algorithms to improve computational efficiency.Studying high-performance vector polygon overlay analysis algorithms for GPU parallel architectures has important theoretical and practical significance for improving the computational performance of traditional spatial analysis algorithms and improving the development level of GIS software technology.In practical applications,faced with the complex and variable geometric morphology and spatial distribution characteristics of spatial entities,the computational efficiency of different calculation processes of vector polygon overlay analysis algorithms varies significantly.Therefore,accurately measuring the impact of polygon shape features on the efficiency of overlay analysis algorithms and implementing computational strength expression models for algorithms facing multiple indicators can provide powerful guidance and valuable reference for precise optimization of algorithms and GPU parallelization transformation.The main research contents and conclusions of this article are as follows.(1)Establish a vector polygon overlay computational strength representation model based on Vatti algorithm.In this paper,from two aspects of polygon shape complexity and polygon spatial relationship,the complexity of polygons is quantitatively expressed by selecting multiple indicators,and statistical methods such as data testing,correlation analysis,and multiple linear stepwise regression analysis are used to construct a computational strength expression model for each stage of the Vatti algorithm under different operator operations,This process better reflects the impact of polygon complexity on the computational efficiency of different operator operations at different stages of the algorithm,and further explores the number of vertices that have a significant impact.This process lays the foundation for subsequent algorithm optimization and GPU parallelization transformation.(2)The data structure of the original serial Vatti algorithm is optimized.Aiming at the time-consuming process of scanning beam construction during the execution of Vatti algorithm,an optimization method called VCS(Vertex Coordinate Pre-Sorting)method for polygon boundary vertex Pre-Sorting was proposed.The original binary tree data structure of Vatti algorithm was replaced by a two-way linked list.When the number of trimmed polygon vertices reached 6553600,the algorithm’s computational efficiency under differentiation or operator operation was improved by nearly 1400 s,and its performance was improved by nearly 10%.The efficiency of searching polygon boundary vertex information is significantly improved with less additional storage space.(3)Research on GPU parallelization and optimization methods of Vatti algorithm.Based on the established Vatti algorithm computational strength expression model and data structure optimization methods,this paper applies parallel odd-even sorting,shell sorting,and bitonic sorting to the process of constructing LMT and SBT using Vatti algorithm,and further optimizes the bitonal sorting with the best performance improvement.Experiments have found that the optimized dual tone sorting has a significant optimization effect on the Vatti algorithm,achieving a maximum acceleration ratio of 2.8 times.