图形学种子填充算法

一、实验目标1.了解基于种子填充算法的基本思想；2.掌握基于种子填充算法的算法实现；3.掌握栈的使用。

二、实验内容本次实验主要是实现递归种子填充算法、简单种子填充算法、扫描线种子填充算法以及区域图案填充算法。

种子填充算法原理简述：在开始介绍种子填充算法之前，首先也介绍两个概念，就是“4-连通算法”和“8-连通算法”。

既然是搜索就涉及到搜索的方向问题，从区域内任意一点出发，如果只是通过上、下、左、右四个方向搜索到达区域内的任意像素，则用这种方法填充的区域就称为四连通域，这种填充方法就称为“4-连通算法”。

如果从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下全部八个方向到达区域内的任意像素，则这种方法填充的区域就称为八连通域，这种填充方法就称为“8-连通算法”。

种子填充算法采用的边界定义是区域边界上所有像素均具有某个特定的颜色值，区域内部所有像素均不取这一特定颜色，而边界外的像素则可以具有和边界相同的颜色值。

程序从（x，y）开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点，然后检测相邻位置，以确定它们是否边界色和填充色，若不是，就填充该相邻点。

这个过程延续到已经检测完边界范围内的所有像素为止。

扫描线种子填充算法原理简述：当给定种子点(x, y)时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个区段的范围[xLeft, xRight]，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。

反复这个过程，直到填充结束。

扫描线种子填充算法可由下列四个步骤实现：(1)初始化一个空的栈用于存放种子点，将种子点(x, y)入栈；(2)判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y是当前的扫描线；(3)从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。

《计算机图形学实验》报告2016年春季学期实验四:种子点填充算法Seed Filling实验时间：2016年9月底实验地点：实验目的：掌握使用opengl 的种子点填充算法，观察改变参数对生成图形的改变(改变点的位置、颜色等)如果要填充的区域是以图像元数据方式给出的，通常使用种子填充算法进行区域填充。

种子填充算法的核心是一个递归算法，都是从指定的种子点开始，向各个方向上搜索，逐个像素进行处理，直到遇到边界。

种子填充算法常用四连通域和八连通域技术进行填充操作。

从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。

用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。

从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。

用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。

算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。

程序代码：使用的运行环境是vc++6.0#include <glut.h>#include <fstream>typedef float Color[3];//获取像素点的颜色void getpixel(GLint x, GLint y, Color color) {glReadPixels(x, y, 1, 1, GL_RGB, GL_FLOAT, color); //OPENGL自带}//画点函数void setpixel(GLint x, GLint y) {glBegin(GL_POINTS);glVertex2f(x, y);glEnd();}//比较颜色是否相等int compareColor(Color color1, Color color2) {if (color1[0] != color2[0] || color1[1] != color2[1] || color1[2] != color2[2]) { return 0; }else { return 1; }}void boundaryFill4(int x, int y, Color fillColor, Color boarderColor) {Color interiorColor;getpixel(x, y, interiorColor);if (compareColor(interiorColor, fillColor) == 0 && compareColor(interiorColor, boarderColor) == 0) { setpixel(x, y);boundaryFill4(x + 1, y, fillColor, boarderColor);boundaryFill4(x - 1, y, fillColor, boarderColor);boundaryFill4(x, y + 1, fillColor, boarderColor);boundaryFill4(x, y - 1, fillColor, boarderColor);}}void boundaryFill8(int x, int y, Color fillColor, Color boarderColor) {Color interiorColor, a, b, c, d;getpixel(x, y, interiorColor);getpixel(x + 1, y, a);getpixel(x, y - 1, b);getpixel(x, y + 1, c);getpixel(x - 1, y, d);int i = 0;if (compareColor(a, boarderColor) == 1) i++;if (compareColor(b, boarderColor) == 1) i++;if (compareColor(c, boarderColor) == 1) i++;if (compareColor(d, boarderColor) == 1) i++;if (i <= 1) {if (compareColor(interiorColor, fillColor) == 0 && compareColor(interiorColor, boarderColor) == 0) {setpixel(x, y);boundaryFill8(x+1,y,fillColor,boarderColor);boundaryFill8(x-1,y,fillColor,boarderColor);boundaryFill8(x,y+1,fillColor,boarderColor);boundaryFill8(x,y-1,fillColor,boarderColor);boundaryFill8(x-1,y+1,fillColor,boarderColor);boundaryFill8(x-1,y-1,fillColor,boarderColor);boundaryFill8(x+1,y+1,fillColor,boarderColor);boundaryFill8(x+1,y-1,fillColor,boarderColor);}}}void polygon() {glBegin(GL_LINE_LOOP);glLineWidth(5);//此处修改坐标，绘制多边形glVertex2f(100, 150);glVertex2f(150, 200);glVertex2f(200, 200);glVertex2f(200, 160);glEnd();}void display(void) {Color fillColor = {0.0, 1.0, 1.0};//填充颜色Color boarderColor = {0.0, 1.0, 0.0};//边界颜色glClear(GL_COLOR_BUFFER_BIT);glViewport(0, 0, 500, 500);glColor3fv(boarderColor);polygon();glColor3fv(fillColor);//boundaryFill4(150, 150, fillColor, boarderColor);//设置起点坐标及颜色boundaryFill8(120, 160, fillColor, boarderColor);glFlush();}int main(int argc, char **argv) {glutInit(&argc, argv);glutInitDisplayMode(GLUT_SINGLE | GLUT_RED);glutInitWindowSize(500, 500);glutInitWindowPosition(100, 100);glutCreateWindow("BoundaryFill1");glClearColor(1, 1, 1, 0.0);glMatrixMode(GL_PROJECTION);//投影模型gluOrtho2D(0.0, 500.0, 0.0, 500.0);glutDisplayFunc(display);glutMainLoop();return 0;}实验结果：（更改颜色）（更改形状）。

