一种有效的复杂多边形裁剪算法

一种有效的复杂多边形裁剪算法导引基本概念目前主流的多边形裁剪算法有Sutherland-Hodgeman算法(简称S算法)、Liang-Barsky算法、Maillot算法(简称M算法)等，它们均要求窗口多边形是矩形,而主多边形则是凸多边形，具有极大的应用局限性。本算法中主多边形和窗口多边形可以为任意形状的多边形！裁剪多边形裁剪确定图形中哪些部分落在显示区之内，哪些部分落在显示区之外,以便只显示落在显示区内的那部分图形，这个选择过程称为裁剪。将被裁剪的多边形（又称为主多边形）位于作“剪刀”的多边形（又称为窗口多边形）之外的部分裁剪掉，保留两者之间的重合区域，称为多边形裁剪。注意：多边形裁剪算法的输出应该是定义裁剪后的多边形边界的顶点序列。条件(a)裁剪前(b)错误的裁剪结果不连续的直线段(c)正确的裁剪结果基本概念多边形裁剪示意图算法原理算法原理栅格数据是一种重要的地理数据模型，它基于规则的格网单元表示地理实体，即任何复杂的地理实体均可由栅格单元“拼接”而成。考虑到裁剪问题中任意多边形的复杂性，引入栅格法的思想，即考虑将复杂的多边形（主多边形和窗口多边形）划分为形态简单的空间单元（几何单元），并以这些“基元”为空间运算对象设计算法（进行裁剪），最后将计算结果“拼接”起来获得最终的裁剪结果。如图示栅格法的缺陷：精度问题克服方法：分解为不规则的几何单元栅格法思想栅格图多边形裁剪中的栅格法思想算法原理如果是单个多边形图层可以这样扫描分解：针对多边形的所有顶点，对其纵坐标y值进行排序，然后根据y值的排序依次绘制水平扫描线，此时多边形顶点均位于扫描线上。图示扫描线思想多边形如何分解？？由于多边形裁剪中涉及到两个多边形图层,为保证所划分的条带不相互跨越,需事先计算两个图层的交点,将交点视同多边形顶点,如上方法同样地绘制扫描线。图示扫描线的作用图示顶点纵坐标y值的排序结果是Y3Y4Y5Y2Y1(Y6)Y7，按此顺序依绘制水平扫描线单个多边形的扫描线绘制两个多边形的扫描条带出现跨越两多边形的交点视同顶点同样绘制扫描线多个多边形的扫描线绘制扫描线思想引入的意义扫描线将主多边形和窗口多边形分别分割为两个梯形集合。(注意：三角形也可以看成是一种有两个点重合的特殊梯形。)从纵轴方向看,空间被分割成一条条扫描带,由多边形分割成的梯形按其纵坐标位置“镶嵌”在这些扫描带上。并且任何一个梯形都只能被限制在一条扫描带中,不会跨越多条扫描带。若主多边形与窗口多边形有重叠区域,则在某些扫描带上,主多边形生成的梯形与窗口多边形生成的梯形也会部分重叠。多边形裁剪转化成逐行检索两类梯形的“交集”,裁剪结果是分布在各扫描带上的“交梯形”的集合。1234针对多边形顶点和交点，对其纵坐标y进行排序，以此为依据建立水平扫描线，将主多边形和窗口多边形分别进行分割，得到两个梯形集合。计算主多边形与窗口多边形的交点。在各扫描带上建立“交梯形”的集合。在“交梯形”集合的基础上通过边界追踪等方法构建裁剪多边形并输出计算结果。多边形裁剪算法的步骤关键过程实现一、计算两个图层的交点两多边形图层间的交点也可借助扫描线思想获得，思路为:①分配一个坐标数组，记录主多边形与窗口多边形上所有顶点的纵坐标值，并对该数组排序。②以数组中每一个元素值作水平扫描线，分别将主多边形和窗口多边形的边打断成小线段，得到两组线段集合。③遍历扫描带，在各扫描带上用窗口多边形生成的小线段与主多边形生成的小线段两两判断是否相交，若有交点,则求出交点坐标。在第4条扫描带上拿窗口多边形生成的线段A、B分别与主多边形边生成的线段1、2作相交判断,可以得出线段B与线段2相交。二、多边形梯形化在多边形各个结点（包括顶点与交点）处作水平扫描线只是将多边形的边打断成了小线段,为正确提取出裁剪多边形,必须对多边形完成全梯形化。步骤如下：①分配一个坐标数组，记录主多边形与窗口多边形上所有结点的纵坐标值，并对该数组排序。②以数组中每一个元素值作水平扫描线，分别将主多边形和窗口多边形的边打断成小线段，得到两组线段集合。【类同前面】③对各个扫描带上的小线段从左至右两个为一组提取并作为梯形斜边构造梯形。（注意：主多边形与窗口多边形分开来看！）（1）用一个结构体来表示梯形单元,其中记录梯形的4个顶点坐标。每条扫描带上用一个有序链表来存储该带上所生成的梯形集合。则每条扫描带对应有两个有序链表，分别对应存储主多边形和窗口多边形的梯形集。（2）对每条扫描带：先固定主多边形的链表(参照链表),再拿窗口多边形链表中的梯形逐个与参照链表中的梯形集作比较,判断是否有梯形相交的情形出现，这个过程称为梯形与参照链表的“插入”操作。若待“插入”梯形与链表中的梯形不相交,舍弃该操作,否则对参照链表中的梯形执行“分裂”运算，并对“交梯形”进行标记。（3）“分裂”运算的关键是判断“插入”梯形在参照链表中的位置。在算法初期已完成多边形线段求交运算,待“插入”梯形与参照链表中梯形之间不会出现斜边交叉的情况,梯形位置的判断十分容易。具体判断方法为:计算梯形两条斜边中点的横坐标值x,参照链表中每个梯形两斜边的x按照从左至右的方式构成一个有序坐标序列;通过折半查找求出待“插入”梯形两斜边中点横坐标x在该坐标序列中的位置,从而推断出待“插入”梯形两斜边位于参照链表中的位置，并找出该梯形与链表中哪些梯形相交。三、扫描带内的梯形求交三、扫描带内的梯形求交参照链表中的灰色部分表示梯形单元,当梯形与参照链表完成“插入”操作后,该链表中将具有8个梯形单元,其中黑色部分表示“交梯形”,即主多边形所在梯形与窗口多边形所在梯形的“交集”。四、梯形单元提取与面的构建梯形求交运算后,各带参照链表中“交梯形”已生成并被标记。可遍历扫描带上的参照链表,删除链表中未被标记的梯形,最后保留“交梯形”集合。“交梯形”相互拼接生成的多边形集就是裁剪结果,但我们需要的裁剪结果并不是梯形的集合，而是构成定义裁剪后多边形的顶点序列，所以还需建立专门的边界追踪算法完成面的构建。注意：此时参照链表中应只剩下“交梯形”的集合！四、梯形单元提取与面的构建边界追踪的思路：（1）可以将梯形看作一种特殊的矩形,对每个梯形边界进行追踪时，追踪方向可以以左上、左下、右上和右下标记。（2）一般情形下,在追踪到梯形的某一斜边时,该梯形所在扫描带的上一行和下一行扫描带中必能找到两个梯形,且这两个梯形的斜边与当前追踪梯形的斜边正好相接,从而沿追踪方向很容易找到下一追踪梯形。（3）显然,只有在多边形的极值点处（梯形转化为三角形）其追踪方向才会发生改变,此时首先判断追踪梯形当前所追踪的斜边是否与其相邻的梯形斜边相接,若相接则将该梯形标记为新的追踪梯形并改变追踪方向;若无法找到符合条件的梯形,则继续追踪当前梯形的另一斜边,并改变追踪方向。总结算法的突出特点该算法借鉴了计算几何中常用的扫描线思想,将裁剪多边形进行梯形分割,将复杂多边形划分为由简单梯形构成的图元集合,根据各梯形单元的属性来判定它们是否隶属于裁剪结果,最后通过边界追踪将离散的梯形单元拼贴为完整的计算结果。与现有算法相比,该算法的特点为:采用类似于栅格的方式来组织数据,逐行存储形态简单的梯形单元,结构简单，便于实现。具有矢量算法的计算精度，可以回避多数矢量算法中存在的弧段切割重组、出入点关系判定、包含关系计算等复杂过程,算法实现相对简单。兼具栅格数据和矢量数据的优点！！！参考文献[1]张均，王鹏.一种新的矢量数据多边形的快速裁剪算法[J].中国图象图形学报，2008，13(12):2409-2413.[2]李静，王文成，吴恩华.基于凸剖分的多边形窗口线裁剪算法[J].计算机辅助设计与图形学学报，2007，19(4):425-429.[3]王结臣，沈定涛，陈焱明，等.一种有效的复杂多边形裁剪算法[J].武汉大学学报：信息科学版，2010，35(3):369-372.[4]杜月云，周子平，张云龙.一种任意多边形裁剪快速算法[J].计算机应用与软件，2009，26(6):265-267.[5]方志祥，李清泉，熊盛武.GIS矩形网格中任意多边形裁剪算法*[J].武汉理工大学学报：交通科学与工程版，2005，29(5):686-688.