活性边表法对多边形上色
如果不知道何为活性边表法的同学可以参阅：

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、边的ymax
2、边的底端x坐标
3、斜率的倒数1/m
4、指向下条边的指针
二、多边形边表（ET）
1、与x轴平行的边不计入
2、多次相交的点记录方式如下：
边表具体记录方式如图：
三、活动边表（AET）
从多边形的ymin开始，步长为1向上扫描。
活动边表记录了扫描线与多边形的相交情况。若当前的的y到达了活动边表内某一边的ymax，把该边删除。若当前的y处有新的边信息，把新边加入。然后重新排序，填充。
具体活动边表更新过程：
（1）开始y=1：
（2）对保留下来的每个记录，用Xi+1/m代替Xi：
（3）使yi+1，以便进入下一轮循环。当y=2时，ET表为空，所以不需要ET表加入AET表。此时上图中x=4和x=6.5，将他们之间的点填上像素。由于y=2，此时没有达到y=3和y=5，所以不必删除节点。
（4）再让Xi+1/m代替Xi，得到：
（5）使yi=3，此时他的边表不为空，所以将其ET表加入，得到：
注意按照xi的升序排列。将Xi=2，至Xi=7之间填上颜色。
（6）由于此时yi=3，而第一个节点的yi=3，所以去掉此节点。
（7）再用Xi+1/m代替Xi，得到：
（8）yi=4，重复继续
参考：https://blog.csdn.net/wodownload2/article/details/52154207

一、定义边的数据结构
1、边的ymax
2、边的底端x坐标
3、斜率的倒数1/m
4、指向下条边的指针
二、多边形边表（ET）
1、与x轴平行的边不计入
2、多次相交的点记录方式如下：
边表具体记录方式如图：
三、活动边表（AET）
从多边形的ymin开始，步长为1向上扫描。
活动边表记录了扫描线与多边形的相交情况。若当前的的y到达了活动边表内某一边的ymax，把该边删除。若当前的y处有新的边信息，把新边加入。然后重新排序，填充。
具体活动边表更新过程：
（1）开始y=1：
（2）对保留下来的每个记录，用Xi+1/m代替Xi：
（3）使yi+1，以便进入下一轮循环。当y=2时，ET表为空，所以不需要ET表加入AET表。此时上图中x=4和x=6.5，将他们之间的点填上像素。由于y=2，此时没有达到y=3和y=5，所以不必删除节点。
（4）再让Xi+1/m代替Xi，得到：
（5）使yi=3，此时他的边表不为空，所以将其ET表加入，得到：
注意按照xi的升序排列。将Xi=2，至Xi=7之间填上颜色。
（6）由于此时yi=3，而第一个节点的yi=3，所以去掉此节点。
（7）再用Xi+1/m代替Xi，得到：
（8）yi=4，重复继续
参考：https://blog.csdn.net/wodownload2/article/details/52154207

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



（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的新边表中。



例如，还是此图。





各扫描线的新边表如下：





三、算法小结



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



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