1、矢量地图图幅裁剪技术研究罗胜 郭海涛 张保明111（1 信息工程大学测绘学院遥感信息工程系 郑州市陇海中路 66 号， 450052）摘要：本文针对矢量地图的图幅裁剪要求，讨论了目前矢量地图图幅裁剪的原理和方法，并提出了一种图幅裁剪的通用算法，适应于对矢量数据中的点、线和面数据的裁剪。实验表明，该算法运行快速，可靠性高。关键词：矢量地图 图幅裁剪 节点 线段所谓图幅裁剪就是将地图图廓线以外的矢量数据信息舍弃。对于矢量地图的图幅裁剪在 GIS 或其它相关应用中非常常见。在图幅裁剪中用到的二维图形的多边形窗口裁剪技术，是计算机图形学中的一项重要技术，目前对该类算法的研究也比较多，如 Cyrus 和
2、 Berk 提出的 CyrusBerk 算法 等。但是在进行1矢量地图图幅裁剪的时候，如对面数据的裁剪，此类算法通常不能适应裁剪要求，需进一步研究。本文针对矢量地图图幅裁剪的特点，重点描述了其裁剪的原理和方法，并对涉及的点和线段裁剪算法做了具体的描述，最后给出了裁剪实例。1. 矢量地图的图幅裁剪原理和方法矢量地图数据是以军标格式存储的，由十八个地物要素层构成，每个要素层分别有一个坐标文件和一个属性文件 。矢量数据的裁剪与普通的图形裁剪2有所不同，在裁剪操作时不仅仅需要考虑到坐标信息，同时也要保留矢量地图数据的属性信息。矢量数据的坐标信息是以点、线和面的方式分类存储的，所以也可以说对矢量数据的裁
3、剪也就是对点、线和面的裁剪。1.1 矢量地图点的裁剪矢量地图中的点分两种：无向点和有向点。对于无向点来说，对它的裁剪相对来说比较容易，只要判断出该无向点的坐标是否在裁剪窗口内部即可。对于有向点，它是由一个定位点和方向点构成。对它的裁剪，首先判断它的定位点是否在裁剪窗口之内，如果定位点不在窗口之内，则认为有向点在裁剪窗口之外；如果定位点和有向点都在窗口之内则判断在裁剪窗口之内。如定位点在裁剪窗口之内，而方向点在窗口之外，需求出线段与裁剪窗口的交点，把它作为新的方向点并存储。1.2 矢量地图线的裁剪对于线和裁剪窗口的相交情况总体上可分成两种，一种是线被裁剪窗口分成了一条新的线，另一种就是线被裁剪窗
4、口截断成多条线段，如图 1：L1L21 2 3 4 56P11 7 8 P2P3P692345 6 78 9 10P4P5图 1 线段与裁剪窗口相交位置概略图图 1 中线 L1 被裁剪窗口裁剪成了一条新的线。对该线的裁剪只要求出线段的进入裁剪窗口的入口点 P1 及出裁剪窗口的出口点 P2 即可，然后保存 P1 与P2 之间的节点，组成新的线并赋原线的属性值并保存。对于线 L2，被裁剪成两条线或两条以上的线，对它的裁剪过程如下：1 判断该线的首点是否在裁剪窗口内，如在，计算出线的出口点，保存首点与出口点之间的节点，并赋原线的属性作为新的线存储；2 如当前点不在窗口内，求其入口点，如 P3。如果当
5、前线直到最后一个节点都在窗口内，则保存入口点和其后的所有节点，作为新的线并赋属性保存，此时当前线裁剪完毕；如果有节点出窗口，则求出其出口点（如 P4），保存入口点（如 P3）和出口点（如 P4）之间的节点作为新的线并赋属性保存；3 当前点为出口点的后一个节点，计算后面的节点有无入口点，如无则当前线处理完毕；如有入口点（如 P5），则进入步骤 2；4 直到最后一个节点判断完毕，则当前线全部裁剪完成。1.3 矢量地图面的裁剪面裁剪的情况与线裁剪相比，不同之处是多了面域点的生成和面的强制闭合。如图 2 所示：1P223D1 D2D34567P1P2P3P4P5P68SS图 2 矢量地图面数据的裁剪示
6、意图图 2 中，面 S 的边线被裁剪窗口分成多条线段，最后裁剪完毕生成的面为S，其裁剪操作步骤如下：1 如果当前面 S 中当前处理的节点在裁剪窗口内，判断其后的所有节点是否在裁剪窗口内，如是则保存所有节点作为新的面的顶点，当前面也裁D4剪完毕；如否求出出口点并保存其间的节点作为新的面的顶点，转入步骤 3；2 如当前面的当前处理节点不在窗口内，求出后面节点的入口点，如无，则当前面全在裁剪窗口之外，退出裁剪操作；如有，求出入口点（如图2 中的 P1），转入步骤 1；3 判断前面裁剪中的出口点（如 P2）之后的节点，如全在窗口外，则根据面域点与刚才保存的线段（如 P1P2）的相对位置关系选择强制闭合
7、线，如图 2，如果面域点在线段 P1P2 的上面，则选择 P1P2 上半部分的裁剪窗口顶点作为强制线的顶点，反之取下半部分的顶点，此时当前面裁剪完毕；如当前节点后仍有入口点，求出入口点（如 P3），转入步骤 4；4 如前出口点与当前入口点（如 P2 与 P3）间不经过裁剪窗口的顶点，则保存此入口点到刚才保存的新面数据中，转入步骤 1；如其间经过裁剪窗口的顶点，如 P4 与 P5，则根据 P4 和 P5 之间的节点 5、6 与线段 P4 P5 的相对关系（位于相对上方或下方，图 2 中为下方）确定强制闭合线的顶点（图 2 中为 D2），保存裁剪窗口的顶点与当前入口点作为强制闭合线保存到新的面数据
8、中，转入步骤 1；5 当前面的所有节点都裁剪完毕，构成新的面节点（如图 2，新的面节点为 P1-2-P2-P3-4-P4-D2-P5-7-P6-P1）。计算所有节点构成的新多边形的几何中心坐标，作为新生成的面数据的面域点，赋原面的属性并保存，当前面裁剪完毕。2. 图幅裁剪的算法及实现2.1建立矢量地图数据链表在进行图幅裁剪之前，需要读取矢量地图的数据。为了简化算法，我们在本算法中定义了一个既包含坐标数据又包含属性数据的链表，将矢量数据以统一的格式存储到链表中。链表定义如下：class ARC int flag; /标志，判断是点、线或者面long Standardattrib; /编码，判断当
9、前链是什么地物属性int rect4; /当前链表的外接矩形MAttribute *attribute;/当前链表对应的属性指针，记录了当前链的所有属性int num; /当前链表的总节点数struct POINT *point; /当前链的节点结构体，包括节点的横、纵坐标及前后指针ARC *next; /当前链的下一个链指针ARC *pre; /当前链的上一个链指针其中 flag 代表当前链是点、线或者是面，在裁剪的时候根据 flag 值判断当前链是何种属性，以区别普通的线属性与面属性数据的裁剪。2.2图幅裁剪的具体算法矢量地图图幅裁剪具体过程中，涉及到的最基本操作就是对节点或由两节点构成的
10、线段的裁剪，其算法直接决定整个图幅裁剪的速度和效率，所以在本节中我们具体讨论一下他们的算法。2.2.1 节点裁剪算法对于矢量数据的图幅裁剪来说，其裁剪窗口一般为凸多边形，所以本算法是一种基于凸多边形窗口的算法，对线段裁剪也是如此。如图 3 所示，裁剪窗口为多边形 P1P2P3P4P5，对于任意一个节点 P,作过点 P 的水平线和垂线，计算其与裁剪窗口的交点 1（x1，y1）、2（x2，y2）、3（x3，y3）、4（x4，y4），如节点 P 的横坐标 Px 在 x1 和 x2 之间且纵坐标 Py 在 y1 和 y2 之间，则 P 在窗口内；如否，则节点在窗口之外，如节点 P。P2P1P4P3P5
11、PP561 24图 3 节点裁剪示意图根据上述原理，它的算法流程图如图 4 所示：开始结束节点在外接矩形之外节点在内接矩形之内依次求出过节点的水平线与垂线和裁剪窗口的交点节点是否位于各交点之间NNY ， 返回 T R U EY ， 返回 F A L S EY ， 返回 T R U EN ， 返回 F A L S E图 4 节点裁剪算法流程图2.2.2 线段裁剪算法如图 5 所示（A 为线段首点，B 为末点），本文把线段与裁剪窗口的位置关系概括分成六种，其中虚方框表示的是裁剪窗口的外接矩形。3BP(a) (b) (c)A A CD(d) (e) (f)图 5 线段与裁剪窗口的位置关系图如果当前线
12、段的两个节点都在裁剪窗口的外接矩形之外，则当前线段在裁剪窗口外，如图 5（a）；如当前线段的两个节点都在裁剪窗口内，则整个线段在窗口内，如图 5（b）所示；对于当前线段的两个节点分别在窗口内外的情况，如图 5（c）,则计算线段与裁剪窗口各个边的交点，必能算出一个交点 P，保存交点和裁剪窗口内的节点构成新的线段（PB）并保存；如果线段与窗口的位置都不属于上面几种，则此时两个节点均在裁剪窗口之外，需要判断线段 AB 与 A 点和裁剪窗口顶点之间连线的位置关系，本文采用计算斜率的方法。设节点 A 与裁剪窗口各顶点连线的斜率为 ，求出最大和最ik小斜率 ，如果线段 AB 的斜率 或 则线段 AB 在裁
13、剪窗口maxink和 maxABkinAB外，如图 5（d）；反之如果 ，则线段 AB 可能与裁剪窗口有交点，min此时需要计算线段 AB 与裁剪窗口边线的交点，如不存在，则当前线段在裁剪窗口之外，如图 5（e），如存在，则必有两个交点，如图 5（f），保存两交点作为新的线段并保存。其算法流程图如图 6 所示：BBA开始线段是否位于裁剪窗口外接矩形之外N求出线段一个节点与裁剪窗口其它顶点连线的斜率 k iY求线段与裁剪窗口边线之间的交点线段的斜率 k 大小是否位于 k i 之间Y是否有两交点N结束YN两个交点构成新的线段并保存N当前线段两节点是否全在裁剪窗口内Y ， 保存图 6 线段裁剪算法流
14、程图2.2.3 矢量地图图幅裁剪总算法结合以上的算法，我们给出矢量地图图幅裁剪的总的算法流程描述：1读入数据链表；2判断当前链表的外接矩形与裁剪窗口的外接矩形和内接矩形的位置关系。如在外接矩形之外，则此链不在裁剪窗口内，进行下一条链操作；如在内接矩形之内，则此链必在裁剪窗口内，保存当前链表，并跳入下一条链表进行操作。否则，执行步骤 3；3判断当前链表的属性，如为点数据，则进行点的裁剪处理；4如当前链表为线数据，则进行线的裁剪处理；5如当前链表为面数据，计算裁剪过后生成的新的面数据顶点，并给出新生成面的面域点，保存并进入下一条链表的裁剪；6判断链表是否全部裁剪完毕，如否转入步骤 2；1. 实验和
15、总结根据以上算法，在主频 P2.6G 内存 512M 的微机上，以一幅 1:5 万的矢量地图为基础，裁剪了一副 1:1 万矢量地图，以及一幅自由图幅，如图 7 所示。(a) (b)(c) (d)图 7 矢量地图图幅裁剪实例图图 7 中(a)为 1:5 万的矢量地图，四边形窗口为 1:1 万图幅图廓在 1:5 图幅中的位置，图 7(b)为裁剪后的效果图。图 7 中(c)为 1:5 万矢量地图，其中的裁剪窗口为任意给的凸多边形，图 7(d)为裁剪后的效果图。两个裁剪过程的相关信息如表 1 所示：裁剪窗口裁剪的总链表数裁剪的线段数裁剪后的链表数 裁剪用时（毫秒）标准 1:1 万图幅 16，619 6
16、0，218 1，967 2，547自由图幅 12，235 53，247 1，106 2，037表 1 裁剪实例中的相关信息表由实验结果可知，本算法能很好的适用于标准的图幅裁剪和凸多边形的自由图幅裁剪，且运算速度和裁剪结果都比较令人满意。参考文献1 Cyrus M，Beck J，Generalized twodimensional clippingJComputer and Graphics，1978，3(1)：23282 1:5 万矢量地形图数据生产记录格式. 中国人民解放军总参谋部作战部测绘局3 李伟青. 凸多边形窗口线裁剪的折半查找算法. 计算机辅助设计与图形学学报，2005，Vol.l7
17、 No.5:962-9654 李雪、石广田 一种新的任意四边形窗口线裁剪算法 兰州交通大学学报(自然科学版)，2005，Vol.24 No.6:90-925 孙家广. 计算机图形学M第 3 版北京,清华大学出版社，19986 基于 Epscan2.1 的地形图图幅裁剪的实现. 北京测绘,2002 No4:36-397 唐棣、单会秋. 基于直线斜率的凸多边形线裁剪算法. 计算机应用与软件. 2005,Vol.22 No.8:115-1178 武志强、杨哲海等. 基于 Visual C+平台的多边形裁剪算法实现. 测绘学院学报, 2000,Vol.17 No.4:301-304THE RESEAR
18、TH OF MAP CLIPPING ALGORITHM FOR VECTOR MAPLuo Sheng Guo HaiTao Zhang BaoMing(Institute of Surveying and Mapping,Information Engineering University,ZhengZhou,450052)Abstract: The text discusses the current theory and method of the map clipping algorithm for vector map, and puts forward a universal algorithm of map clipping. It can process the points、lines and areas in the vector data. The result of the experiment indicates that the algorithm operates quickly, and has a good reliability.Key Words: vector map map clipping node line segmenti第一作者简介：罗胜，研究生，助教，主要从事数字摄影测量，空间数据质量等研究