图形填充之种⼦填充算法编译器：VS2013算法：在图形内选择⼀个点为种⼦，然后对这个种⼦四⽅位坐标未着⾊的⼊栈，出栈便着⾊，如此重复，等到栈内为空，则着⾊完成代码：1 #include "stdafx.h"2 #include<stdio.h>3 #include"graphics.h"4 #include<stdlib.h>5 #include<stack>67using namespace std;89//定义结构体存储像素坐标10struct Point11 {12int x;13int y;14 };1516//函数声明17void Boundaryfilling(Point a[], int n);18void judgecolor(int x, int y, stack<int> &sx, stack<int> &sy);1920int main()21 {22int gdriver = DETECT, gmode, n, i;2324 printf("please input number of point:\n");25 scanf_s("%d", &n);2627 Point *p=(Point *)malloc(n*sizeof(Point)); //动态分配内存2829 printf("please input point :\n");30for (i = 0; i < n; i++)31 scanf_s("%d%d", &p[i].x, &p[i].y);3233 initgraph(&gdriver, &gmode, "");3435 setcolor(BLUE);36 setbkcolor(BLACK);3738//画出多边形39for (i = 0; i < n-1; i++)40 line(p[i].x, p[i].y, p[i + 1].x, p[i + 1].y);4142 Boundaryfilling(p, n);4344 system("pause");45 closegraph();4647return0;48 }4950void Boundaryfilling(Point a[], int n)51 {52 stack<int> sx,sy;53int x=0 , y=0 ,x0,y0,i;5455for (i = 0; i < n; i++)56 {57 x += a[i].x;58 y += a[i].y;59 }6061 x = x / (n-1);62 y = y / (n-1);6364 sx.push(x);//x坐标⼊栈65 sy.push(y);//y坐标⼊栈6667while (!sx.empty()) //判断栈是否为空68 {69 x0 = sx.top();70 y0 = sy.top();7172 putpixel(sx.top(), sy.top(), YELLOW); //栈顶元素着⾊73 sx.pop();//栈顶元素出栈74 sy.pop();//栈顶元素出栈7576 judgecolor(x0 - 1, y0, sx, sy);//左边点77 judgecolor(x0 + 1, y0, sx, sy);//右边点78 judgecolor(x0, y0 - 1, sx, sy);//下边点79 judgecolor(x0, y0 + 1, sx, sy);//上边点80 }81 }8283//判断该像素是否没有着⾊84void judgecolor(int x, int y,stack<int> &sx,stack<int> &sy) 85 {86if (getpixel(x, y) == BLACK)87 {88 sx.push(x);89 sy.push(y);90 }91 }结果：。

《计算机图形学》实验报告(实验二：图形填充算法)一、实验目的及要求用两种方法做图形的填充算法！二、理论基础1.边填充算法对于每一条扫描线和每条多边形的交点（x1,y1），将该扫描线上的交点右方的所有像素取补。

2.种子填充算法利用栈来实现种子填充算法。

