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

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