图形学--扫描线种子填充算法

算法描述：
种子填充算法原理和程序都很简单, 但由于多次递归, 费时、费内存, 效率不高。
为了减少递归次数, 提高效率可以采用扫描线种子填充算法。

算法的基本过程如下: 当给定种子点 (x, y) 时, 首先填充种子点所在扫描线上的位于给定区域的一个区段, 然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段, 并依次保存下来。反复这个过程, 直到填充结束。

/**
 * begin_point 是起始点
 * boundaryColor 是边界色
 * fillColor 是填充色
 * */
void scanLineSeedFillingAlgorithm(CPoint begin_point, COLORREF boundaryColor, COLORREF fillColor, CDC* pDC)
{
	std::stack<CPoint> stack;//使用STL自带的栈容器
	stack.push(begin_point);//将起点先入栈
	CPoint* currentPoint = NULL;//当前操作的点
	int x_left = 0, x_right = 0;

	while (!stack.empty())//栈不空时进行循环
	{
		currentPoint = &stack.top();//访问栈顶元素
		stack.pop();//删除栈顶元素
		pDC->SetPixelV(*currentPoint, fillColor);//填充颜色

		x_left = fillThisLine(currentPoint->x - 1, currentPoint->y, boundaryColor, fillColor, false, pDC) + 1;
		x_right = fillThisLine(currentPoint->x + 1, currentPoint->y, boundaryColor, fillColor, true, pDC) - 1;
		int tempY = currentPoint->y;
		searchNewLineSeed(&stack, x_left, x_right, tempY + 1, boundaryColor, fillColor, pDC);
		searchNewLineSeed(&stack, x_left, x_right, tempY - 1, boundaryColor, fillColor, pDC);
	}
}

/**
 * x 是该点横坐标
 * y 是该点纵坐标
 * boundaryColor 是边界色
 * fillColor 是填充色
 * sign是填充标志，当sign是false时，向左扫描；当sign是true时，向右扫描。
 * */
int fillThisLine(int x, int y, COLORREF boundaryColor, COLORREF fillColor, BOOL sign, CDC* pDC)
{
	COLORREF currentColor = pDC->GetPixel(x, y);
	
	if (sign == false)//当sign是false时，向左扫描。
	{
		while (currentColor != boundaryColor)//当当前颜色不是边界线颜色时进行循环，否则跳出循环。
		{
			
			pDC->SetPixelV(x, y, fillColor);//向左填充颜色
			currentColor = pDC->GetPixel(--x, y);//获取左侧颜色
		}
	}
	else//当sign是true时，向右扫描。
	{
		while (currentColor != boundaryColor)//当当前颜色不是边界线颜色时进行循环，否则跳出循环。
		{
			pDC->SetPixelV(x, y, fillColor);//向右填充颜色
			currentColor = pDC->GetPixel(++x, y);//获取右侧颜色
		}
	}
	return x;
}

/**
 * stack是栈指针
 * x_left 是左边界
 * x_right 是右边界
 * y 是当前扫描线
 * boundaryColor 是边界色
 * fillColor 是填充色
 */ 
void searchNewLineSeed(std::stack<CPoint> *stack, int x_left, int x_right, int y,
	COLORREF boundaryColor, COLORREF fillColor, CDC* pDC)
{
	BOOL findNewSeed = false;
	for(; x_left <= x_right; x_left++)
	{
		if(pDC->GetPixel(x_left, y) != boundaryColor && pDC->GetPixel(x_left, y) != fillColor)
		{
			findNewSeed = true;
			break;
		}
	}
	if(findNewSeed)
	{
		stack->push(CPoint(x_left, y));
	}
}