Q|二、多边形的填充原理 多边形图形的填充原理:找出所有位于封闭图形内的像素点, 把这些点置换成所要求的像素值。 般方法:如果在显示屏中,采用从上到下、从左到右找出每一 个显示点,然后通过多边形的边界函数(凸多边形有边界函数且表 达方式简单等方法,判断其是否位于封闭图形之内后再填充。 评价:这种方法原理虽然简单,但速度太慢,特别不适合凹多边 形与带孔多边形的填充需要 因此有必要寻找一种通用的(适用于凸、凹、带孔的多边形) 快速判断像素点位于封闭图形之内的计算方法,这是多边形图形 填充的关键
二、多边形的填充原理 多边形图形的填充原理：找出所有位于封闭图形内的像素点， 把这些点置换成所要求的像素值。 一般方法：如果在显示屏中，采用从上到下、从左到右找出每一 个显示点，然后通过多边形的边界函数(凸多边形有边界函数且表 达方式简单)等方法，判断其是否位于封闭图形之内后再填充。 评价：这种方法原理虽然简单，但速度太慢，特别不适合凹多边 形与带孔多边形的填充需要。 因此有必要寻找一种通用的(适用于凸、凹、带孔的多边形) 快速判断像素点位于封闭图形之内的计算方法，这是多边形图形 填充的关键
利用射线的交点计数法判断像素点位于封 闭图形内外的方法 从封闭图形外找一点,引一水平射线(称为扫描线)与封闭图形 相交。当交点计数为奇数时,扫描线在封闭图形内(射线穿人封闭 图形);当交点计数为偶数时,扫描线在封闭图形外,该方法简称 交点计数法则。 60000 缺点:这种计算交 点的方法不能正确 处理如y=7时的情 况。必须提出补充 规则以完善交点计 数法则。 012343678910B6 图2-3封闭图形与扫描线
利用射线的交点计数法判断像素点位于封 闭图形内外的方法 从封闭图形外找一点，引一水平射线(称为扫描线)与封闭图形 相交。当交点计数为奇数时，扫描线在封闭图形内(射线穿人封闭 图形)；当交点计数为偶数时，扫描线在封闭图形外，该方法简称 交点计数法则。 缺点：这种计算交 点的方法不能正确 处理如y=7时的情 况 。必须提出补充 规则以完善交点计 数法则
Q改进方法() 1.当扫描线与封闭多边形的水平边相交时,不计算其交点个数; 2.当扫描线与封闭多边形的奇异点相交时,其交点个数计算两次 而对于扫描线与多边形的其余每条斜边相交,其交点个数仅计算 次 所谓奇异点即封闭图 形的极值点,图中共 有(7,7),(7 (2 9),(3,1)等4个奇8-0006000 异点 这样保证了任何一条扫描4 线与多边形相交,其交点3 个数总是偶数。由此能正 确地判断出每一条扫描线 中哪一部分位于封闭图形0123456789101456 之内,哪一部分位于其外。 图23封闭图形与扫描线
改进方法(1) 1.当扫描线与封闭多边形的水平边相交时，不计算其交点个数； 2.当扫描线与封闭多边形的奇异点相交时，其交点个数计算两次； 而对于扫描线与多边形的其余每条斜边相交，其交点个数仅计算 一次。 所谓奇异点即封闭图 形的极值点，图中共 有(7，7)，(7，1)，(2， 9)，(13，11)等4个奇 异点. 这样保证了任何一条扫描 线与多边形相交，其交点 个数总是偶数。由此能正 确地判断出每一条扫描线 中哪一部分位于封闭图形 之内，哪一部分位于其外
改进方法(2) 由于奇异点的交点个数要计算两次,这对于实际操作来讲还不够简练, 因此对于多边形填充又提出另一种对奇异点的简单近似的处理方法: 在计算扫描线与多边形的每一斜边的交点之前,将斜边中最低的端点 在y方向上缩短一个屏坐标刻度单位(注意,这将忽略近似水平斜边),然后 再计算水平扫描线与多边形各斜边的所有交点。经过这样处理后,对多边 形的极大值奇异点计算两次交点,而忽略了极小值奇异点的存在。 eeeeee 66ee由 X (a)该点填充两次 (b)缩短一个y单位, (c)缩短一个y单位, 该点填充一次 缺少这条扫描线 图24奇异点的简单近似处理方法 缺点:严重时,实面积图形的下部分缺少一条扫描填充线
改进方法(2) 由于奇异点的交点个数要计算两次，这对于实际操作来讲还不够简练， 因此对于多边形填充又提出另一种对奇异点的简单近似的处理方法： 在计算扫描线与多边形的每一斜边的交点之前，将斜边中最低的端点 在y方向上缩短一个屏坐标刻度单位(注意，这将忽略近似水平斜边)，然后 再计算水平扫描线与多边形各斜边的所有交点。经过这样处理后，对多边 形的极大值奇异点计算两次交点，而忽略了极小值奇异点的存在。 缺点：严重时，实面积图形的下部分缺少一条扫描填充线