精华内容
下载资源
问答
  • 活性边表法对多边形上色 如果不知道何为活性边表法同学可以参阅: ... 我们对一个多边形进行从上至下...将即将扫描到边加入新边表新边表进行排序 每条扫描线不断向下逐行像素求交点(线段交点横坐标可以用

    活性边表法对多边形上色

    如果不知道何为活性边表法的同学可以参阅:
    https://blog.csdn.net/ZY_cat/article/details/78184336
    https://blog.csdn.net/u013044116/article/details/49737585

    我们对一个多边形进行从上至下的扫描,将每个节点的纵坐标伸展出一条扫描线,将扫描线从上至下排序,然后按照每条扫描线:
    将即将扫描到的边加入新边表
    对新边表进行排序
    每条扫描线不断向下逐行像素求交点(线段的交点的横坐标可以用原坐标-1/k得到)
    将交点排序后两两配对之后对配对的交点作为线段端点进行上色
    这样的顺序逻辑进行操作
    下面是javascript的源码:

    function drawPolygon(points){
     
        /// 下方代码用以绘制多边形
        var ET=[];
        for(var h=0;h<points.length;h++){
            addPixel(points[h][0],points[h][1]);
        }
        function cal_x(x1,x2,y1,y2){//x为较高点横坐标
            if(y1>y2){
                return x1;
            }
            else{
                return x2;
            }
        }
        function cal_dx(x1,x2,y1,y2){//斜率的倒数
            return (x1-x2)/(y1-y2);
        }
        function cal_ymax(y1,y2){
            return y1>y2? y1:y2;
        }
        function cal_ymin(y1,y2){
            return y1<y2? y1:y2;
        }
        function draw(x1,x2,y){
            for(var ia=x1;ia<x2;ia++){//左闭右开绘制线条
                addPixel(ia,y);
            }
        }
        var k=0;
        for(k=0;k<points.length-1;k++){
            if(points[k][1]!=points[k+1][1]){
                ET.push({//建立边表
                            x:cal_x(points[k][0],points[k+1][0],points[k][1],points[k+1][1]),
                            dx: cal_dx(points[k][0],points[k+1][0],points[k][1],points[k+1][1]),
                            ymax:cal_ymax(points[k][1],points[k+1][1]),
                            ymin: cal_ymin(points[k][1],points[k+1][1]),
                            is_cross:0
                })
             }
        }
        ET.push({//连接首尾顶点
            x:cal_x(points[points.length-1][0],points[0][0],points[points.length-1][1],points[0][1]),
            dx: cal_dx(points[points.length-1][0],points[0][0],points[points.length-1][1],points[0][1]),
            ymax:cal_ymax(points[points.length-1][1],points[0][1]),
            ymin: cal_ymin(points[points.length-1][1],points[0][1]),
            is_cross:0
        })
       
        ET.sort(function(a,b){return b.ymax-a.ymax}); //按照Ymax的大小降序
        var line_T=[];//建立扫描线表
        for(var i1=0;i1<points.length;i1++){
            if(line_T.indexOf(points[i1][1])>-1){}
            else{
                    line_T.push(points[i1][1]);//将该纵坐标值插入扫描线表中
            }
        }
        line_T.sort(function(a,b){return b-a});//将扫描线降序排序
        for(var p=0;p<line_T.length;p++){//逐扫描线操作
            var NET=[];//建立新边表
            console.log(line_T[p]);
            for(var d =0;d<ET.length;d++){//将ymax=扫描线高度的边加入NET表
                if(ET[d].ymax>=line_T[p]&&ET[d].ymin<line_T[p])
                {
                    NET.push(ET[d]);
                }
            }
            //求交点
            var line_c=[];//建立交点表
            for(var a1=line_T[p];a1>line_T[p+1];a1--){
                for(var s=0;s<NET.length;s++){
                    if(NET[s].is_cross==0){ 
                        NET[s].is_cross=1;
                        line_c.push(NET[s].x);
                    }
                    else{
                        NET[s].x=NET[s].x-NET[s].dx;
                        line_c.push(NET[s].x);
                    }
                }
                line_c.sort(function(a,b){return a-b});//将交点坐标升序排列
                for(var u=0;u<line_c.length;u=u+2){
                    draw(Math.round(line_c[u]),Math.round(line_c[u+1]),a1);
                }
                line_c=[];
                NET.sort(function(a,b){return b.ymax-a.ymax});
            }
        }
    }
      
    
    
    
    展开全文
  • 一、定义边的数据结构1、边的ymax2、边的底端x坐标3、斜率的倒数1/m4、指向下条边的指针二、多边形边表(ET)1、与x轴平行的边不计入2、多次相交的点记录方式如下:边表具体...:三、活动边表(AET)从多边形的ymin开始...

    一、定义边的数据结构

    1、边的ymax

    2、边的底端x坐标

    3、斜率的倒数1/m

    4、指向下条边的指针

    二、多边形边表(ET)

    1、与x轴平行的边不计入

    2、多次相交的点记录方式如下:

    bc46d7ecd58aa74d00e632f3cc28f142.png

    边表具体记录方式如图:

    7ee018f871e1312d9f6e5fa3bf8c87a8.png

    三、活动边表(AET)

    从多边形的ymin开始,步长为1向上扫描。

    活动边表记录了扫描线与多边形的相交情况。若当前的的y到达了活动边表内某一边的ymax,把该边删除。若当前的y处有新的边信息,把新边加入。然后重新排序,填充。

    具体活动边表更新过程:

    (1)开始y=1:

    d8e58f1b41eaf5dfda20c0d275482c51.png

    (2)对保留下来的每个记录,用Xi+1/m代替Xi:

    a736c417ca1688b626ab201123928eca.png

    (3)使yi+1,以便进入下一轮循环。当y=2时,ET表为空,所以不需要ET表加入AET表。此时上图中x=4和x=6.5,将他们之间的点填上像素。由于y=2,此时没有达到y=3和y=5,所以不必删除节点。

    (4)再让Xi+1/m代替Xi,得到:

    93b9246146d3cc871d74b4d1ee5ff5d8.png

    (5)使yi=3,此时他的边表不为空,所以将其ET表加入,得到:

    472bd8fbd39af3568749794f168ab882.png

    注意按照xi的升序排列。将Xi=2,至Xi=7之间填上颜色。

    (6)由于此时yi=3,而第一个节点的yi=3,所以去掉此节点。

    d9279e6533734f6d9e7260635c9aa310.png

    (7)再用Xi+1/m代替Xi,得到:

    6b8d634cc44273b73894f2eca79de67c.png

    (8)yi=4,重复继续

    参考:https://blog.csdn.net/wodownload2/article/details/52154207

    展开全文
  • 一、定义边的数据结构1、边的ymax2、边的底端x坐标3、斜率的倒数1/m4、指向下条边的指针二、多边形边表(ET)1、与x轴平行的边不计入2、多次相交的点记录方式如下:边表具体...:三、活动边表(AET)从多边形的ymin开始...

    一、定义边的数据结构

    1、边的ymax

    2、边的底端x坐标

    3、斜率的倒数1/m

    4、指向下条边的指针

    二、多边形边表(ET)

    1、与x轴平行的边不计入

    2、多次相交的点记录方式如下:

    2ad4a9ec3f8deb3bbbca1ea598b2aaca.png

    边表具体记录方式如图:

    3fdeb6a483f0bc925a13f82dc0bdffc9.png

    三、活动边表(AET)

    从多边形的ymin开始,步长为1向上扫描。

    活动边表记录了扫描线与多边形的相交情况。若当前的的y到达了活动边表内某一边的ymax,把该边删除。若当前的y处有新的边信息,把新边加入。然后重新排序,填充。

    具体活动边表更新过程:

    (1)开始y=1:

    21acff2eeee6a60d656de3ef85ccbb3c.png

    (2)对保留下来的每个记录,用Xi+1/m代替Xi:

    813232146be6f47145046c4bfd95f33b.png

    (3)使yi+1,以便进入下一轮循环。当y=2时,ET表为空,所以不需要ET表加入AET表。此时上图中x=4和x=6.5,将他们之间的点填上像素。由于y=2,此时没有达到y=3和y=5,所以不必删除节点。

    (4)再让Xi+1/m代替Xi,得到:

    887e43b23b275a1994a8c298894a67aa.png

    (5)使yi=3,此时他的边表不为空,所以将其ET表加入,得到:

    a1466cd5988439e365af2a70b6c74854.png

    注意按照xi的升序排列。将Xi=2,至Xi=7之间填上颜色。

    (6)由于此时yi=3,而第一个节点的yi=3,所以去掉此节点。

    3b46f43dda71b1fe2b49f8c521ff94d3.png

    (7)再用Xi+1/m代替Xi,得到:

    3b8429e9c0fa113360b722fa2cb7f3d3.png

    (8)yi=4,重复继续

    参考:https://blog.csdn.net/wodownload2/article/details/52154207

    展开全文
  • (1)假定多边形的顶点已知 (2)基本思想:按扫描线从下到上扫描,一条一条确定区域内的像素 (3)步骤: ①求交。计算扫描线与多边形各的交点。 ②排序。把所有交点按x值的递增顺序排序。x1、x2、x3、x4、...

    一、基本扫描线填充算法基础知识

    (1)假定多边形的顶点已知

    这里写图片描述

    (2)基本思想:按扫描线从下到上扫描,一条一条确定区域内的像素

    (3)步骤:

       ①求交。计算扫描线与多边形各边的交点。
       ②排序。把所有交点按x值的递增顺序排序。x1、x2、x3、x4、x5、x6……
       ③配对。[x1, x2],[ x3, x4] , [x5, x6]……每对交点代表扫描线与多边形的一个相交区间。
       ④填色。把相交区间内的像素置成多边形的颜色,把相交区间外的像素置成背景色。
    

    (4)虽然以上步骤思想简单,但存在诸多问题。

      问题①交点刚好是多边形的顶点。
      问题②大量的求交运算。
      问题③无用的求交运算
      问题④交点排序
    

    二、解决问题

    (1)解决问题一。交点是顶点。极大值计数0次是为了防止区域扩大。

    这里写图片描述

    (2)解决问题二。大量求交运算。采用增量法。

    当前扫描线合某边交点x坐标与下一条扫描线和这条边交点x坐标的关系。

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

    (3)解决问题三。无用的求交运算。

    P3P4和扫描线6相交,和扫描线7不想交,所以,7以上的扫描线都不用和P3P4求交。

    这里写图片描述

    (4)解决以上问题,我们采用以下数据结构。

    ①活性边表AET

    活性边:和当前扫描线有交点的边。

    活性边表的结点的数据结构:(与新边表结点的数据结构相同)

    这里写图片描述

    结点的更新:

    这里写图片描述

    具体实例:

    这里写图片描述

    则扫描线6的活性边表:(注意x坐标递增)

    这里写图片描述

    则扫描线7的活性边表:(注意x由增量得到,极大值计数为0)

    这里写图片描述

    ②新边表NET

    为了方便活性边表的建立与更新,为每一条扫描线建立一个新边表NET,存放在该扫描线第一次出现的边。也就是说,若某边的较低端点为Ymin,则该边就放在扫描线Ymin的新边表中。

    例如,还是此图。

    这里写图片描述

    各扫描线的新边表如下:

    这里写图片描述

    三、算法小结

    优点:对每个像素只访问一次。

    缺点:数据结构复杂,表的维护排序开销大。

    展开全文
  • 题意:给定空间中n个点,求这n个点形成凸包表面的多边形个数。 增量法求解:首先任选4个点形成一个四面体,然后每次加一个点,分两种情况: 1> 在凸包内,则可以跳过 2> 在凸包外,找到从这个点可以"看见"面S...
  • 这两张表部分内容是重复,而且“新边表”在很多情况下都是一张稀疏表,如果能对其进行改进,避免出现两张表,就可以节省存储空间,同时省去从“边表”生成“新边表开销,同时也省去了用“新边表”维护“活动...
  • HNOI2019 多边形 polygon

    2019-04-08 18:00:00
    根据样例及打猜个结论,每一步一定可以连一条到n的边,这个结论也很好证 然后可以把多边形分成若干区间,这些区间形成一棵树。具体划分方法很简单,就是用一些现有点和中间所有构成的多边形缩成一个区间,这...
  • 三、改进扫描线填充算法  扫描线填充算法原理和实现都很简单,但是因为要...这两张表部分内容是重复,而且“新边表”在很多情况下都是一张稀疏表,如果能对其进行改进,避免出现两张表,就可以节省
  • 这两张表部分内容是重复,而且“新边表”在很多情况下都是一张稀疏表,如果能对其进行改进,避免出现两张表,就可以节省存储空间,同时省去从“边表”生成“新边表开销,同时也省去了用“新边表”维护“活动...
  • 【图像处理】相关扫描线填充算法

    万次阅读 多人点赞 2012-07-03 19:12:54
    接着上篇博文《 多边形的扫描转换》 ...边相关扫描线填充算法需要建立两张表:新边表(New Edge Table,NET)和 活动边表(Active Edge Table,AET) 新边表 NET 记录多边形除水平边外的所有
  • 接着上篇博文《多边形的扫描转换》 ...边相关扫描线填充算法需要建立两张表:新边表(New Edge Table,NET)和活动边表(Active Edge Table,AET) 新边表 NET 记录多边形除水平边外的所有的边,记录在没...
  • 这个算法其实很复杂,实现...下面AET为活性边表,NET存储新边表 1.定义数组,变量 class AET//定义AET表,不论是AET还是NET表用都是这个AET类,因为里面内容都是一样 { public float x; public floa...
  • 接着上篇博文《 多边形的扫描转换》 转载请注明出处:... ...边相关扫描线填充算法需要建立两张表:新边表(New Edge Table,NET)和 活动边表(Active Edge Table,AET) ...新边表 NE
  • 然后基于该二维多边形各内角及各长度在多边形内插入新的离散点, 再将多边形内离散点三角网格化;最后用移动最小二乘近似法将破洞附近点拟和成曲面,以此求出插入点高度值,这样就得到了在三维空间中网格数据...
  • 扫描线填充算法

    2019-12-23 21:11:51
    介绍 用水平扫描线从上到下扫描由点线段构成多段构成的多边形。 每根扫描线与多边形各边产生一系列交点。...新边表: 代码(使用数组) import numpy as np from PIL import Image from PIL impo...
  • 本文实例为大家分享了python扫描线填充算法,供大家参考,具体...新边表: 代码(使用数组) import numpy as np from PIL import Image from PIL import ImageDraw from PIL import ImageFont array = np.ndarray
  • 3.9 凸多边形的判定和内法线确定 168 3.10 凹多边形分割 172 3.11 三维裁剪 172 3.12 三维中点分割算法 175 3.13 三维Cyrus-Beck算法 177 3.14 Liang-Barsky三维裁剪 181 3.15 齐次坐标裁剪 185 3.15.1 ...
  • // 多边形的边保存在数组edges中 // 像素的颜色可以使用函数cv->MySetPixel(int x, int y, int color)设置 // 使用扫描线算法扫描转换多边形 struct ET { Edge * head,*move; //设定两个指针,一个可...

空空如也

空空如也

1 2 3
收藏数 46
精华内容 18
关键字:

多边形的新边表