Research On The Self-adaptive Algorithm For Geometric Division Of Planar Region

Geometric division of planar region is widely used in many fields.The process of geometric division of planar region is the process of automatic construction of single polygon.There are two traditional algorithms for polygon automatic construction,the one is based on vector graphics,and the other one is based on raster image.The first algorithm's output data is accurate,but it is not possible to extract the boundaries of a single polygon in a short time,especially in data change operations.The second algorithm takes less time,but it will make data quality problems in vector rasterization part,and the output data is not accurate enough.Combing the vector with the advantages of the raster,we propose an algorithm for geometric division of planar region based on vector and raster interblended.The main research contents include the following points.1.Establishment of geometric division algorithm.Based on the idea of vector and raster combination,we will get the boundary line of polygon by the area boundary formed in the grid filling,which will reduce the range of line search.Then use the line segment to construct the polygon.Automatically generate polygons by using vector method and raster method to maintain data accuracy and reduce the range of line search.2.Adaptive improvement for geometric division algorithm.In order to extend the application of the algorithm,there are numbers of special cases of data: tiny polygons,"dead zone" polygons and continuous multi-island polygons.Special treatments will done to adaptively deal with the common polygon and the polygon with island,as well as the local individual polygons constructing and the global geometric division of planar region.3.Parallel acceleration for geometric division algorithm.In order to speed up the calculation of the algorithm,the "block drive" strategy will be adopted.In order to improve the time efficiency,geometric division of planar region uses the block division process.Doing geometric division for sub-block first,and then doing polygon seamless contiguity by the partition table that set up in segmentation.CPU will be used to speed up the parallel between blocks.We will detect the correctness and adaptability of the algorithm through multiple sets of experiments,and analyze the execution time at last.