扫描线种子多边形填充算法(MFC）

void CCGPainterView::ScanLineFill(CDC* pDC, CPoint startPoint, COLORREF fillCol, COLORREF boundaryCol)

{

	//Write your boundary fill algorithm here.

	// 定义堆栈

	CArray<CPoint, CPoint>Stack;

	CPoint fillPoint = startPoint;

	COLORREF currentCol = pDC->GetPixel(startPoint);

	// 最左点，最右点

	int xl, xr;

	// 标志位

	bool spanNeedFill;

	// 种子点

	CPoint pt;

	Stack.RemoveAll();// 设置堆栈为空

	pt.x = fillPoint.x;

	pt.y = fillPoint.y;

	Stack.Add(pt);// 种子点压入堆栈

	while (Stack.GetSize() != 0)

	{

		pt = Stack[Stack.GetSize() - 1];// 取出种子点

		Stack.RemoveAt(Stack.GetSize() - 1);// 堆栈减短

		fillPoint.y = pt.y;

		fillPoint.x = pt.x;

		// 从种子开始向右填充

		while (pDC->GetPixel(fillPoint.x, fillPoint.y) == currentCol)

		{

			pDC->SetPixelV(fillPoint, fillCol);

			fillPoint.x++;

		}

		xr = fillPoint.x - 1;

		fillPoint.x = pt.x - 1;

		// 从种子开始向左填充

		while (pDC->GetPixel(fillPoint.x, fillPoint.y) == currentCol)

		{

			pDC->SetPixelV(fillPoint, fillCol);

			fillPoint.x--;

		}

		xl = fillPoint.x + 1;

		// 处理上一条扫描线和下一条扫描线

		for (int I = 0; I < 2; I++)

		{

			fillPoint.x = xl;

			if (I == 0) fillPoint.y = fillPoint.y + 1;

			else fillPoint.y = fillPoint.y - 2;

			while (fillPoint.x < xr)

			{

				spanNeedFill = FALSE;

				while (pDC->GetPixel(fillPoint.x, fillPoint.y) == currentCol)

				{

					spanNeedFill = TRUE;

					fillPoint.x++;

				}// 待填充区搜索完毕

				if (spanNeedFill)

				{// 右端点作为种子入栈

					pt.x = fillPoint.x - 1;

					pt.y = fillPoint.y;

					Stack.Add(pt);

					spanNeedFill = FALSE;

				}

				// 继续向右检查以防遗漏

				while (pDC->GetPixel(fillPoint.x, fillPoint.y) != currentCol && fillPoint.x < xr)

					fillPoint.x++;

			}// 上一条扫描线上检查完毕

		}

	}

}

void CCGPainterView::ScanLineFillConvert(CDC* pDC, CPoint startPoint, COLORREF fillCol, COLORREF boundaryCol)

{

	/* 定义结构体用于活性边表 AET 和新边表 NET*/

	typedef struct XET

	{

		double x;

		double dx, ymax;

		XET* next;

	}AET, NET;

	//CPoint *ThePolygon.m_Vertex;

	int vertNum = ThePolygon.m_VerticeNumber;

	/* 计算最高点 y 的坐标，扫描线扫到 y 的最高点就结束 */

	int MaxY = ThePolygon.m_Vertex[0].y;

	int MinY = ThePolygon.m_Vertex[0].y;

	int i;

	for (i = 1; i < vertNum; i++) {

		if (ThePolygon.m_Vertex[i].y > MaxY)

			MaxY = ThePolygon.m_Vertex[i].y;

		if (MinY > ThePolygon.m_Vertex[i].y)

			MinY = ThePolygon.m_Vertex[i].y;

	}

	/* 初始化 AET 表，这是一个有头结点的链表 */

	AET* pAET = new AET;

	pAET->next = NULL;

	/* 初始化 NET 表，这也是一个有头结点的链表，头结点的 dx，x，ymax 都初始化为 0*/

	NET* pNET[1024];

	for (i = 0; i <= MaxY; i++) {

		pNET[i] = new NET;

		pNET[i]->dx = 0;

		pNET[i]->x = 0;

		pNET[i]->ymax = 0;

		pNET[i]->next = NULL;

	}

	/* 扫描并建立 NET 表 */

	for (i = MinY; i <= MaxY; i++) {

		/*i 表示扫描线，扫描线从多边形的最底端开始，向上扫描 */

		for (int j = 0; j < vertNum; j++)

			/* 如果多边形的该顶点与扫描线相交，判断该点为顶点的两条直线是否在扫描线上方

			 * 如果在上方，就记录在边表中，并且是头插法记录，结点并没有按照 x 值进行排序，毕竟在更新 AET 的时候还要重新排一次

			 * 所以 NET 表可以暂时不排序

			*/

			if (ThePolygon.m_Vertex[j].y == i) {

				/* 笔画前面的那个点 */

				if (ThePolygon.m_Vertex[(j - 1 + vertNum) % vertNum].y > ThePolygon.m_Vertex[j].y) {

					NET* p = new NET;

					p->x = ThePolygon.m_Vertex[j].x;

					p->ymax = ThePolygon.m_Vertex[(j - 1 + vertNum) % vertNum].y;

					p->dx = double((ThePolygon.m_Vertex[(j - 1 + vertNum) % vertNum].x - ThePolygon.m_Vertex[j].x)) / double((ThePolygon.m_Vertex[(j - 1 + vertNum) % vertNum].y - ThePolygon.m_Vertex[j].y));

					p->next = pNET[i]->next;

					pNET[i]->next = p;

				}

				/* 笔画后面的那个点 */

				if (ThePolygon.m_Vertex[(j + 1 + vertNum) % vertNum].y > ThePolygon.m_Vertex[j].y) {

					NET* p = new NET;

					p->x = ThePolygon.m_Vertex[j].x;

					p->ymax = ThePolygon.m_Vertex[(j + 1 + vertNum) % vertNum].y;

					p->dx = double((ThePolygon.m_Vertex[(j + 1 + vertNum) % vertNum].x - ThePolygon.m_Vertex[j].x)) / double((ThePolygon.m_Vertex[(j + 1 + vertNum) % vertNum].y - ThePolygon.m_Vertex[j].y));

					p->next = pNET[i]->next;

					pNET[i]->next = p;

				}

			}

	}

	/* 建立并更新活性边表 AET*/

	for (i = MinY; i <= MaxY; i++) {

		/* 更新活性边表 AET，计算扫描线与边的新的交点 x，此时 y 值没有达到临界值的话 */

		NET* p = pAET->next;

		while (p) {

			p->x = p->x + p->dx;

			p = p->next;

		}

		/* 更新完以后，对活性边表 AET 按照 x 值从小到大排序 */

		AET* tq = pAET;

		p = pAET->next;

		tq->next = NULL;

		while (p) {

			while (tq->next && p->x >= tq->next->x)

				tq = tq->next;

			NET* s = p->next;

			p->next = tq->next;

			tq->next = p;

			p = s;

			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;

			NET* s = p->next;

			p->next = q->next;

			q->next = p;

			p = s;

			q = pAET;

		}

		/* 配对填充颜色 */

		p = pAET->next;

		while (p && p->next) {

			for (float j = p->x; j <= p->next->x; j++) {

				pDC->SetPixel(static_cast<int>(j), i, fillCol);

			}

			p = p->next->next;

		}

	}

}