计算机图形学作业：多边形的扫描线种子和边填充算法

扫描线种子算法描述

在已经以颜色bcolor画出了多边形的情况下：

1. 输入多边形的顶点数组、顶点数和多边形内部的一点(x,y)，边界颜色bcolor，填充颜色ncolor。
2. 初始化：堆栈置空，将种子点(x,y)压入栈s，找出多边形顶点数组中的的最大与最小的x，y值，保存为maxx，maxy，minx，miny。
3. 栈顶元素出栈并保存在p中，并以p.y值作为当前扫描线号；否则栈s为空，算法结束。
4. 填充并确定区间范围：left=p.x, right=p.x+1。若GetPixel(left, p.y) !=bcolor且left>minx，用颜色ncolor填充(left, p.y)，left减1,重复这个过程；若GetPixel(right, p.y) !=bcolor且right< maxx，用颜色ncolor填充(right, p.y)，right加1，重复这个过程。
5. 确定新的种子点：在区间(left,right)中检查p.y-1，p.y+1扫描线。若p.y-1>miny，令y1= p.y-1，i=left+1。若i<right，执行循环：如果GetPixel(i, y1) != bcolor 且 GetPixel(i, y1) != ncolor，则令j=i+1，递增至GetPixel(j, y1) == bcolor。然后将(j-1,y1)压栈，i=j-1；直到i>=right，循环结束。同样的，若if(p.y+1<maxy)，令y1= p.y+1，i=left+1。执行与y1=y-1相似的过程。执行结束后，转入步骤（3）。

代码部分（MFC里的view类里实现的，使用栈需要添加头文件#include<iostream>）

void CSimpleDrawView::Seed_FillPolygon(int x, int y, COLORREF bcolor, COLORREF ncolor, CDC* pDC)
{
	CRect rect;
	GetClientRect(rect);
	std::stack<CPoint> s;
	CPoint p;
	int left, right;
	s.push(CPoint(x, y));
	if (fill_polynum == -1) return;
	find_maxmin_xy(fill_pts, fill_polynum1);
	while (!s.empty())
	{
		//栈顶元素出栈
		p = s.top();
		s.pop();

		//向左填充
		for (left = p.x; pDC->GetPixel(left, p.y) != bcolor&&left>minx; left--)
			pDC->SetPixel(left, p.y, ncolor);
		//向右填充
		for (right = p.x + 1; pDC->GetPixel(right, p.y) != bcolor&&right< maxx; right++)//以边界点为区间点
			pDC->SetPixel(right, p.y, ncolor);

		//在当前行的下一行寻找确定新的种子点

		if(p.y-1>miny)
		FindNewSeed(s, left, right, p.y - 1, bcolor, ncolor, pDC);
		//在当前行的上一行寻找确定新的种子点
		if(p.y+1<maxy)
		FindNewSeed(s, left, right, p.y + 1, bcolor, ncolor, pDC);
	}
}

void CSimpleDrawView::FindNewSeed(std::stack<CPoint>& s, int left, int right, int y, COLORREF bcolor, COLORREF ncolor, CDC* pDC)
{

	for (int i = left + 1; i < right; i++)
	{
		if (pDC->GetPixel(i, y) != bcolor && pDC->GetPixel(i, y) != ncolor)
		{
			int j = i + 1;
			while (pDC->GetPixel(j, y) != bcolor && j < right && pDC->GetPixel(j, y) != ncolor)
			//while (pDC->GetPixel(j, y) != bcolor && pDC->GetPixel(j, y) != ncolor)
				j++;
			i = --j;
			s.push(CPoint(j, y));
		}
	}
}

?边填充算法

在已经以颜色bcolor画出了多边形的情况下：

1. 1. 1. 输入多边形的顶点数组pts、顶点数num，边界颜色bcolor，填充颜色ncolor。
      2. 初始化：计算出多边形顶点数组中的的最大与最小的x，y值，保存为maxx，maxy，minx，miny。令i=0。
      3. 若i小于num-1，执行（4）；否则算法结束。
      4. 令p1= pts[i]，p2= pts[i+1]，如果p1.y==p2.y，i++，返回步骤（3）；如果p1.y>p2.y，两者交换。令m=(1.0 * p1.x - p2.x) / (p1.y-p2.y)，y= p1.y，x = p1.x。
      5. 如果y< p2.y：x += m，y++，且令right=maxx，若right > x，对像素(right,y)用颜色ncolor异或写操作，right--，重复这个过程直到right<=x；否则（y>=p2.y），i++，转入步骤（3）。

说明： pts为多边形点数组，num为点的数目，注意遍历的时候要看你的起点是否存了两次，即最后一个点是不是存了起点（因为多边形是闭合的）。

find_maxmin_xy(pts,num);用于找到多边形的边界，即边填充只在多边形的外接矩形区域进行，减少不必要的访问。

void CSimpleDrawView::sidefill(CPoint pts[], int num)
{
	CDC* pDC = GetDC();
	find_maxmin_xy(pts,num);
	for (int i = 0; i < num-1; i++)
	{
		/*if (i == num - 1)
		{
			sideright_xor(pts[num - 1], pts[0], pDC);
		}
		else*/
		{
			sideright_xor(pts[i], pts[i + 1], pDC);
		}
	}
}

int CSimpleDrawView::sideright_xor(CPoint p1, CPoint p2, CDC* pDC)
{
	if(p1.y==p2.y)  return 0;
	if (p1.y > p2.y)
	{
		CPoint temp;
		temp = p1;p1 = p2;p2 = temp;
	}
	double m = (1.0 * p1.x - p2.x) / (p1.y-p2.y);
	int y = p1.y;double  x = p1.x;
	while (y < p2.y)
	{
		x += m;
		y++;
		for (int right = maxx; right > x; right--)
		{
		   pDC->SetROP2(R2_NOTXORPEN);
		   pDC->SetPixel(right, y, RGB(100, 149, 237));
		}
	}
	return 1;
}

?

void CSimpleDrawView::find_maxmin_xy(CPoint p[], int num)
{
	int x1 = p[0].x, y1 = p[0].y, x2 = p[0].x, y2 = p[0].y;
	for (int i = 1; i < num; i++)
	{
		x1 = max(x1, p[i].x);
		y1 = max(y1, p[i].y);
		x2 = min(x2, p[i].x);
		y2 = min(y2, p[i].y);
	}
	maxx = x1, maxy = y1, minx = x2, miny = y2;
}