深入浅出理解计算机图形学中的图形填充技巧（深度与广度探讨）
最编程
2024-02-13 21:02:31
...
扫描线算法：没学会。。。
2.
区域填充算法：
区域指已经表示成点阵形式的填充图形，它是象素的集合。
区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。
主要思想(类似于走迷宫)：在区域内选中一个未点亮的点，点亮它；
遍历它的上下左右(四连通法)、左上左下右上右 下(八连通法)，获取像素，没有点亮就放入队列；
把队列中所有点全部取出遍历后，填充完毕。
关键点：
首先要了解画线时候对点的选取；
|k|<1:x从起始点的坐标开始：x每次变化1 -> y变化0或1
也就是每个对应的x坐标上都有一个点；
|k|>1:y从起始点的坐标开始： y每次变化1 -> x变化0或1
也就是每个对应的y坐标都有一个点；
(1)递归方法：(只适合填充较小图形，否则递归层数太多会抛出异常)
四连通：
void CTestView::FloodFill4(CDC* pDC,int x, int y, int oldColor, int newColor)
{
//替换颜色
if (pDC->GetPixel(x, y) == oldColor )
{
pDC->SetPixel(x, y, newColor);
FloodFill4(pDC, x, y + 1, oldColor, newColor);//上
FloodFill4(pDC, x, y - 1, oldColor, newColor);//下
FloodFill4(pDC, x+1, y, oldColor, newColor);//右
FloodFill4(pDC, x-1, y , oldColor, newColor);//左
}
}
oldColor是未点亮的点的颜色即屏幕的白色：RGB(255,255,255)
newColor是想要给点点亮的颜色；
八连通：(加上左上左下右上右下四个方向)
void CTestView::FloodFill8(CDC* pDC, int x, int y, int oldColor, int newColor)
{
//替换颜色
if (pDC->GetPixel(x, y) == oldColor)
{
pDC->SetPixel(x, y, newColor);
FloodFill4(pDC, x, y + 1, oldColor, newColor);//上
FloodFill4(pDC, x, y - 1, oldColor, newColor);//下
FloodFill4(pDC, x - 1, y+1, oldColor, newColor);//左上
FloodFill4(pDC, x - 1, y-1, oldColor, newColor);//左下
FloodFill4(pDC, x + 1, y+1, oldColor, newColor);//右上
FloodFill4(pDC, x + 1, y-1, oldColor, newColor);//右下
FloodFill4(pDC, x + 1, y, oldColor, newColor);//右
FloodFill4(pDC, x - 1, y, oldColor, newColor);//左
}
}
评价：该八连通只适合填充矩形，不适合含有斜线的多边形（可能会填充到外面去 因为左上左下右上右下四个方向上的点可能在图形外）
(2)广度优先(可以填充较大图形)
四连通：
void CTestView::BFill4(CDC* pDC, int x, int y, int oldColor, int newColor)
{
CPoint a[100000];
int k = 0;//存点
int r = 0;//取点
a[0] = CPoint(x,y);
//替换颜色
while (r <= k) {
int x = a[r].x;
int y = a[r].y;
if (pDC->GetPixel( x,y) == oldColor )
{
pDC->SetPixel(x,y, newColor);
if (pDC->GetPixel(x - 1, y) == oldColor) {//左边
a[k++] = CPoint(x - 1, y);
}
if (pDC->GetPixel(x, y + 1) == oldColor ) {//上边
a[k++] = CPoint(x, y + 1);
}
if (pDC->GetPixel(x + 1, y) == oldColor ) {//右边
a[k++] = CPoint(x + 1, y);
}
if (pDC->GetPixel(x , y-1) == oldColor ) {//下边
a[k++] = CPoint(x , y-1);
}
}
r++;
}
}
评价：若点亮的点超过a数组大小会溢出，应该对k,r加判断。
八连通：
void CTestView::BFill8(CDC* pDC, int x, int y, int oldColor, int newColor)
{
int dir[8][2] = { -1,0,0,1,1,0,0,-1,-1,1,1,1,1,-1,-1,-1 };
std::queue<CPoint> Q;
if (pDC->GetPixel(x, y) == oldColor) {
pDC->SetPixel(x, y, newColor);//给该点设置新颜色
Q.push(CPoint(x, y));
}
while (!Q.empty()) {
CPoint p = Q.front();
Q.pop();
for (int i = 4; i < 8; i++) {//左上、右上、右下、左上
int tx = p.x + dir[i][0];
int ty = p.y + dir[i][1];
if (pDC->GetPixel(tx, ty) != oldColor) continue;
if (pDC->GetPixel(tx, p.y) != oldColor && pDC->GetPixel(p.x, ty) != oldColor) continue;//该点未点亮，但是它相邻的两个点都已点亮(说明可能是边界，那么该点在边界外所以不点亮)
pDC->SetPixel(tx, ty, newColor);
Q.push(CPoint(tx, ty));
}
for (int i = 0; i < 4; i++) {
int tx = p.x + dir[i][0];
int ty = p.y + dir[i][1];
if (pDC->GetPixel(tx, ty) == oldColor) {
pDC->SetPixel(tx, ty, newColor);
Q.push(CPoint(tx,ty));
}
}
}
}
其实我不知道在图形里面的未点亮的点会不会遇到相邻(特指)两个点已经被点亮，所以注释里用的“可能”是边界外的点，不过，图形里面的点就算这次没有被点亮，也可以下次作为别的点的八个方向上的点被点亮，或者不被点亮影响也不大吧，只要整体看上去图形是填充的就行。