区域填充的扫描线算法

扫描线多边形填充算法例题

扫描线多边形填充算法是一种常用的计算机图形学算法，用于对多边形进行填充。下面我将以一个例题来说明该算法的步骤和原理。

假设有一个凸多边形，顶点坐标分别为A(2, 4)，B(6, 6)，C(8, 4)，D(6, 2)，E(4, 2)。现在我们要使用扫描线多边形填充算法对该多边形进行填充。

步骤如下：

1. 首先，确定扫描线的范围。扫描线的范围由多边形的最高点和最低点决定，即在本例中扫描线的范围为y=2到y=6。

2. 从最高点开始，逐行进行扫描线填充。在本例中，从y=6开始扫描。

3. 对于每一条扫描线，确定与多边形交点的x坐标。在本例中，对于y=6，与多边形交点的x坐标为x=2和x=6。

4. 将交点按照升序排列，得到交点序列。在本例中，交点序列为(2, 6)，(6, 6)。

5. 根据交点序列，对每一对交点进行填充。在本例中，对于(2,

6)和(6, 6)，在扫描线y=6上的像素点进行填充。

6. 继续向下扫描，重复步骤3至步骤5，直到扫描到最低点y=2。

通过以上步骤，我们可以完成对该凸多边形的填充。

需要注意的是，如果多边形是凹多边形，那么在步骤3中，可能会出现多个交点。此时，需要根据扫描线与多边形的交点个数的奇偶性来确定填充的规则。

扫描线多边形填充算法的原理是通过扫描线与多边形的交点来确定填充的区域。该算法的优点是简单易懂，适用于凸多边形和简单的凹多边形。然而，对于复杂的凹多边形，该算法可能会遇到一些困难。

希望以上回答能够满足你的要求。如果还有其他问题，请随时提出。

佛山科学技术学院

实 验 报 告

课程名称 计算机图形学基础

实验项目 多边形的区域填充

一、实验目的

1. 通过实验，进一步理解和掌握几种常用多边形填充算法的基本原理

2. 掌握多边形区域填充算法的基本过程

3. 掌握在C/C++环境下用多边形填充算法编程实现指定多边形的填充。

二、实验内容

用种子填充算法和扫描线填充算法等任意两种算法实现指定多边形的区域填充。

三、实验原理

种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。种子填充算法常用四连通域和八连通域技术进行填充操作。

四向连通填充算法：

a） 种子像素压入栈中；

b） 如果栈为空，则转e)；否则转c)；

c） 弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈；

d） 转b）；

e） 结束。

扫描线填充算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。

区域填充的扫描线算法可由下列四个步骤实现：

(1)初始化：堆栈置空。将种子点(x,y)入栈。

(2)出栈：若栈空则结束。否则取栈顶元素(x,y)，以y作为当前扫描线。

(3)填充并确定种子点所在区段：从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。

(4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。

扫描线算法（Scan-Line Filling）

扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需要指定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏和三维CAD软件的渲染等等。

对矢量多边形区域填充，算法核心还是求交。《计算几何与图形学有关的几种常用算法》一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法，利用此算法可以判断一个点是否在多边形内，也就是是否需要填充，但是实际工程中使用的填充算法都是只使用求交的思想，并不直接使用这种求交算法。究其原因，除了算法效率问题之外，还存在一个光栅图形设备和矢量之间的转换问题。比如某个点位于非常靠近边界的临界位置，用矢量算法判断这个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就有可能是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此，适用于矢量图形的填充算法必须适应光栅图形设备。

扫描线算法的基本思想

扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色画水平直线。多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤：

（1） 求交，计算扫描线与多边形的交点

（2） 交点排序，对第2步得到的交点按照x值从小到大进行排序；

（3） 颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色填充；

（4） 是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第1步继续处理；

整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显示。

对于每一条扫描线，如果每次都按照正常的线段求交算法进行计算，则计算量大，而且效率底下，如图（6）所示： 图（6） 多边形与扫描线示意图

扫描线种子填充算法

扫描线种子填充算法的基本过程如下：当给定种子点(x, y)时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个区段的范围[xLeft, xRight]，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。

扫描线种子填充算法可由下列四个步骤实现：

(1) 初始化一个空的栈用于存放种子点，将种子点(x, y)入栈；

(2) 判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y是当前的扫描线；

(3) 从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xLeft和xRight；

(4) 分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素，从xLeft开始向xRight方向搜索，若存在非边界且未填充的像素点，则找出这些相邻的像素点中最右边的一个，并将其作为种子点压入栈中，然后返回第（2）步；

这个算法中最关键的是第（4）步，就是从当前扫描线的上一条扫描线和下一条扫描线中寻找新的种子点。如果新扫描线上实际点的区间比当前扫描线的[xLeft,

xRight]区间大，而且是连续的情况下，算法的第（3）步就处理了这种情况。如图所示：

新扫描线区间增大且连续的情况 假设当前处理的扫描线是黄色点所在的第7行，则经过第3步处理后可以得到一个区间[6,10]。然后第4步操作，从相邻的第6行和第8行两条扫描线的第6列开始向右搜索，确定红色的两个点分别是第6行和第8行的种子点，于是按照顺序将（6, 10）和（8, 10）两个种子点入栈。接下来的循环会处理（8, 10）这个种子点，根据算法第3步说明，会从（8, 10）开始向左和向右填充，由于中间没有边界点，因此填充会直到遇到边界为止，所以尽管第8行实际区域比第7行的区间[6,10]大，但是仍然得到了正确的填充。