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;
		}
	}
}