这里的四个交点在计算时未必是按从左到右 顶序获得。例如,当多边形采用顶点序列 P1P2P3P4P5P6表示时,把扫描线6分别与P1P2 P2P3、P3P4、P4P5 P5P6、P6P1六条边 相交,得到交点序列为D、C、B、A,必须经过 序,按X递增的顺序排列交点顺序,才能得到从 左到右排列的交点序列。 般多边形的填充过程,对于一条扫描线, 可以分为四个步骤: (1)求交:计算扫描线与多边形各边的交点 (2)排序:把所有交点按x递增顺序进行排序 3)交点配对:第一个与第二个,第三个与第四 第2i-1与第 配对,其中 1~n。每对交点就代表扫描线与多边形的一个相 交区间 4)区间填色:把这些相交区间内的像素置成多边 填充色,把区间外的像素置成背景色
这里的四个交点在计算时未必是按从左到右 顺序获得。例如，当多边形采用顶点序列 P1P2P3P4P5P6表示时，把扫描线6分别与P1P2、 P2P3 、P3P4 、P4P5 、P5P6 、P6P1 六条边 相交，得到交点序列为D、C、B、A，必须经过 排序，按x递增的顺序排列交点顺序，才能得到从 左到右排列的交点序列。 一般多边形的填充过程，对于一条扫描线， 可以分为四个步骤： (1)求交：计算扫描线与多边形各边的交点； (2)排序：把所有交点按x递增顺序进行排序； (3)交点配对：第一个与第二个，第三个与第四 个，…，第2i-1与第2i个交点配对，其中，i取 1~n。每对交点就代表扫描线与多边形的一个相 交区间。 (4)区间填色：把这些相交区间内的像素置成多边 形填充色，把区间外的像素置成背景色
在多边形填充算法中,必须解决两个特殊的问题 是当扫描线与多边形顶点相交时,交点的取舍问题 多边形边界上像素的取 题。前者用于保证交点正确配 对,后者用于避免填充扩大化 先讨论第一个问题。当扫描线与多边形顶点相交时, 出现异常情况。例如图5.1.1中过的与P1、P2、P5 P6点的扫描线,算几个交点,如果取舍不正确,交点配对 和填充就会出现错误 为了正确地进行交点取舍,必须按照下面的规则对交 点进行取舍: (1)扫描线交于一顶点,而共享该顶点的两条边分别落在 扫描线的两边,则交点只算一个。如图5.1.2(a) )扫描线交于一顶点,而共享该顶点的两条边在扫描线 同一边,这时交点作为零个或两个,这取决于该顶点 多边形的局部最高点(0个)还是局部最低点(2个) 图51.2(b)和如图5.1.2(C)
在多边形填充算法中，必须解决两个特殊的问题：一 是当扫描线与多边形顶点相交时，交点的取舍问题。二是 多边形边界上像素的取舍问题。前者用于保证交点正确配 对，后者用于避免填充扩大化。 先讨论第一个问题。当扫描线与多边形顶点相交时， 会出现异常情况。例如图5.1.1中过的与P1、P2、P5、 P6点的扫描线，算几个交点，如果取舍不正确，交点配对 和填充就会出现错误。 为了正确地进行交点取舍，必须按照下面的规则对交 点进行取舍： (1)扫描线交于一顶点，而共享该顶点的两条边分别落在 扫描线的两边，则交点只算一个。如图5.1.2(a)。 (2)扫描线交于一顶点，而共享该顶点的两条边在扫描线 的同一边，这时交点作为零个或两个，这取决于该顶点是 多边形的局部最高点（0个）还是局部最低点（2个）。如 图5.1.2(b)和如图5.1.2(c)
A B A B A B (b) (C 取 取零个 取 图51.2扫描线与多边形顶点相交时交点的取舍
A B C A B C C B A (a) 取 一 个 (b) 取 零 个 (c) 取 二 个 图5.1.2 扫描线与多边形顶点相交时交点的取舍
具体实现时,只需检查顶点的两体条边的另外两个端 点的y值,如果两个y值中大于交点出y值的个数是0、1 2,那么交点分别取零个 按照上述规则,图5.1.1中的顶点P2,算两个交点, 这样P2像素用多边形颜色设置。在顶点P1处,只算一个 交点。而在P6处,交点算零个,即该点不予填充 下面讨论第二个问题,即边界上像素的取舍问题。例 如,对左下角为(1,1),右上角为(3,3)的正方形填充时 若对边界上所有的像素均进行填充,就得到如图5.1.3的 结果,被填充的像素覆盖的面积为3X3单位,而正方形的 实际面积只有2X2单位。这种现象称为边界扩大化问题。 为了克服这个问题,规定落在右/上边界的像素不予填充, 而落在左/下边界的像素予以填充。在具体实现时,只要 对扫描线与多边形的相交区间取左闭右开。容易看出,在 解决第一个问题时,对交点的取舍方法保证了多边形的 “下闭上开”,即丢弃上方水平边以及上方非水平边上作 为局部最高点的顶点
具体实现时，只需检查顶点的两体条边的另外两个端 点的y值，如果两个y值中大于交点出y值的个数是0、1、 2，那么交点分别取零个、一个或二个。 按照上述规则，图5.1.1中的顶点P2 ，算两个交点， 这样P2 像素用多边形颜色设置。在顶点P1 处，只算一个 交点。而在P6 处，交点算零个，即该点不予填充。 下面讨论第二个问题，即边界上像素的取舍问题。例 如，对左下角为(1,1)，右上角为(3,3)的正方形填充时， 若对边界上所有的像素均进行填充，就得到如图5.1.3的 结果，被填充的像素覆盖的面积为3х3单位，而正方形的 实际面积只有2х2单位。这种现象称为边界扩大化问题。 为了克服这个问题，规定落在右/上边界的像素不予填充， 而落在左/下边界的像素予以填充。在具体实现时，只要 对扫描线与多边形的相交区间取左闭右开。容易看出，在 解决第一个问题时，对交点的取舍方法保证了多边形的 “下闭上开”，即丢弃上方水平边以及上方非水平边上作 为局部最高点的顶点
432 3 图5.1.3边界上像素的填充
1 2 3 4 x 1 2 3 4 y 图5.1.3 边界上像素的填充