Polygon Auto-construction Algorithm Based on Graph Model

To conquer the low efficiency of topological establishment problem,according to the characteristics of graph model with directed rings,propose a robust polygon construction algorithm here.Firstly,this algorithm makes the lines data into graph and preprocesses the graph model;Then,form rings according to graph model,and judge if the valid ring is hole or shell based on the direction of forming the directed rings.At last,assign the holes to the corresponding shells.The number of shells is the number of polygons.This algorithm can solve large-scale lines data forming polygons' effective problem,at the same time,compare with mixed model,element model and simple element model.in this algorithm we adopt quadrant tree index and R tree index which have high effective.Quadrant index in experiment is 5.400 s faster than element model,and 3.641 s faster than simple element model when dispose the same data(namely,with the 93664 quantity of line data to form polygon data).Experiment result shows this algorithm' effecting is better than others'.