一、实现方案

扫描线算法：

实现原理：

       把图形的填充转换为扫描线从上往下扫描填充，这时我们只需要判断每一条扫描线与图形的交点，而我们可以根据扫描线的连贯性，对交点进行排序，第1个点与第2个点之间，第3个点与第4个点之间.....
       依照此原理可以对图形进行扫描线算法扫描转换多边形，其中在判断上述交点时，还会出现扫描线与边重合、扫描线与边的交点为顶点等现象，具体实现步骤如下。

实现步骤：

1、找到多边形的最大Ymax和最小Ymin，在此范围内扫描多边形逐条；

2、一条扫描线y，求与多边形的交点（通过与每一条边的求交，步骤如下），首先定义一个交点表
     （1）如果该边是水平的，并且边的Y值=y，直接将该线画出来
     （2）如果该边与y无交点，跳过
     （3）该边与y有交点,求出交点（qx，qy）
            i.如果该点是顶点

             ①如果该点极值点，将该点x加入表两次

             ①否则将该x加入表一次<通过判断顶点相交的两点是否在一侧>

            Ii.如果不是顶点，则直接将该x加入表中

     （4）对交点的x进行排序
     （5）按照扫描线的连贯性进行填充
     （6）重复上述操作

注：设计多边形时，需要按顺序导入点

种子填充算法：

实现原理：

       通过区域的4连通和8连通（区域内每一个像素可以通过四个方向（上、下、左、右）组合到达。），从四个方向寻找下一像素者来完成整个区域的填充。

实现步骤：

1. 设（x,y）为内点表示的4连通区域内的一点，oldColor为区域的原色，newColor为填充后的颜色。
2. 确定多边形的边界，并初始化区域内部原色
3. 以（x,y）开始，每次向（上、下、左、右）四个点延伸，判断该点颜色，如果为newColor，递归终止。否则填充该点颜色为newColor，并以该点开始递归开始步骤3
4. 所有点都被点亮，递归终止

注：实现代码只能完成矩形的填充

二、代码实现

任务A（扫描线算法填充）： 

实现代码：

源代码：

class  MyPolygon
{
public:
    int m_VerticeNumber;
    CPoint m_Vertex[50];
    COLORREF m_LineColor;
};

//--------------------------------
int getMiny(MyPolygon ThePolygon)
{
    int min = ThePolygon.m_Vertex[0].y;
    for (int i = 1; i < ThePolygon.m_VerticeNumber; i++)
        if (min > ThePolygon.m_Vertex[i].y)
            min = ThePolygon.m_Vertex[i].y;
    return min;
}

int getMaxy(MyPolygon ThePolygon)
{
    int max = ThePolygon.m_Vertex[0].y;
    for (int i = 1; i < ThePolygon.m_VerticeNumber; i++)
        if (max < ThePolygon.m_Vertex[i].y)
            max = ThePolygon.m_Vertex[i].y;
    return max;
}

