图形学--有效边表填充算法

算法描述：
有效边表填充算法通过维护边表和有效边表，避开了扫描线与多边形所有边求交的复杂运算。

填充原理是按照扫描线从小到大的移动顺序，计算当前扫描线与有效边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，最后用指定颜色填充区间内的所有像素，即完成填充工作。有效边表填充算法已成为目前最为有效的多边形填充算法之一。

Edge.h

#pragma once
class Edge
{
public:
	Edge();
	~Edge();
	Edge(double x, int yMax, double reciprocalOfSlope, Edge* pNext);
	void setEdge(double x, int yMax, double reciprocalOfSlope, Edge* pNext);
	void reUseEdge();

public:
	double x;
	int yMax;
	double reciprocalOfSlope;//斜率分之一，1/k
	Edge* pNext;
};

Edge.cpp

#include "stdafx.h"
#include "Edge.h"


Edge::Edge()
{
	x = 0.0;
	yMax = 0;
	reciprocalOfSlope = 0.0;
	pNext = NULL;
}


Edge::~Edge()
{
}

Edge::Edge(double x, int yMax, double reciprocalOfSlope, Edge* pNext)
{
	this->x = x;
	this->yMax = yMax;
	this->reciprocalOfSlope = reciprocalOfSlope;
	this->pNext = pNext;
}

void Edge::setEdge(double x, int yMax, double reciprocalOfSlope, Edge* pNext)
{
	this->x = x;
	this->yMax = yMax;
	this->reciprocalOfSlope = reciprocalOfSlope;
	this->pNext = pNext;
}

void Edge::reUseEdge()
{
	this->x = this->x + this->reciprocalOfSlope;
	this->pNext = NULL;
}

Bucket.h

#pragma once
#include "Edge.h"

class Bucket
{
public:
	Bucket();
	~Bucket();
	Bucket(int scanLine, Edge* pEdge, Bucket* pNext);

	static Bucket* creatBucket(CPoint points[], int points_num);
	static Bucket* creatEdgeTable(CPoint points[], Edge edges[], int points_num, Bucket* headBucket);
	static void addEdge(Bucket* currentBucket, Edge* edge);

public:
	int scanLine;
	Edge* pEdge;
	Bucket* pNext;
};

Bucket.cpp

#include "stdafx.h"
#include "Bucket.h"

Bucket::Bucket()
{
	scanLine = 0;
	pEdge = NULL;
	pNext = NULL;
}

Bucket::~Bucket()
{
}

Bucket::Bucket(int scanLine, Edge* pEdge, Bucket* pNext)
{
	this->scanLine = scanLine;
	this->pEdge = pEdge;
	this->pNext = pNext;
}

Bucket* Bucket::creatBucket(CPoint points[], int points_num)
{
	if (points_num == 0) { return NULL; }

	int scanMin = points[0].y, scanMax = points[0].y;//确定扫描线的最小值和最大值。初始值使用第一个点的y值。
	for (int i = 1; i < points_num; i++)
	{
		if (points[i].y < scanMin)
		{
			scanMin = points[i].y;//扫描线的最小值         
		}
		if (points[i].y > scanMax)
		{
			scanMax = points[i].y;//扫描线的最大值
		}
	}

	//TODO: 以下是创建桶的代码，此时桶上不加入边
	Bucket *headBucket = new Bucket(scanMin, NULL, NULL);//建立桶的头结点

	Bucket *currentBucket = headBucket;
	for (int i = scanMin + 1; i <= scanMax; i++)//建立桶的其它结点
	{
		currentBucket->pNext = new Bucket(i, NULL, NULL);//新建一个桶结点
		currentBucket = currentBucket->pNext;//使currentBucket指向新建的桶结点	
	}

	return headBucket;
}

