基于图模型的多边形自动构建算法

Polygon Auto-construction Algorithm Based on Graph Model

为了克服线拓扑造区效率低的问题,根据图模型中有向闭合环的特点,提出了一种基于图模型的鲁棒性较强的多边形构建方案.该方案首先将线数据构成图模型,并对图模型进行预处理;然后根据图模型生成环,再依据有向环的构成方向,判断有效环是洞还是壳;最后,把生成的洞分配给其对应的壳.壳的个数即为生成多边形的个数.该算法可较好地解决大规模线性数据生成区的效率问题,同时用其与混合模型,要素模型和简单要素模型进行了比较,实验中采用了四叉树索引和R树索引,都具有较高的效率,其中四叉树索引在实验中对于93664大小的线数据生成区数据,比要素模型快了5.400 s,比简单要素模型快了3.641 s.实验结果说明该算法性能优于其他的同类算法.

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＇.