资源描述：
《一种有效的复杂多边形裁剪算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一种有效的复杂多边形裁剪算法导引基本概念目前主流的多边形裁剪算法有Sutherland-Hodgeman算法(简称S算法)、Liang-Barsky算法、Maillot算法(简称M算法)等，它们均要求窗口多边形是矩形,而主多边形则是凸多边形，具有极大的应用局限性。本算法中主多边形和窗口多边形可以为任意形状的多边形！裁剪多边形裁剪确定图形中哪些部分落在显示区之内，哪些部分落在显示区之外,以便只显示落在显示区内的那部分图形，这个选择过程称为裁剪。将被裁剪的多边形（又称为主多边形）位于作“剪刀”的多边形（又称为窗口多边形）之外的部分裁剪掉，保留两者之间的重合区域，
2、称为多边形裁剪。注意：多边形裁剪算法的输出应该是定义裁剪后的多边形边界的顶点序列。条件(a)裁剪前(b)错误的裁剪结果不连续的直线段(c)正确的裁剪结果基本概念多边形裁剪示意图算法原理算法原理栅格数据是一种重要的地理数据模型，它基于规则的格网单元表示地理实体，即任何复杂的地理实体均可由栅格单元“拼接”而成。考虑到裁剪问题中任意多边形的复杂性，引入栅格法的思想，即考虑将复杂的多边形（主多边形和窗口多边形）划分为形态简单的空间单元（几何单元），并以这些“基元”为空间运算对象设计算法（进行裁剪），最后将计算结果“拼接”起来获得最终的裁剪结果。如图示栅格法的缺陷：精
3、度问题克服方法：分解为不规则的几何单元栅格法思想栅格图多边形裁剪中的栅格法思想算法原理如果是单个多边形图层可以这样扫描分解：针对多边形的所有顶点，对其纵坐标y值进行排序，然后根据y值的排序依次绘制水平扫描线，此时多边形顶点均位于扫描线上。图示扫描线思想多边形如何分解？？由于多边形裁剪中涉及到两个多边形图层,为保证所划分的条带不相互跨越,需事先计算两个图层的交点,将交点视同多边形顶点,如上方法同样地绘制扫描线。图示扫描线的作用图示顶点纵坐标y值的排序结果是Y3Y4Y5Y2Y1(Y6)Y7，按此顺序依绘制水平扫描线单个多边形的扫描线绘制两个多边形的扫描条带出现跨
4、越两多边形的交点视同顶点同样绘制扫描线多个多边形的扫描线绘制扫描线思想引入的意义扫描线将主多边形和窗口多边形分别分割为两个梯形集合。(注意：三角形也可以看成是一种有两个点重合的特殊梯形。)从纵轴方向看,空间被分割成一条条扫描带,由多边形分割成的梯形按其纵坐标位置“镶嵌”在这些扫描带上。并且任何一个梯形都只能被限制在一条扫描带中,不会跨越多条扫描带。若主多边形与窗口多边形有重叠区域,则在某些扫描带上,主多边形生成的梯形与窗口多边形生成的梯形也会部分重叠。多边形裁剪转化成逐行检索两类梯形的“交集”,裁剪结果是分布在各扫描带上的“交梯形”的集合。1234针对多边形
5、顶点和交点，对其纵坐标y进行排序，以此为依据建立水平扫描线，将主多边形和窗口多边形分别进行分割，得到两个梯形集合。计算主多边形与窗口多边形的交点。在各扫描带上建立“交梯形”的集合。在“交梯形”集合的基础上通过边界追踪等方法构建裁剪多边形并输出计算结果。多边形裁剪算法的步骤关键过程实现一、计算两个图层的交点两多边形图层间的交点也可借助扫描线思想获得，思路为:①分配一个坐标数组，记录主多边形与窗口多边形上所有顶点的纵坐标值，并对该数组排序。②以数组中每一个元素值作水平扫描线，分别将主多边形和窗口多边形的边打断成小线段，得到两组线段集合。③遍历扫描带，在各扫描带上
6、用窗口多边形生成的小线段与主多边形生成的小线段两两判断是否相交，若有交点,则求出交点坐标。在第4条扫描带上拿窗口多边形生成的线段A、B分别与主多边形边生成的线段1、2作相交判断,可以得出线段B与线段2相交。二、多边形梯形化在多边形各个结点（包括顶点与交点）处作水平扫描线只是将多边形的边打断成了小线段,为正确提取出裁剪多边形,必须对多边形完成全梯形化。步骤如下：①分配一个坐标数组，记录主多边形与窗口多边形上所有结点的纵坐标值，并对该数组排序。②以数组中每一个元素值作水平扫描线，分别将主多边形和窗口多边形的边打断成小线段，得到两组线段集合。【类同前面】③对各个扫
7、描带上的小线段从左至右两个为一组提取并作为梯形斜边构造梯形。（注意：主多边形与窗口多边形分开来看！）（1）用一个结构体来表示梯形单元,其中记录梯形的4个顶点坐标。每条扫描带上用一个有序链表来存储该带上所生成的梯形集合。则每条扫描带对应有两个有序链表，分别对应存储主多边形和窗口多边形的梯形集。（2）对每条扫描带：先固定主多边形的链表(参照链表),再拿窗口多边形链表中的梯形逐个与参照链表中的梯形集作比较,判断是否有梯形相交的情形出现，这个过程称为梯形与参照链表的“插入”操作。若待“插入”梯形与链表中的梯形不相交,舍弃该操作,否则对参照链表中的梯形执行“分裂”运算
8、，并对“交梯形”进行标记。（3）“分裂”运算的关键是