Bucket* Bucket::creatEdgeTable(CPoint points[], Edge edges[], int points_num, Bucket* headBucket)
{
	Bucket *currentBucket = NULL;
	Edge *currentEdge = NULL;
	for (int i = 0; i < points_num; i++)//访问每个顶点
	{
		int j = (i + 1) % points_num;//边的第二个顶点，points[i]和points[j]构成一条边

		currentBucket = headBucket;//从桶链表的头结点开始循环

		if (points[j].y > points[i].y)//若终点比起点高
		{
			while (currentBucket->scanLine != points[i].y)//在桶内寻找该边的yMin
			{
				currentBucket = currentBucket->pNext;//移到下一个桶结点
			}//跳出循环时，找到对应的桶，即为currentBucket
			edges[i].setEdge(points[i].x, points[j].y, (points[j].x - points[i].x) * 1.0 / (points[j].y - points[i].y), NULL);//将该边记入数组edges中
			addEdge(currentBucket, &edges[i]);//将该边加入桶中
		}

		if (points[j].y < points[i].y)//终点比起点低
		{
			while (currentBucket->scanLine != points[j].y)//在桶内寻找该边的yMin
			{
				currentBucket = currentBucket->pNext;//移到下一个桶结点
			}//跳出循环时，找到对应的桶，即为currentBucket
			edges[i].setEdge(points[j].x, points[i].y, (points[i].x - points[j].x) * 1.0 / (points[i].y - points[j].y), NULL);//将该边记入数组edges中
			addEdge(currentBucket, &edges[i]);//将该边加入桶中
		}
	}
	return headBucket;
}

//按照x的大小顺序将边加入桶中
void Bucket::addEdge(Bucket* currentBucket, Edge* edge)
{
	if (currentBucket->pEdge == NULL)//若当前桶结点上没有链接边结点
	{
		currentBucket->pEdge = edge;//第一个边结点直接连接到对应的桶中
	}
	else if(edge->x < currentBucket->pEdge->x)//比首结点小时
	{
		Edge *tempEdge = currentBucket->pEdge;
		currentBucket->pEdge = edge;
		edge->pNext = tempEdge;
	}
	else						//如果当前边已连有边结点
	{
		Edge *currentEdge = currentBucket->pEdge;
		while (currentEdge->pNext)
		{
			if(currentEdge->pNext->x >= edge->x && currentEdge->x < edge->x)//currentEdge的x比该边x小 且currentEdge下一个边比比该边x大时插入
			{
				Edge* tempEdge = currentEdge->pNext;
				currentEdge->pNext = edge;
				edge->pNext = tempEdge;
				return;
			}
			currentEdge = currentEdge->pNext;
		}
		//跳出循环时，说明edge->x比最后一个结点都大，所以放在最后
		currentEdge->pNext = edge;
		edge->pNext = NULL;
	}
}

main.cpp

/**
 * headBucket 是桶表头节点
 * colorref 是填充颜色
 */ 
void effectiveEdgeTableFillingAlgorithm(Bucket* headBucket ,COLORREF colorref, CDC *pDC)
{
	Edge *currentEdge = NULL, *tempEdge = NULL;
	Bucket* currentBucket = headBucket;//当前操作的桶，从第一个开始
	Bucket* tempBucket = NULL;
	//访问所有桶结点
	while(currentBucket->pNext)
	//for(currentBucket = headBucket; currentBucket != NULL; currentBucket = currentBucket->pNext)
	{
		currentEdge = currentBucket->pEdge;//首先currentEdge指向当前扫描线的第一个边

		//TODO: 以下是当前桶的绘图的代码。
		bool in = true; //设置一个bool变量in，初始值为真，用于判断当前选择像素点是否在图形内部
		tempEdge = currentEdge;
		while(tempEdge->pNext)
		{
			if (in)//若在内部则绘图
			{
				for (double x = tempEdge->x; x < tempEdge->pNext->x; x++)
				{

					pDC->SetPixelV(x, currentBucket->scanLine, colorref);
					//Sleep(1);
				}
			}
			in = !in;//in取反
			tempEdge = tempEdge->pNext;
		}

		//TODO：以下是处理下个桶的代码。即将当前桶的边处理，得出下个桶的有效边，并插入下个桶中，同时释放当前桶的资源。
		//遍历该桶
		while(currentEdge)
		{	
			if(currentEdge->yMax > currentBucket->scanLine + 1) //若满足加入条件,则将该结点进行修改并按顺序插入下一个桶
			{
				tempEdge = currentEdge;
				currentEdge = currentEdge->pNext;
				tempEdge->reUseEdge();//修改信息
				Bucket::addEdge(currentBucket->pNext, tempEdge);//插入下个桶
			}
			else//否则释放该边的资源
			{
				tempEdge = currentEdge;
				currentEdge = currentEdge->pNext;
				//if(tempEdge != NULL){ delete tempEdge; }	
			}
		}
		tempBucket = currentBucket;
		currentBucket = currentBucket->pNext;
		delete tempBucket;
	}
}