精华内容
下载资源
问答
  • 《计算机图形学边缘填充算法》由会员分享,可在线阅读,更多相关《计算机图形学边缘填充算法(63页珍藏版)》请在人人文库网上搜索。1、边缘填充算法,思路:利用求余运算代替交点排序、配对、构造填充区间。 原理:...

    《计算机图形学边缘填充算法》由会员分享,可在线阅读,更多相关《计算机图形学边缘填充算法(63页珍藏版)》请在人人文库网上搜索。

    1、边缘填充算法,思路:利用求余运算代替交点排序、配对、构造填充区间。 原理:象素点颜色值经过偶数次求余运算后保持不变,经过奇数次求余运算后变为其余数 算法: 以扫描线为中心的边缘填充算法 以边为中心的边缘填充算法,基本思想:对于每一条扫描线和每条多边形边的交点 (x1,y1),将该扫描线上交点右方的所有象素取补.对多边形的每条边做此处理,多边形的顺序随意. 该算法的优点是简单,缺点是对复杂图形,每一象素可能被访问多次,输入输出的量比较大.,边缘填充算法,以扫描线为中心的边缘填充算法,基本思想:对于每一条扫描线和每条多边形边的交 点(x1,y1),将该扫描线上交点右方的所 有象素取补.对多边形的每。

    2、条边做此处理, 多边形的顺序随意.,将当前扫描线上的所有象素着上指定颜色的补色,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,将当前扫描线上的所有象素着上指定颜色的补色,以扫描线为中心的边缘填充算法,将当前扫描线上的所有象素着上指定颜色的补色,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中。

    3、心的边缘填充算法,以扫描线为中心的边缘填充算法,以扫描线为中心的边缘填充算法,对各条扫描线循环上述处理过程。,以边为中心的边缘填充算法,原始多边形,以边为中心的边缘填充算法,初始化:将绘图窗口的背景色置为多边形颜色的补色,以边为中心的边缘填充算法,对非水平边上的每个象素点向右求余,以边为中心的边缘填充算法,以边为中心的边缘填充算法,以边为中心的边缘填充算法,该算法的优点是简单,缺点是对复杂图形,每一象素可能被访问多次,输入输出的量比较大. 栅栏填充算法 基本思想:对于每个扫描线与多边形边的交点,仅将交点与栅栏之间的象素取补.,边缘填充算法特点,栅栏填充算法,将当前扫描线上的所有象素着上指定颜色。

    4、的补色,栅栏填充算法,将当前扫描线上的所有象素着上指定颜色的补色,栅栏填充算法,将当前扫描线上的所有象素着上指定颜色的补色,栅栏填充算法,边标志算法进一步改进了栅栏算法,使得算法对每个象素仅访问一次. 边标志算法分两步进行: 对多边形边界上的象素打上边标志; 填充.,边标志算法,扫描线算法:对每条扫描线,首先计算它与扇形区域边界的交点,再把配对交点之间的像素用指定颜色填充。,Filling Ellipse Arcs,区域(种子)填充是指先将区域内的一点(种子点)赋予给定颜色,然后将颜色扩充到整个区域内的过程(染色过程). 区域:已经表示成点阵形式的象素集合,具有相同颜色.,区域填充(种子填充算。

    5、法),区域的两种表示:内点表示、边界表示. 边界表示:给位于边界上的所有象素着色,而区 域内不着色.,区域的表示,内点表示:给区域内所有象素都着上同一种颜色 (特征值),边界上pixel不着色.,要求: 区域具有一定的连通性:4连通或8连通 4连通区域:取区域内任意两点,在该区域内(不能通过区域外的点),若从其中一点出发,通过上、下、左、右 四种运动可到达另一点时,则称该区域为4连通区域.,区域连通性(1),4连通运动方向,8连通运动方向,区域连通性(2),区域连通性(3),允许从4个方向搜索下一个象素的填充算法称为是四向填充算法,允许从8个方向搜索下一个象素的填充算法称为是8向填充算法,算法。

    6、思想: 设G为一内点表示的区域,(x,y)是G内一点,以(x,y)为种子点,先将(x,y)置为newcolor,然后对(x,y)的4(或8)领域进行递归处理,逐步将整个区域G置为newcolor.,(1)递归算法,递归填充算法,初始化:种子象素入栈 第一步:栈顶象素出栈,作为种子点; 第二步:种子点被置为填充色; 第三步:按照上、下、左、右顺序检查与种子点相邻的象素:若非边界且未被填充,则入栈(8向连通区域需考虑更多相邻象素)。 若栈不空,则重复第一步。,void FloodFill4(int x, int y, int oldColor, int newColor) if (GetPixel。

    7、(x,y)=oldColor) PutPixel(x,y,newColor); FloodFill4(x,y+1,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor); FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); ,Algorithm,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,Example:,算法: (1)填充并确定种子点所在的区段; (2)将种子区段压栈; (。

    8、3)若堆栈非空,栈顶区段出栈;否则算法 结束; (4)填充并确定新的区段, 将其区段信息 压栈.,(2)扫描线算法,扫描线种子填充算法流程(1),初始化:由指定的种子象素点(x,y)生成种子(y,xl,xr),填充并入栈。 (xl,xr分别为种子点所在扫描线上多边形内部区间的左、右端点) 第一步:若种子栈空则算法终止,否则栈顶种子出栈 第二步:确定新种子:分别确定y+1,y-1扫描线上与(y,xl,xr)连通的区间;填充新区间并将新种子压入堆栈 第三步:上述过程循环执行。,扫描线种子填充算法流程(2),考虑到区域可以是凹的或有内环的,所以可能在该扫描线上出现多个填充区间,亦即需定义多个种子。,。

    9、同样考虑到凹或有孔的区域,需对扫描线y-1进行同样的处理,获得新的种子。,扫描线种子填充算法的改进思路,算法中的回溯过程并非总是必要的。,Pattern filling,用图象(pattern)填充区域,Definition of the pattern: M X N bitmaps patternij: the value of the position (i,j),Two issues,the relation of the area of the pattern to that of the primitive Relative anchor Absolute anchor write 。

    10、mode Transparent Opaque,Relative anchor,To anchor the pattern at a vertex of the primitive: (x0,y0) valuexy=pattern(x-x0)%M(y-y0)%N,Absolute anchor,To consider the entire screen as being tiled with the pattern and to think of the primitive as consisting of an outline or filled area of transparent bi。

    11、ts that let the pattern show through valuexy=patternx%My%n,write mode,Filling with a pattern: Adding extra control to the part of the scan-conversion algorithm that actually writes each pixel Write mode Doing PutPixel with foreground color at a pixel for a 1 in the pattern In transparent mode: 若为0,则。

    12、不改变屏幕上该象素的颜色(不做任何处理); In opaque mode 若为0,则用背景色显示该象素,Pattern filling without repeated scan conversion,Rectangle write To scan convert a primitive first into a rectangular work area, and then to write each pixel from that bitmap to the appropriate place in the canvas. Twice as much work as filling dur。

    13、ing scan conversion Be suitable to characters, icons and application symbols,(d) Bitmap for solid version of house icon. (e) Clearing the scene by writing background (f) Brick pattern applied to house icon (g) Writing the screen transparently with patterned house icon,An example: Writing a patterned。

    14、 object in opaque mode with two transparent writes,Thick primitives 在产生一定宽度的线条时,只需用一个“刷子”来替代单象素直线段中扫描生成的单象素即可.,线画图元的属性控制,Replicating pixels(1) (线刷子),Using more than 1 pixel for each column (or row) during scan conversion,Pixels are duplicated in column for lines with 1slope1 Pixels are duplicated in。

    15、 rows for all other lines,原理:假设直线斜率在-1,+1之间,如图(a)所示.这时可把刷子置成垂直方向图(b).首先将刷子的中点对准直线的一个端点,从该点开始,让刷子中点沿直线的轨迹往直线的另一端点平移即可“刷出”具有一定宽度的直线.如图(c).,m1,m2,(a),(b),(c),Replicating Pixels(2),缺点:(1)线的始末断总是水平或垂直的. (2)线的粗细不一样.水平和垂直线最粗,45斜线最 细. (3) 当线宽为偶数个时,绘制的线条宽度不精确.,Disadvantages,方形刷子是一个宽度为指定线宽的正方形.将正方形的中心对准直线作平移运。

    16、动即可.,The Moving Pen(方形刷子),The Moving Pen(方形刷子),Thick line drawn by tracing a rectangular pen.,该方法将会重复的写象素.为避免重复,可采用与活化边表类似的技术.,Disadvantages,Recording the spans,先算出直线的四个角点的坐标,将其顺序连接成一个四边形,再用区域填充的方法将四边形填充.,Filling Areas Between Boundaries,圆弧线宽的处理 圆弧线宽的处理与直线类似.,如虚线、实线、点划线等不同线的处理.,Line Style And Pen Style。

    展开全文
  • 计算机图形学里的经典算法,运用吊桶的思想,考虑了各种特殊情况,用C/C++实现,算法比较复杂,代码量不小。
  • 边标志填充算法----计算机图形

    千次阅读 2019-10-14 13:57:39
    缺点:对于复杂图形而言,一些像素的颜色值需反复改变多次,并且多边形外的像素处理过多,输入/输出的量比有序边表算法大得多。 边填充算法的改进——栅栏填充算法 栅栏:指的是一条与水平扫描线垂直的直线...

    边标志填充算法:

    基本原理:考虑每一条水平扫描线与每一条多边形边的交点,将该扫描线上交点右边的所有像素求补。对多边形的每条边作此处理,顺序随意。

    本算法的特点:
     优点:简单易行;
     缺点:对于复杂图形而言,一些像素的颜色值需反复改变多次,并且多边形外的像素处理过多,输入/输出的量比有序边表算法大得多。

     

    边填充算法的改进——栅栏填充算法


     栅栏:指的是一条与水平扫描线垂直的直线,栅栏位置通常取过多边形顶点且把多边形分为左右两半。

    基本原理:对于每条扫描线与多边形的交点,将交点与栅栏之间的扫描线上的像素取补。若交点位于栅栏左侧,则将交点之右至栅栏之左的所有像素取补;若交点位于栅栏右侧,则将栅栏之右至交点之左的所有像素取补。

    栅栏填充算法的特点:
    多边形外的像素处理大大减少,被重复取补的像素数目也有减少,但仍有一些像素被重复取补。
     

     

    算法评价:

    可以看到该算法思想简单,实现容易。算法既不需要初始化边表、求交点、交点排序等额外操作,也不需要使用链表、堆栈等数据结构。

     

    需要明确的关键细节问题:

    (1)   边标志算法虽然简单,但是使用时对边界的处理要格外小心,否则很容易出错。比如上下顶点之类的局部极值点,会造成标志的奇偶计数不匹配,填充时会出现“抽丝”现象,也就是扫描线上不该填充的区段被填上色,而应该填充的区段却没有填上色。

    解决方法:解决的方法是修改边的区间,将y 值大的一端顶点排除在区间之外,也就是删除这条边的终点,即假设本来线段的 y 值的取值范围为 [ 2, 9 ] ,修改后线段的 y 值的取值范围为 [ 2, 9 )。这样在计算交点时,上顶点就计算零个交点,下顶点就计算两个交点,左右顶点就计算一个交点。

    体现在本程序中则是:

    for y in range(p0.y(), p1.y()):
        i = maxy - y
        x = int(fx)
        for x1 in range(x, maxx):
            j = x1 - minx
            mat[i][j] = not mat[i][j]
        fx = fx + dx

    外层 for 循环中 ,y 的取值为 [ p0.y() , p1.y() )  .

     

    (2)   边界像素点重复的问题,多边形的边界是利用直线的生成算法依次画出的,当扫描线遇到斜率小于1的边时,容易产生重

    复的边界点,如图所示,引起标志的无序改变,从而造成填充错误。

    解决方法:解决的方法是在计算水平扫描线与多边形边的交点时,不直接使用直线的生成算法。而是不管斜率如何,都采用使 y 步增1,计算  x 值的方法,这样就能保证 一条水平扫描线与多变形的某一条边只相交于一点。

     

     

    核心代码:

    (在实施边标志填充算法通常先求出多边形所在图像区域的最小包围盒,以便缩小扫描范围,加快填充速度。)

    边标志填充算法:

    from PySide2.QtCore import *
    
    class Polygon:
        def __init__(self, vs):
            self.vertex_pts = vs
    
        def max_x(self):
            max1 = 0
            for p in self.vertex_pts:
                if p.x() > max1:
                    max1 = p.x()
            return max1
    
        def min_x(self):
            min1 = self.max_x()
            for p in self.vertex_pts:
                if p.x() < min1:
                    min1 = p.x()
            return min1
    
        def max_y(self):
            max1 = 0
            for p in self.vertex_pts:
                if p.y() > max1:
                    max1 = p.y()
            return max1
    
        def min_y(self):
            min1 = self.max_y()
            for p in self.vertex_pts:
                if p.y() < min1:
                    min1 = p.y()
            return min1
    
        def pts_sets(self):
            pts = [] #多边形像素点集
            if len(self.vertex_pts) < 3:
                return pts
            minx = self.min_x()
            miny = self.min_y()
            maxx = self.max_x()
            maxy = self.max_y()
            m = maxy - miny + 1
            n = maxx - minx + 1
    
            # 多边形最小包围盒对应的矩阵总的元素个数,这里将最小包围盒中的像素全部初始化为 False
            mat = [[False for col in range(n)] for row in range(m)]
    
            #多边形顶点数
            for k in range(len(self.vertex_pts)):
    
                # 取多边形中一条边
                if k < len(self.vertex_pts) -1 :
                    p0 = self.vertex_pts[k]
                    p1 = self.vertex_pts[k+1]
                else:
                    p0 = self.vertex_pts[k]
                    p1 = self.vertex_pts[0]
                if p0.y() > p1.y():
                    temp = p0
                    p0 = p1
                    p1 = temp
    
                print(p0,p1)
    
    
                if p0.y() != p1.y(): #非水平边
                    dx = (p1.x()-p0.x())/(p1.y()-p0.y())
                    fx = p0.x()
    
                for y in range(p0.y(), p1.y()):
                    i = maxy - y
                    x = int(fx)
                    for x1 in range(x, maxx):
                        j = x1 - minx
                        mat[i][j] = not mat[i][j]
                    fx = fx + dx
    
            for i in range(m):
                for j in range(n):
                    if mat[i][j]:
                        pts.append(QPoint(j+minx, maxy-i))
    
            return pts

    边填充算法的改进——栅栏填充算法:

    from PySide2.QtCore import *
    
    class Polygon:
        def __init__(self, vs):
            self.vertex_pts = vs
    
        def max_x(self):
            max1 = 0
            for p in self.vertex_pts:
                if p.x() > max1:
                    max1 = p.x()
            return max1
    
        def min_x(self):
            min1 = self.max_x()
            for p in self.vertex_pts:
                if p.x() < min1:
                    min1 = p.x()
            return min1
    
        def max_y(self):
            max1 = 0
            for p in self.vertex_pts:
                if p.y() > max1:
                    max1 = p.y()
            return max1
    
        def min_y(self):
            min1 = self.max_y()
            for p in self.vertex_pts:
                if p.y() < min1:
                    min1 = p.y()
            return min1
    
        def pts_sets(self):
            pts = [] #多边形像素点集
            if len(self.vertex_pts) < 3:
                return pts
            minx = self.min_x()
            miny = self.min_y()
            maxx = self.max_x()
            maxy = self.max_y()
            m = maxy - miny + 1
            n = maxx - minx + 1
            fence = int((self.max_x() - self.min_x()) / 2)
    
            # 多边形最小包围盒对应的矩阵总的元素个数,这里将最小包围盒中的像素全部初始化为 False
            mat = [[False for col in range(n)] for row in range(m)]
    
            #多边形顶点数
            for k in range(len(self.vertex_pts)):
    
                # 取多边形中一条边
                if k < len(self.vertex_pts) -1 :
                    p0 = self.vertex_pts[k]
                    p1 = self.vertex_pts[k+1]
                else:
                    p0 = self.vertex_pts[k]
                    p1 = self.vertex_pts[0]
                if p0.y() > p1.y():
                    temp = p0
                    p0 = p1
                    p1 = temp
    
                if p0.y() != p1.y(): #非水平边
                    dx = (p1.x()-p0.x())/(p1.y()-p0.y())
                    fx = p0.x()
    
                for y in range(p0.y(), p1.y()):
                    i = maxy - y
                    x = int(fx)
                    if x < fence:
                        for x1 in range(x, fence):
                            j = x1 - minx
                            mat[i][j] = not mat[i][j]
                    else:
                        for x1 in range(fence, x):
                            j = x1 - minx
                            mat[i][j] = not mat[i][j]
    
                    fx = fx + dx
    
            for i in range(m):
                for j in range(n):
                    if mat[i][j]:
                        pts.append(QPoint(j+minx, maxy-i))
    
            return pts

     

    加上UI界面实现效果:

     

    PS: 如需参考完整代码,请移步:https://download.csdn.net/download/qq_42185999/11862942   进行下载

     

    展开全文
  • 多边形三条或三条以上的线段首位顺次连接所组成的封闭图形,有凸多边形(任意两顶点间的连线均在多边形内)和凹多边形(任意两顶点间的连线有不在多边形内的部分)。 多边形在计算机中有顶点表示和点阵表

    原博文地址:http://blog.csdn.net/xiaowei_cqu/article/details/7693985

    多边形

    扫描线算法是针对计算机中多边形的显示。多边形三条或三条以上的线段首位顺次连接所组成的封闭图形,有凸多边形(任意两顶点间的连线均在多边形内)和凹多边形(任意两顶点间的连线有不在多边形内的部分)。


    多边形在计算机中有顶点表示和点阵表示两种。

    顶点表示就是用多边形的顶点序列来表示多边形。点阵表示是用位于多边形内的象素集合来表示多边形。顶点表示占内存少,几何意义强,易于进行几何变换;而点阵表示丢失了许多几何信息(如边界、顶点)。但光栅显示图形需要点阵表示形式。

    多边形的扫描转换就是把多边形的顶点表示转换为点阵表示。


    扫描转换算法

    按扫描线顺序,计算扫描线与多边形的相交区间,再用要求的颜色填充这些区间的象素。步骤如下:

    求交:计算扫描线与多边形各边的交点; 
    排序:把所有交点按x值递增顺序排序; 
    配对:第一个与第二个,第三个与第四个等等;每对交点代表扫描线与多边形的一个相交区间, 
    着色:把相交区间内的象素置成多边形颜色,把相交区间外的象素置成背景色。 

    其实很好理解,像下面的图:


    以倒数第三条扫描线为例,有6个交点,排序之后为 A,B,C,D,E,F

    然后配对:(A,B)(C,D)(E,F)也就是要填充(A,B)(C,D)(E,F)之间的部分。

    这是扫描线与一条边相交,会出现问题的地方时扫描线与两条边相交,也就是与顶点相交。比如ABCD上面那条线,如果把顶点处看做一个交点,如图,配对的结果是:(G,H)(I,J)于是(H,I)之间的部分就会被填充为背景;如果吧H看做两个交点,H1,H2。配对结果:(G,H1)(H2,I)。。。把I被看成两个交点也是不科学的,正确的应该是把H看做0个交点,I看做两个。

    总结说来,就是判断共享顶点的两个边:

    如果共享顶点的两条边分别落在扫描线的两边,交点只算一个;
    如果共享顶点的两条边在扫描线的同一边,这时交点作为零个或两个:另外两边都在下面看成0个,都在上面看成2个。
    具体实现时,只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定。

    还是上图GHI那条线,应看做G,I1,I2,J。配对结果:(G,I1)(I2,J)。

    上图所有有交点的地方:



    边相关扫描填充算法

    简单的扫描线填充算法需要一直求扫描线与多边形边的交点。但我们看上图,扫描线与最左边的那条边GA的交点坐标是呈线性关系的。也就是说如果GA的斜率是m,

    如果G的交点坐标是x1,假设A是下一条扫描线的交点,则交点就是x1+1/m。即:x(i+1)=x(i)+1/m。

    这种性质在遇到顶点的时候会有一些改变,可以通过边的相关性总结规律。简单描述为扫描线上相邻像素的点在多边形内还是多边形外,内,外的关系在遇到顶点时会发生改变。还是上面那张图:

    边相关的填充算法描述有点复杂,要维护两张表。回头再重写一章吧。


    OpenCV中的函数

    OpenCV中用 fillPoly() 函数绘制多边形。在core module的部分有所有的基本绘图函数:

    直线 line()、圆circle()、椭圆ellipse()、矩形rectangle()、填充多边形fillPoly()

    在安装目录的  OpenCV2.3.1\samples\cpp\tutorial_code\CxCore\Matrix  的文件夹下有名为  Drawing_1.cpp 的文件,有所有绘图的演示。填充多边形使用如下:

    [cpp] view plain copy
    1. void MyPolygon( Mat img )  
    2. {  
    3.   int lineType = 8;  
    4.   
    5.   /** Create some points */  
    6.   Point rook_points[1][20];  
    7.   rook_points[0][0] = Point( w/4.0, 7*w/8.0 );  
    8.   rook_points[0][1] = Point( 3*w/4.0, 7*w/8.0 );  
    9.   rook_points[0][2] = Point( 3*w/4.0, 13*w/16.0 );  
    10.   rook_points[0][3] = Point( 11*w/16.0, 13*w/16.0 );  
    11.   rook_points[0][4] = Point( 19*w/32.0, 3*w/8.0 );  
    12.   rook_points[0][5] = Point( 3*w/4.0, 3*w/8.0 );  
    13.   rook_points[0][6] = Point( 3*w/4.0, w/8.0 );  
    14.   rook_points[0][7] = Point( 26*w/40.0, w/8.0 );  
    15.   rook_points[0][8] = Point( 26*w/40.0, w/4.0 );  
    16.   rook_points[0][9] = Point( 22*w/40.0, w/4.0 );  
    17.   rook_points[0][10] = Point( 22*w/40.0, w/8.0 );  
    18.   rook_points[0][11] = Point( 18*w/40.0, w/8.0 );  
    19.   rook_points[0][12] = Point( 18*w/40.0, w/4.0 );  
    20.   rook_points[0][13] = Point( 14*w/40.0, w/4.0 );  
    21.   rook_points[0][14] = Point( 14*w/40.0, w/8.0 );  
    22.   rook_points[0][15] = Point( w/4.0, w/8.0 );  
    23.   rook_points[0][16] = Point( w/4.0, 3*w/8.0 );  
    24.   rook_points[0][17] = Point( 13*w/32.0, 3*w/8.0 );  
    25.   rook_points[0][18] = Point( 5*w/16.0, 13*w/16.0 );  
    26.   rook_points[0][19] = Point( w/4.0, 13*w/16.0) ;  
    27.   
    28.   const Point* ppt[1] = { rook_points[0] };  
    29.   int npt[] = { 20 };  
    30.   
    31.   fillPoly( img,  
    32.         ppt,  
    33.         npt,  
    34.             1,  
    35.         Scalar( 255, 255, 255 ),  
    36.         lineType );           
    37. }  

    简单来说就是定义多边形的点就可以直接绘制。

    效果如下:

    还有一个效果很炫的 Drawing_2.cpp ,里面有Text的演示

    尤其喜欢最后的效果:


    转载请注明出处:http://blog.csdn.net/xiaowei_cqu/article/details/7693985
    找不到的,代码可以在这里下载:http://download.csdn.net/detail/xiaowei_cqu/4394955


    展开全文
  • 接上文 计算机图形学 学习笔记(二):多边形扫描转换:X扫描线算法 和 改进的X扫描线算法光栅图形学算法2.6 多边形的区域填充算法区域:指已经表示成点阵样式的填充图形,是像素的集合区域填充:指将区域内的一点...

    接上文 计算机图形学 学习笔记(二):多边形扫描转换:X扫描线算法 和 改进的X扫描线算法


    光栅图形学算法

    2.6 多边形的区域填充算法

    区域:指已经表示成点阵样式的填充图形,是像素的集合

    区域填充:指将区域内的一点(常称种子点)赋予给定颜色,然后将这种颜色扩展到整个区域内的过程。

    区域可采用* 内点表示* 和 边界表示 两种表示形式。

    这里写图片描述
    内点表示:枚举出区域内部的所有像素,内部的所有像素着同一个颜色,边界像素着与内部像素不同的颜色

    边界表示:枚举出边界上的所有像素,边界上的所有像素着同一个颜色,内部像素着与边界像素不同的颜色

    区域填充算法要求区域是连通的,因为只有在连通区域中,才可能将种子点的颜色扩展到区域内的其它点。

    区域可分为 4向连通区域和 8向连通区域。

    这里写图片描述

    4向连通区域 指的是从区域上一点出发,可通过四个方向,即上下左右移动的组合,在不越出区域的前提下,到达区域内的任意像素。

    8向连通区域指的是区域内每一像素出发,可通过八个方向,即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。

    简单四连通种子填充算法(区域填充递归算法)

    种子填充算法的原理:假设在多边形区域内部有一像素已知,由此出发找到区域内的所有像素,用一定的颜色或灰度来填充。

    假设区域采用边界定义,即区域边界上所有像素均具有某个特定值,区域内部所有像素均不取这一特定值,而边界外的像素则可具有与边界相同的值。

    考虑区域的四向连通,即从区域上一点出发,可通过四个方向,即上下左右移动的组合,在不越出区域的前提下,到达区域内的任意像素。

    使用栈结构来实现简单的种子填充算法

    算法原理如下:种子像素入栈,当栈非空时重复执行如下三步操作:

    1. 栈顶元素出栈
    2. 将出栈像素置成要填充的颜色
    3. 按左,上,右,下顺序检查与栈像素相邻的四个像素,若其中某个像素不再边界且未被置成填充色,则把该像素入栈

    例子

    这里写图片描述

    一开始种子像素入栈,形成第1幅图。然后因为栈非空(因为种子像素入栈了),所以现在执行那三步操作。第一步栈顶元素出栈(现在的栈顶元素即种子像素),第二步将出栈元素置为填充色(即种子像素现在变为绿色了),形成第2幅图。然后按左上右下顺序,把1号元素入栈,形成了第3幅图。以此类推,则是种子填充算法的实现。

    种子填充算法的不足

    • 有些像素会入栈多次,降低算法效率,栈结构占空间
    • 递归执行,算法很简单,但是效率不高。区域内每一像素都引进一次递归,进/出栈,费时费内存。

      改进算法,减少递归次数,提高效率(可以采用区域填充的扫描线算法)

    多边形的扫描转换与区域填充算法小结

    基本思想不同
    - 多边形扫描转换是指将多边形的顶点表示转化为点阵表示
    - 区域填充只改变区域的填充颜色,不改变区域表示方法

    基本条件不同

    • 在区域填充算法中,要求给定区域内的一点作为种子点,然后从这一点根据连通性将新的颜色扩散到整个区域
    • 扫描转换多边形是从多边形的边界(顶点)信息出发,利用多种形式的连贯性进行填充的

    扫描转换区域填充的核心是知道多边形的边界,要得到多边形内部的像素集,有多种方法。其中扫描线算法是利用一套特殊的数据结构,避免求交,然后一条条扫描线确定。

    区域填充条件更强一些,不但知道边界,而且还知道区域内的一旦,可以利用四连通或八连通区域不断往外扩展。

    填充一个定义的区域的选择包括:

    • 选择实际区域颜色或图案填充方式
    • 选择某种颜色和图案

    这些填充选择可应用于多边形区域或用曲线边界定义的区域;此外,区域可用多种画笔、颜色和透明度参数来绘制。

    2.7 反走样算法

    对直线、圆及椭圆这些最基本元素的生成速度和显示质量的改进,在图形处理系统中具有重要的应有价值。

    但是它们生成线条具有明显的“锯齿形”即它们会发生走样现象。

    走样

    在前面,我们讲过直线转换算法,比如说 DDA,中点画线算法等。但是无论是什么直线转换算法,其实画的都不是直线,而是对直线的一种逼近,如下所示,因此会产生锯齿形。

    这里写图片描述

    “锯齿”是走样的一种形式。而走样是光栅显示的一种固有性质,产生走样现象的原因是像素本质上的离散性。(因为我是以有限的像素,去逼近包含无限点的直线的)

    走样现象

    1. 光栅图形产生的阶梯形(锯齿形
    2. 图形中包含相对微小的物体时,这些物体在静态图形中容易被丢弃或忽略(小物体由于走样而消失)
    3. 在动画序列中时隐时现,产生闪烁(因为有的时候显示,有的时候不显示)

    小物体由于走样而消失 例子:

    这里写图片描述

    简单来说,走样的产生是因为采样不足。就像如下图所示:

    这里写图片描述

    那么如何降低由于采样不足而产生的走样现象呢?(引出反走样技术)

    反走样技术

    用于减少或消除走样效果的技术,称为反走样。由于图形的走样现象对图形的质量有很大影响,几乎所有图形处理系统都要对基本图形进行反走样处理。

    直观上我们有一种解决方案:采用分辨率更高的显示设备,对解决走样现象有所帮助,因为可以使锯齿相对物体更小一些。如下所示:

    这里写图片描述

    但是该反走样方法是以4倍的存储器代价和扫描转化时间获得的,因此这个方法是不可取的。

    反走样技术涉及到某种形式的“模糊”来产生更平滑的图像。

    对于在白色背景中的黑色矩形,通过在矩形的边界附近掺入一些灰色像素,可以柔化从黑到白的尖锐变化。从远处观察这幅图像时,人眼能够把这些缓和变化的暗影融合在一起,从而看到了更加平滑的边界。如下所示:

    这里写图片描述

    主要有两种反走样方法:

    1. 非加权区域采样方法
    2. 加权区域采样方法

    非加权区域采样方法

    算法原理:根据物体的覆盖率计算像素的颜色。(覆盖率:某个像素区域被物体覆盖的比例)

    例子:显示器的背景颜色是黑色,而我要显示的图形是白色。下面做出“模糊”处理,使其产生更平滑的图像。

    这里写图片描述

    以此类推,进行计算。因为进行了颜色的灰度处理,产生了渐变的效果,所以锯齿变得平滑。

    非加权区域采样方法的两个缺点

    1. 像素的亮度与相交区域的面积成正比,而与相交区域落在像素内的位置无关,这仍然会导致锯齿效应。
    2. 直线条上沿理想直线方向的相邻两个像素有时会有较大的灰度差

    因为每个像素的权值是一样的,这是它的主要缺点。因此这个算法也被称为非加权区域采样算法。

    加权区域采样方法

    非加权区域采样方法没有考虑,亮度不仅取决于所占的面积,还需要取决于这个物体里像素中心的远近。所以介绍加权区域采样方法。

    加权区域采样方法:这种方法更适合人视觉系统对图像信息的处理方式,反走样效果更好。

    算法原理:将直线段看做是具有一定宽度的狭长矩形。当直线段与像素有相交时,根据相交区域与像素中心的距离来决定其对像素亮度的贡献(比重)。

    简单来说:直线段对一个像素亮度的贡献正比于相交区域与像素中心的距离。

    计算方法:设置相交区域面积与像素中心距离的权函数(高斯函数)反映相交面积对整个像素亮度的贡献大小,利用权函数积分求相交区域面积,用它乘以像素可设置最大亮度值,即可得到该像素实际显示的亮度值。

    上述的计算方法比较复杂,我们可采用离散计算方法

    这里写图片描述
    这里写图片描述

    展开全文
  • 计算机图形学——区域填充算法 橡皮筋效果 本次实验的环境是使用vs提供的MFC框架,在鼠标交互输入中使用橡皮筋算法来实现多边形的输入。首先定义相应变量来保存输入的数据。 int m_pNumbers; //输入点的个数 CPoint ...
  • SVG的图形填充规则通过fill-rule属性来指定。其值有nonzero(默认)和evenodd(看参考文章说还有一个inherit属性,但是我在MDN上看只有两种) fill-rule属性用于指定使用哪一种算法去判断画布上的某区域是否属于该...
  • 二、扫描线算法(Scan-Line Filling) 扫描线算法适合对矢量图形进行区域填充,只需要直到...《计算几何与图形学有关的几种常用算法》一文出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法,利用此算
  • 图形学篇:多边形有效边表填充算法

    千次阅读 多人点赞 2019-04-19 21:11:09
    点阵表示:使用大量的点进行描述,描述完成之后,得到的就是完整形态的多边形,内部已被填充,可直接针对点来进行上色 多边形的扫描转换就是从顶点表示转换到点阵表示的过程。 基础的填充多边形方式: 检查...
  •  平面区域填充算法是计算机图形学领域的一个很重要的算法,区域填充即出一个区域的边界 (也可以是没有边界,只是出指定颜色),要求将边界范围内的所有象素单元都修改成指定的颜色(也可能是图案填充)。...
  • 理解SVG的图形填充规则

    万次阅读 2012-08-09 17:11:53
    本文内容翻译自W3.org网站的SVG规范,作为自己的备忘,供SVG初学者参考。...SVG的图形填充规则通过fill-rule属性来指定。 ‘fill-rule’ 有效值:  nonzero | evenodd | inherit 默认值:
  • 二、扫描线算法(Scan-Line Filling)  扫描线算法适合对矢量图形进行区域填充,只需要直到多边形...《计算几何与图形学有关的几种常用算法》一文出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法,...
  • 1.3扫描线种子填充算法  1.1和1.2节介绍的两种种子填充算法的优点是非常简单,缺点是使用了递归算法,这不但需要大量栈空间来存储相邻的点,而且效率不高。为了减少算法中的递归调用,节省栈空间的使用,人们提出了...
  • 二、扫描线算法(Scan-Line Filling)  扫描线算法适合对矢量图形进行区域填充,只需要直到多边形区域的...《计算几何与图形学有关的几种常用算法》一文出了判断点与多边形关系的算法――扫描交点的奇偶数判断算
  • 1.3扫描线种子填充算法 1.1和1.2节介绍的两种种子填充算法的优点是非常简单,缺点是使用了递归算法,这不但需要大量栈空间来存储相邻的点,而且效率不高。为了减少算法中的递归调用,节省栈空间的使用,人们提出了...
  • 四、边界标志填充算法 在光栅显示平面上,多边形是封闭的,它是用某一边界色围成的一个闭合区域,填充是逐行进行的,即用扫描线逐行对多边形求交,在交点对之间填充。边界标志填充算法就是在逐行处理时,利用边界或...
  • 二、扫描线算法(Scan-Line Filling)  扫描线算法适合对矢量图形进行区域填充,只需要直到多边形区域的...《计算几何与图形学有关的几种常用算法》一文出了判断点与多边形关系的算法――扫描交点的奇偶数判断算

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,798
精华内容 7,519
关键字:

给复杂图形填充算法