主权项 |
一种多边形矢量图层快速叠合方法,其特征在于所述方法包括:A)将两矢量图层多边形(每个多边形必须是封闭面状对象)分别存入两个链表G1和G2中,并为各图层多边形分配唯一ID号,规则为:第i个图层第j个多边形ID为i_j;同时,初始化一个结果图层R为空;B)分别从G1和G2中读取多边形,将从G1获得的每个多边形Pi与所有G2中的多边形Qi进行分析判断;直至G1为空,跳到第H步;否则将不断从G1中取得多边形P,并从G1中删除;C)如果满足下述表达式:(P外包).x2<(Qi外包).x1‖(P外包).y2<(Qi外包).y1‖(P外包).x1>(Qi外包).x2‖(P外包).y1>(Qi外包).y2,则将该多边形Qi存入多边形集合M中,否则存入多边形集合N中;D)进行多边形求交,只要多边形集合N不为空,则采用基于事件点组的平面扫描线算法对P与N进行扫描线求交点;如果N为空,则将P直接存进结果图层R中,跳回第B步;(基于事件点组的平面扫描线算法需要保护)E)然后,开始进行多边形重建:先对步骤D中基于事件点组的平面扫描线算法所求得的多边形交点进行原线段截断,产生新的节点和连通新线段的处理;并且,对连通后节点所关联的边进行夹角排序,按同一节点边的排列顺序生成边信息链表;F)再根据最小夹角原则,采用深度搜索,按逆时针方式求出所有合法多边形,包括P与N的交P∩N、P与N的差P N、N与P的差N P,并为每个新的多边形重新分配ID;G)将P∩N与P N存入结果图层R中,将N P存进集合M中,更新第二个图层G2的图形数据,用M覆盖G2,即:使得G2=M,返回步骤B;H)两图层所有多边形已经叠合完毕后,则结果多边形已经全部更新,并存于结果图层R中,接着,对R中所有多边形图形数据进行属性统计计算和配置;I)返回结果图层R,结束运算。 |