种子像素入栈，当栈非空时重复执行如下步骤：将栈顶像素出栈，将出栈像素置成多边形色，按左，上，右，下顺序检查与出栈像素相邻的四个像素，若其中某个像素不再边界且未置成多边形，则把该像素入栈！三、算法设计与分析1、边填充算法void CEdge_mark_fillView::OnDraw(CDC* pDC){CEdge_mark_fillDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);int d[500][500]={0};int inside;int x,y;Bresenham(80,101,100,400,d);Bresenham(100,300,290,400,d);Bresenham(292,400,382,50,d);Bresenham(380,50,202,150,d);Bresenham(200,150,82,101,d);for(y=0;y<500;y++){inside=0;for(x=0;x<500;x++){if(d[x][y]==1)if(d[x+1][y]!=1){inside=!(inside);}if(inside!=0)pDC->SetPixel(x,y,12);}}}2、种子填充int x=299,y=51;COLORREF oldcolor;COLORREF newcolor;oldcolor=RGB(256,256,256);newcolor=RGB(123,123,123);pDC->MoveTo (40,40);pDC->LineTo (80,40);pDC->LineTo (70,80);pDC->LineTo (40,40);FloodFill(51,51,RGB(255,255,255),RGB(0,0,255));pDC->LineTo (40,40);void CMyView::FloodFill(int x,int y,COLORREF oldcolor,COLORREF newcolor) {CDC* pDC;pDC=GetDC();if(pDC->GetPixel(x,y)==oldcolor){pDC->SetPixel(x,y,newcolor);FloodFill(x,y-1,oldcolor,newcolor);FloodFill(x,y+1,oldcolor,newcolor);FloodFill(x-1,y,oldcolor,newcolor);FloodFill(x+1,y,oldcolor,newcolor);}四、程序调试及结果的分析1、2、四、实验心得及建议由于很多不会，所以这次没能按时当堂完成，下来花了不少时间才弄出来，第二种尤其比较麻烦，在同学的帮助下才做出来了。

填充（Fill）相关知识点填充（Fill）是一种常见的计算机图形学技术，用于在图像或物体的内部或边界区域中填充颜色或纹理。

填充技术在许多领域中被广泛应用，如图像处理、计算机辅助设计（CAD）和计算机游戏开发等。

本文将介绍填充相关的知识点，从基本原理到常见算法，让读者对填充技术有一个全面的了解。

基本原理填充技术的基本原理是通过某种规则或算法，在给定的区域内部或边界上填充颜色或纹理。

这个区域可以是一个简单的几何形状，如矩形或圆形，也可以是一个复杂的多边形。

填充通常从区域内部的某个点开始，按照一定的规则或算法进行扩散，直到填充满整个区域。

基本算法以下是一些常见的填充算法：扫描线填充算法扫描线填充算法是一种基于扫描线的填充方法。

它通过将扫描线与区域的边界进行比较，确定扫描线与区域的交点，并根据规则填充扫描线上的像素。

该算法的优点是简单易懂，并且适用于任意形状的区域。

边界填充算法边界填充算法是一种基于区域边界的填充方法。

它通过检测区域的边界像素，并根据规则填充区域内部的像素。

该算法的优点是填充效果清晰，但对于复杂的区域边界可能会存在一些问题。

种子填充算法种子填充算法是一种基于种子点的填充方法。

它通过选择一个种子点作为起始点，并按照一定的规则或算法进行扩散填充。

种子填充算法适用于复杂的区域填充，但可能存在堆栈溢出的问题。

填充的应用领域填充技术在许多领域中都有广泛的应用，以下是其中一些常见的应用领域：图像处理在图像处理中，填充技术可以用于图像的增强、修复和合成等方面。

例如，可以使用填充技术修复图像中的缺陷、填充图像的边界以及合成多个图像。

计算机辅助设计（CAD）在计算机辅助设计中，填充技术可以用于填充图形对象的内部或边界，以增加图形的真实感和细节。

例如，可以使用填充技术填充建筑物的内部、道路的纹理以及地形的颜色。

计算机游戏开发在计算机游戏开发中，填充技术可以用于填充游戏场景的地形、角色的纹理以及特效的颜色。

通过使用填充技术，可以使游戏画面更加精美和逼真。

种子填充算法
填充算法是随机化的有益的近似算法中的经典例子，用它来解决最大问题可以产生出理想的解决方案。

种子填充算法作为该算法的一种，经常被用来解决贪婪的最大化问题或者寻优，在有限的时间内求解传统最大化目标函数的最优解。

种子填充算法是一种常用的函数字符串优化技术，能以有限的步骤实现最大化随机化优化，在计算图形和调度任务中常用种子填充算法。

主要包括：
1.根据求解的问题，选择最优解种子。

种子是随机产生的群体或者求解器方程，用于准确确定最佳参数；
2.利用种子初始化函数字符串，以较小的步骤完成最大化优化，扩展函数字符串；
3.根据优化的状态和步骤，重新选择种子来改变最大化的结果；
4.重复多步优化，可以得到不同的最优解，对于优化准确率很高。

种子填充算法的优势在于准确地得到期望解，比其它采用搜索的近似解决办法更加精确，且由于经过多次记录，每次重播都能产生一样的最优解。

另外，由于每次迭代中用到种子，可以在不影响目标函数的性能情况下改变最终的优化结果。

种子填充算法目前在理论上和实际应用中都得到了广泛的使用，如求解细胞自动机的模拟、排列调度问题、视觉语义地图等，所有这些问题都是可行空间有限，而且受限于时间和空间，在这些情况下种子填充算法可以有效提高解决问题的效率。