//交换
void Swap(int* a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
//随机快速排序

int qsort(int* a, int begin, int end) {
    int i, j, temp;
    i = begin - 1; j = begin;
    for (; j < end; j++)
    {
        if (a[j] <= a[end - 1])
            Swap(a, ++i, j);
    }
    return i;
}

void randqsort(int* a, int begin, int n) {
    while (begin >= n)
        return;
    srand((unsigned)time(NULL));
    int key = (begin + rand() % (n - begin));
    Swap(a, key, n - 1);
    int m = qsort(a, begin, n);
    randqsort(a, begin, m);
    randqsort(a, m + 1, n);
}

void ScanFill(CDC* pDC, MyPolygon ThePolygon, CPoint startPoint, COLORREF fillCol)
{
    int miny, maxy;
    int sx, sy, tx, ty;
    miny = getMiny(ThePolygon);
    maxy = getMaxy(ThePolygon);
    int* index = new int[100];
    int* judge = new int[ThePolygon.m_VerticeNumber];
    memset(index, -1, sizeof(int) * 100);
    memset(judge, 0, sizeof(int) * ThePolygon.m_VerticeNumber);
    int x;
    CPoint Point;
    for (int i = miny; i <= maxy; i++)
    {
        //记录扫描线与边线的交点
        int temp = 0;
        for (int i1 = 0, L = ThePolygon.m_VerticeNumber, j1 = L - 1; i1 < L; j1 = i1, i1++) {

            sx = ThePolygon.m_Vertex[i1].x;
            sy = ThePolygon.m_Vertex[i1].y;
            tx = ThePolygon.m_Vertex[j1].x;
            ty = ThePolygon.m_Vertex[j1].y;
            int lowy, heighty;
            lowy = (sy < ty) ? sy : ty;
            heighty = (sy > ty) ? sy : ty;
            //水平线
            if (ty == sy)
            {
                if (i == ty)
                {
                    int xmax, xmin;
                    xmax = (sx > tx) ? sx : tx;
                    xmin = (sx < tx) ? sx : tx;
                    for (int xx = xmin; xx <= xmax; xx++)
                    {
                        Point.x = xx; Point.y = i;
                        pDC->SetPixelV(Point, fillCol);
                    }
                }
                continue;
            }
            //没有交点
            if (i<lowy || i>heighty)
                continue;
            x = sx + (i - sy) * (tx - sx) / (ty - sy);
            //判断交点(x,i)是不是顶点
            if ((x == ThePolygon.m_Vertex[i1].x && i == ThePolygon.m_Vertex[i1].y))
            {
                //判断顶点是不是极值点  
                //即判断与交点相关联的两条线的另外两个顶点是不是在交点的同一侧
                if (i1 != L - 1 && judge[i1] == 0) {
                    if ((i - ThePolygon.m_Vertex[i1 + 1].y) * (i - ThePolygon.m_Vertex[j1].y) < 0)//异号
                        index[temp++] = x;
                    else//同号  极值点 记录两次
                    {
                        index[temp++] = x;
                        index[temp++] = x;
                    }
                }
                else if (i1 == L - 1 && judge[i1] == 0)
                {
                    if ((i - ThePolygon.m_Vertex[0].y) * (i - ThePolygon.m_Vertex[j1].y) < 0) {//异号
                        index[temp++] = x;
                    }
                    else//同号  极值点  记录两次
                    {
                        index[temp++] = x;
                        index[temp++] = x;
                    }
                }
                judge[i1] = 1;
                continue;
            }
            else if ((x == ThePolygon.m_Vertex[j1].x && i == ThePolygon.m_Vertex[j1].y))
            {
                if (j1 != 0 && judge[j1] == 0) {
                    if ((i - ThePolygon.m_Vertex[i1].y) * (i - ThePolygon.m_Vertex[j1 - 1].y) < 0) {//异号
                        index[temp++] = x;

                    }
                    else//同号  极值点
                    {
                        index[temp++] = x;
                        index[temp++] = x;
                    }

                }
                else if (j1 == 0 && judge[j1] == 0)
                {
                    if ((i - ThePolygon.m_Vertex[i1].y) * (i - ThePolygon.m_Vertex[l - 1].y) < 0)//异号
                        index[temp++] = x;
                    else//同号  极值点
                    {
                        index[temp++] = x;
                        index[temp++] = x;
                    }
                }
                judge[j1] = 1;
                continue;
            }
            //交点不是顶点
            index[temp++] = x;
        }

        //将index排序
        randqsort(index, 0, temp);//随机快速

        //填充多边形
        for (int n = 0, m = n + 1; m < temp && index[n] != -1; n += 2, m = n + 1)
        {
            for (int xx = index[n]; xx <= index[m]; xx++)
            {
                Point.x = xx; Point.y = i;
                pDC->SetPixelV(Point, fillCol);
            }
        }
        //清零
        for (int k = 0; k < 100; k++)
            index[k] = -1;
    }
    delete[] index;
    delete[] judge;
}

任务B（种子填充算法）：

实现代码：

 源代码：

void FloodFill4(CDC* pDC, int x, int y, int Color) {
    
    if((x<20 )&& (x>-20)&& (y > -20) && (y < 20)&&(pDC->GetPixel(x ,y) != Color)){
        pDC->SetPixel(x, y, Color);
        FloodFill4(pDC, x, y - 1,Color);
        FloodFill4(pDC, x + 1, y,Color);
        FloodFill4(pDC, x - 1, y,Color);
        FloodFill4(pDC, x, y + 1,Color);
    }
    else{
        return;
    }
}

三、算法结果

任务A：

任务Ｂ：

其他计算机图形学实验

传送门

前言

实现多边形扫描线填充算法，并和鼠标进行交互。
具体原理略过，会贴上完整代码，可直接运行。

环境：
vs2019,OpenGL的库（可以搜索如何用vs使用OpenGL的库，可以使用vs自带的插件或者其他方法，很方便）

要点：
1.NET和AET的创建，改动
2.改变鼠标点击和鼠标拖拽的响应事件。

最终效果：
用鼠标随意画顶点，然后展示填充过程
对应控制台会输出顶点坐标和个数

思路借鉴

文章1
文章2

步骤

1.点的结构体

struct point
{
	float x, y;
	point(){}
	point(int xx, int yy):
		x(xx), y(yy) {}
};
vector<point> vertice; //顶点

2. AET 活性边表、NET新边表 的结构体

typedef struct XET
{
	float x;
	float dx;  // 从当前扫描线到下一条扫描线间x的增量，即斜率的倒数
	float ymax; //该边所交的最高扫描线的坐标值ymax
	XET* next;
}AET, NET; //AET 活性边表； NET新边表

3. 扫描线算法实现

void PolyScan()
{
	/*得到最高点的y坐标*/
	int Max_Y = 0;
	for (int i = 0; i < vertice.size(); i++) 
		/*Max_Y = max(Max_Y, vertice[i].y);*/
		if (vertice[i].y > Max_Y)
			Max_Y = vertice[i].y;


	//初始化AET表
	AET* pAET = new AET;
	pAET->next = NULL;

	//初始化NET表
	NET* pNET[800]; //吊桶
	for (int i = 0; i <= Max_Y; i++)
	{
		pNET[i] = new NET;
		pNET[i]->next = NULL;;
	}

	//扫描并且建立NET表
	int len = vertice.size(); //顶点个数
	for (int i = 0; i <= Max_Y; i++)
	{
		for (int j = 0; j < len; j++) //扫描每个点
		{
			if (i == vertice[j].y)
			{
				//如果一个点和前一个点有一条边相连，则该点和后面一个点也相连
				//！这个式子 便于最后一个顶点和第一个点相连 和 防止出现负数
				
				//判断当前点的高低，使ymax、DX、DY的计算有变化
				if (vertice[(j - 1 + len) % len].y > vertice[j].y)
				{
					//前一个点在当前点的上方
					NET* p = new NET;
					p->x = vertice[j].x;
					p->ymax = vertice[(j - 1 + len) % len].y;//与当前扫描线相交的活性边 的 最高点即为相邻顶点的y
					float DX = vertice[(j - 1 + len) % len].x - vertice[j].x;
					float DY = vertice[(j - 1 + len) % len].y - vertice[j].y;
					p->dx = DX / DY;//dx为直线斜率的倒数
					p->next = pNET[i]->next;
					pNET[i]->next = p;
				}
				if (vertice[(j + 1) % len].y > vertice[j].y)
				{
					//后一个点在当前点的上方
					NET* p = new NET;
					p->x = vertice[j].x;
					p->ymax = vertice[(j + 1) % len].y;
					float DX = vertice[(j + 1) % len].x - vertice[j].x;
					float DY = vertice[(j + 1) % len].y - vertice[j].y;
					p->dx = DX / DY;//dx为直线斜率的倒数
					p->next = pNET[i]->next;
					pNET[i]->next = p;
				}
			}
		}
	}

	//建立并且更新活性边表AET
	//各条扫描线i
	for (int i = 0; i <= Max_Y; i++)
	{
		/*把新边表NET[i] 中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列*/
		
		//计算每条扫描线上不同线产生的新的交点x，更新AET
		NET* p = pAET->next;
		while (p)
		{
			p->x = p->x + p->dx; //更新x坐标
			p = p->next;
		}

		//断表排序,不再开辟空间 
		AET* tq = pAET;
		p = pAET->next;
		tq->next = NULL;
		while (p)//顺着链表往下走
		{
			//找到第一个比它大的数字tq->next->next->x，则从p->next到tq->next都是比p->x小的
			while (tq->next != NULL && tq->next->x <= p->x)
				tq = tq->next;
			//插入p到tq和tq->next之间
			NET* t = p->next;
			p->next = tq->next;
			tq->next = p;
			p = t;

			tq = pAET;//回到头
		}

		/*(改进算法) 取消求交，减少计算量*/
		//先从AET表中删除ymax==i的结点****************************************/
		//像素的取舍问题，保证多边形的“下闭上开”，避免填充扩大化（交点的个数应保证为偶数个）
		AET* q = pAET;
		p = q->next;
		while (p)
		{
			if (p->ymax == i)
			{
				q->next = p->next;
				delete p;
				p = q->next;
			}
			else
			{
				q = q->next;
				p = q->next;
			}
		}

		//若NET中有新点，将其用插入法插入AET，按x递增的顺序排列
		p = pNET[i]->next;
		q = pAET;
		while (p)
		{
			while (q->next && p->x >= q->next->x)
				q = q->next;
			//插入p
			NET* t = p->next;
			p->next = q->next;
			q->next = p;
			p = t;

			q = pAET;//回到头
		}

		//配对后填充颜色
		p = pAET->next;
		while (p && p->next != NULL)
		{
			for (float j = p->x; j <= p->next->x; j++)
			{
				//扫描线画点
				draw_a_point(j, i);
				//cout << "(" << j << ", " << i << ")" << endl;
			}
			p = p->next->next;//考虑端点情况
		}
	}
	glFlush();
}

4. 改变鼠标响应函数

void mymouse(int button, int state, int x, int y)
{
	//左键
	if (button == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
	{
		draw_a_point(x, window_height - y);

		point p(x, window_height - y);
		vertice.push_back(p);
		cout << "顶点" << vertice.size() << ": (" << x << ", " << window_height - y << ")" << endl;
	}
	//右键
	if (button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN)
	{
		glClearColor(1, 1, 1, 1);//设置绘制窗口颜色为白色
		glColor3f(0, 1, 1);

		//绘制多边形
		glBegin(GL_LINES);	
		for (int i = 0; i < vertice.size(); i++)
		{
			if (i == vertice.size() - 1)//画完最后一个点，使其闭合
			{
				glVertex2f(vertice[0].x, vertice[0].y);
				glVertex2f(vertice[i].x, vertice[i].y);
			}
			else
			{
				glVertex2f(vertice[i].x, vertice[i].y);
				glVertex2f(vertice[i + 1].x, vertice[i + 1].y);
			}
		}
		glEnd();
		glFlush();
	}

	//鼠标中间
	if (button == GLUT_MIDDLE_BUTTON && state == GLUT_DOWN)
	{
		//cout << "center: (" << x << ", " << y << ")" << endl;
		//BoundaryFill4(x, window_height - y);
		//BoundaryFill4_Stack(x, window_height - y);

		cout << "多边形顶点个数为" << vertice.size() << "。 " << "开始扫描线填充。" << endl;
		PolyScan();
	}
}

完整代码

//扫描线算法
#include<iostream>
#include<gl/glut.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int window_width = 800, window_height = 600;
const int maxn = 99999;

struct point
{
	float x, y;
	point(){}
	point(int xx, int yy):
		x(xx), y(yy) {}
};
vector<point> vertice; //顶点

typedef struct XET
{
	float x;
	float dx;  // 从当前扫描线到下一条扫描线间x的增量，即斜率的倒数
	float ymax; //该边所交的最高扫描线的坐标值ymax
	XET* next;
}AET, NET; //AET 活性边表； NET新边表

void draw_a_point(int x, int y);
void PolyScan();
void mymouse(int button, int state, int x, int y);
void display();


int main(int argc, char* argv[])
{
	glutInit(&argc, argv);
	glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
	glutInitWindowPosition(100, 50);
	glutInitWindowSize(window_width, window_height);
	glutCreateWindow("扫描线填充");

	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	gluOrtho2D(0, window_width, 0, window_height);

	glClearColor(1, 1, 1, 1);
	glClear(GL_COLOR_BUFFER_BIT);

	glutMouseFunc(&mymouse);
	glutDisplayFunc(&display);

	glutMainLoop();
	return 0;
}

//画点函数
void draw_a_point(int x, int y)
{
	glBegin(GL_POINTS);
	glColor3f(0, 1, 1);
	glVertex2f(x, y);
	glEnd();
	glFlush();
}

void PolyScan()
{
	/*得到最高点的y坐标*/
	int Max_Y = 0;
	for (int i = 0; i < vertice.size(); i++) 
		/*Max_Y = max(Max_Y, vertice[i].y);*/
		if (vertice[i].y > Max_Y)
			Max_Y = vertice[i].y;


	//初始化AET表
	AET* pAET = new AET;
	pAET->next = NULL;

	//初始化NET表
	NET* pNET[800]; //吊桶
	for (int i = 0; i <= Max_Y; i++)
	{
		pNET[i] = new NET;
		pNET[i]->next = NULL;;
	}

	//扫描并且建立NET表
	int len = vertice.size(); //顶点个数
	for (int i = 0; i <= Max_Y; i++)
	{
		for (int j = 0; j < len; j++) //扫描每个点
		{
			if (i == vertice[j].y)
			{
				//如果一个点和前一个点有一条边相连，则该点和后面一个点也相连
				//！这个式子 便于最后一个顶点和第一个点相连 和 防止出现负数
				
				//判断当前点的高低，使ymax、DX、DY的计算有变化
				if (vertice[(j - 1 + len) % len].y > vertice[j].y)
				{
					//前一个点在当前点的上方
					NET* p = new NET;
					p->x = vertice[j].x;
					p->ymax = vertice[(j - 1 + len) % len].y;//与当前扫描线相交的活性边 的 最高点即为相邻顶点的y
					float DX = vertice[(j - 1 + len) % len].x - vertice[j].x;
					float DY = vertice[(j - 1 + len) % len].y - vertice[j].y;
					p->dx = DX / DY;//dx为直线斜率的倒数
					p->next = pNET[i]->next;
					pNET[i]->next = p;
				}
				if (vertice[(j + 1) % len].y > vertice[j].y)
				{
					//后一个点在当前点的上方
					NET* p = new NET;
					p->x = vertice[j].x;
					p->ymax = vertice[(j + 1) % len].y;
					float DX = vertice[(j + 1) % len].x - vertice[j].x;
					float DY = vertice[(j + 1) % len].y - vertice[j].y;
					p->dx = DX / DY;//dx为直线斜率的倒数
					p->next = pNET[i]->next;
					pNET[i]->next = p;
				}
			}
		}
	}

	//建立并且更新活性边表AET
	//各条扫描线i
	for (int i = 0; i <= Max_Y; i++)
	{
		/*把新边表NET[i] 中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列*/
		
		//计算每条扫描线上不同线产生的新的交点x，更新AET
		NET* p = pAET->next;
		while (p)
		{
			p->x = p->x + p->dx; //更新x坐标
			p = p->next;
		}

		//断表排序,不再开辟空间 
		AET* tq = pAET;
		p = pAET->next;
		tq->next = NULL;
		while (p)//顺着链表往下走
		{
			//找到第一个比它大的数字tq->next->next->x，则从p->next到tq->next都是比p->x小的
			while (tq->next != NULL && tq->next->x <= p->x)
				tq = tq->next;
			//插入p到tq和tq->next之间
			NET* t = p->next;
			p->next = tq->next;
			tq->next = p;
			p = t;

			tq = pAET;//回到头
		}

		/*(改进算法) 取消求交，减少计算量*/
		//先从AET表中删除ymax==i的结点****************************************/
		//像素的取舍问题，保证多边形的“下闭上开”，避免填充扩大化（交点的个数应保证为偶数个）
		AET* q = pAET;
		p = q->next;
		while (p)
		{
			if (p->ymax == i)
			{
				q->next = p->next;
				delete p;
				p = q->next;
			}
			else
			{
				q = q->next;
				p = q->next;
			}
		}

		//若NET中有新点，将其用插入法插入AET，按x递增的顺序排列
		p = pNET[i]->next;
		q = pAET;
		while (p)
		{
			while (q->next && p->x >= q->next->x)
				q = q->next;
			//插入p
			NET* t = p->next;
			p->next = q->next;
			q->next = p;
			p = t;

			q = pAET;//回到头
		}

		//配对后填充颜色
		p = pAET->next;
		while (p && p->next != NULL)
		{
			for (float j = p->x; j <= p->next->x; j++)
			{
				//扫描线画点
				draw_a_point(j, i);
				//cout << "(" << j << ", " << i << ")" << endl;
			}
			p = p->next->next;//考虑端点情况
		}
	}
	glFlush();
}
void mymouse(int button, int state, int x, int y)
{
	//左键
	if (button == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
	{
		draw_a_point(x, window_height - y);

		point p(x, window_height - y);
		vertice.push_back(p);
		cout << "顶点" << vertice.size() << ": (" << x << ", " << window_height - y << ")" << endl;
	}
	//右键
	if (button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN)
	{
		glClearColor(1, 1, 1, 1);//设置绘制窗口颜色为白色
		glColor3f(0, 1, 1);

		//绘制多边形
		glBegin(GL_LINES);	
		for (int i = 0; i < vertice.size(); i++)
		{
			if (i == vertice.size() - 1)//画完最后一个点，使其闭合
			{
				glVertex2f(vertice[0].x, vertice[0].y);
				glVertex2f(vertice[i].x, vertice[i].y);
			}
			else
			{
				glVertex2f(vertice[i].x, vertice[i].y);
				glVertex2f(vertice[i + 1].x, vertice[i + 1].y);
			}
		}
		glEnd();
		glFlush();
	}

	//鼠标中间
	if (button == GLUT_MIDDLE_BUTTON && state == GLUT_DOWN)
	{
		//cout << "center: (" << x << ", " << y << ")" << endl;
		//BoundaryFill4(x, window_height - y);
		//BoundaryFill4_Stack(x, window_height - y);

		cout << "多边形顶点个数为" << vertice.size() << "。 " << "开始扫描线填充。" << endl;
		PolyScan();
	}
}
void display()
{
	glClear(GL_COLOR_BUFFER_BIT);
	glColor3f(0.0, 0.4, 0.2);
	glPointSize(1);
	glBegin(GL_POINTS);
	PolyScan();
	glEnd();
	glFlush();
}

总结

扫描线算法部分，建立NET 和 建立并且更新活性边表AET 这两个地方比较复杂，可以带入图中多想

一.基本原理

           扫描线多边形区域填充算法是按扫描线顺序（由下到上），计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。

           区间的端点可以通过计算扫描线与多边形边界线的交点获得。

           对于一条扫描线，多边形的填充过程可以分为四个步骤：

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

（2）排序：把所有交点按x值递增顺序排序；

（3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间;

（4）填色：把相交区间内的象素置成多边形颜色;

如图所示，扫描线 6 与多边形的边界 线交于四点A、B、C、D。
这四点把扫描线分 为五个区间 [0, 2]，[2, 3.5]，[3.5, 7]，[7, 11]， [11, 2]。
其中， [2, 3.5]， [7, 11] 两个区间落在 多边形内，该区间内的象素应取多边形色。
其它区间内的象素取背景色。
这里的四个交点在计算时未必是按从左到 右的顺序获得。
例如，当多边形采用顶点序列 P1P2P3P4P5P6 表示时，把扫描线 6 分别与边 P1P2，P2P3，P3P4，P4P5，P5P6，P6P1 相 交，
得到交点序列D、C、B、A，必须经过排 序，才能得到从左到右，按 x 递增顺序排列的
交点 x 坐标序列。

二.问题

（1）当扫描线与多边形顶点相交时，交点 的取舍问题（保证交点正确配对）：

     检查相交顶点的两条边的另外两个顶点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定是取零个、一个、还是两个。

当扫描线与多边形顶点相交 时，会出现异常情况。例如图所示，扫描线 2 与 P1 相交。
按前述方法求得交点 ( x 坐标)序列：2，2，8。这将导致 [2, 8] 区间内的 象素取背景色，
而这个区间的象素正是属于多 边形内部，需要填充的。
所以，我们拟考虑当 扫描线与多边形的顶点相交时，相同的交点只 取一个。
这样，扫描线 2 与多边形的交点序列就成为 2，8。正是我们所希望的结果。
然而，按新的规定，扫描线 7 与多边形的 交点序列为 2，9，11。
这将导致错把[2,9]区间作为多边形内部来填充。
为了正确地进行交点取舍，必须对上述两种 情况区别对待。
在第一种情况，扫描线交于一顶 点，而共享顶点的两条边分别落在扫描线的两边 。
这时，交点只算一个。在第二种情况，共享交 点的两条边在扫描线的同一边，这时交点作为零个或两个，
取决于该点是多边形的局部最高点还是局部最低点。
具体实现时，只需检查顶点的两条边的另 外两个端点的 y 值。按这两个 y 值中大于交点 y 值的个数是 0，1，2 来决定是取零个、一 个、还是二个。
例如，扫描线 1 交于顶点 P2，由于共享该顶点的两条边的另外二个顶点 均高于扫描线，故取交点 P2 两次。
这使得 P2 象素用多边形颜色设置。
再考虑扫描线 2。在 P1 处，由于 P6 高于扫描线，而 P2 低于扫描 线，所以该交点只算一个。
而在 P6 处，由于 P1和P5均在下方，所以扫描线 7 与之相交时，交点算零个，该点不予填充。
//
(如果某一条边，平行于某一条扫描线；那这一条边，不予记录)///

（2）多边形边界上象素的取舍问题（避免填充扩大化）：

对扫描线与多边形的相交区间取左闭右开。

例如，对左下角为 (1,1)，右上角为(3,3)的正方形填充 时，若对边界上所有象素均进行填充，
被填充的象素覆盖的面积为 3×3 单位，而方形实际面积只有 2×2 单 位。显然，
这个扩大化问题是由于对边界上的所有象素进行填充引起的。
为了克服这个问 题，规定落在右/上边界的象素不予填充，而落在左/下边界的象素予以填充。
在具体实现时，只要对扫描线与多边形的 相交区间取*左闭右开*。
容易看出，我们在前面 一个问题所采用的方法，即扫描线与多边形顶
点相交时，交点的取舍方法，保证了多边形的 “下闭上开”——丢弃上方水平边以及上方非
水平边上作为局部最高点的顶点。
重合点的处理：当扫描线和边界相交于边界顶点时，同时产生两个交点，通常采用 “起闭终开”或“起开终闭” 。
水平边处理：水平边不参加求交计算，跳过。

三. 解决步骤

 为了计算每条扫描线与多边形各边的交点， 最简单的方法是把多边形的所有边放在一个表中。

这样处理效率很低。这是因为一条扫描线 往往只与少数几条边相交，甚至与整个多边形 都不相交。若在处理每条扫描线时，不分青红 皂白地把所有边都拿来与扫描线求交，则其中 决大多数计算都是徒劳无用的。

为了提高效率，在处理一条扫描线时，仅 对与它相交的多边形的边进行求交运算。我们 把与当前扫描线相交的边称为活性边，并把它 们按与扫描线交点 x 坐标递增的顺序存放在一个链表中，称此链表为活性边表（AET）。

 假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量△x。(连贯性)

        设该边的直线方程为：ax+by+c=0；

        若y＝yi，x=xi；则当y = yi+1时，

         xi+1=xi-b/a

       其中ΔX= -b/a为常数，

       另外使用增量法计算时，我们需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表中删除出去。

x i+1 = ( - by i+1 –c)/a = x i –b/a 其中△x = -b/a 为常量。△x 可以存放在对应 边的活性边表结点中。另外，使用增量法计算 时，我们需要知道一条边何时与下一条扫描线 相交，以便及时把它从活性边表中删除出去， 避免下一步进行无谓的计算。综上所述，活性边表的结点中至少应为对应边保存如下内容：

第1项存当前扫描线与边的交点坐标x值；

第2项存从当前扫描线到下一条扫描线间x的增量D x；

第3项存该边所交的最高扫描线号ymax；

第4项存指向下一条边的指针（Λ代表一条边的退出，即结束或抛弃）；

扫描线6的活性边表  ：

 扫描线7的活性边表：

 为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表（NET）,存放在该扫描线第一次出现的边。也就是说，若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。

1.这个结构实际上是一个指针数组，数组的每个变量是个指针，
这个指针指向所有的以这个y值作为起点的边。
2.把多边形所有的边全部填成这样的结构，插到这个指针数组里面来。
3.从上面这个指针数组里面就知道多边形是从哪里开始的。
在这个指针数组里只有1、2、3、5处有边，因此当从下往上进行扫描转换的时候，
从y=1开始做，而在1这条线上有两条边进来了，然后就把这两条边放进活性边表来处理。
4.当处理y=2这条扫描线时（活性边里有2条边），先看活性边表里是否有边要退出和加入，
实际上p1p2边要退出了（y=ymax），p1p6边要加入了。
退出的边要从活性边表里去掉，不退出的边要进行处理，即把x值加上一个增量。
（这时p1p2变后边需要加一个Λ）
5.后面持续步骤3,4，只到y=5这扫描线结束。
6.即每做一次新的扫描线时，要对已有的边进行三个处理：
一是否被去除掉；如果不被去除；
第二就要对它的数据进行更新，所谓更新数据就是要更新它的x值，即x+△x；
最后，就是有没有新的边进来，新的边在NET里，可以插入排序插进来。

四.算法描述

     这个算法过程从来没有求交，这套数据结构使得你不用求交点！避免了求交运算。

     扫描线多边形填充算法的主要步骤：

1. 建立NET(NewEdgeList)
2. 从最低扫描线开始到最高扫描线循环
3. 建立或调整AET(ActiveEdgeList)
4.  按照AET中的接点顺序填充

void polyfill (多边形  polygon, 颜色 color)
{ for (各条扫描线i )
  { 初始化新边表头指针NET [i]；把ymin = i 的边放进边表NET [i];   }
   y = 最低扫描线号；
   初始化活性边表AET为空；
   for (各条扫描线i )
    { 把新边表NET[i]中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；
      遍历AET表，把y max= i 的结点从AET表中删除，并把y max > i结点的x值递增D x；
      若允许多边形的边自相交，则用冒泡排序法对AET表重新排序；
      遍历AET表，把配对交点区间(左闭右开)上的象素(x, y)，用drawpixel (x, y, color) 改写象素颜色值；
     }
}