中点划线法

  原理是这样的,看下图:

【注意:一个方格是一个像素,像素坐标按中心计算,看见两个大绿点儿没?】

  由给定的(x0,y0),(x1,y1)算出直线L的一般描述式_F(x,y)=ax+by+c=0。直线的取向并不止上图一种,不同取向的处理略有不同(正负加减的区别而已),下面内容都按上图情况,代码里也集中注释这一块儿。

  (x0,y0)既定,先考察(x0+1,Ym),即(x0+1,y0-0.5)点相对直线L的上下位置关系,确切说是相对(x0+1,Yline)的上下位置关系,用的是高中解析几何:_Fm=F(x0+1,y-0.5)=a(x0+1)+b(y0-0.5)+c,通过_Fm正负做推论:

(_Fm>0且已知b>0)-->(ym>yline)-->该x坐标下,中点在直线上方,因此像素点往下取整

(_Fm<0且已知b>0)-->(ym<yline)-->该x坐标下,中点在直线下方,因此像素点往上取整

用流程图描述算法:

【_2Fm是算法细节,将前面含0.5的项转化为整数】

贴上算法的c语言实现:

View Code
void drawLine_m(int x0_int,int y0_int,int x1_int,int y1_int){
    int x0_x1_int=x1_int-x0_int;
    int y0_y1_int=y1_int-y0_int;
    if((x0_x1_int>0?x0_x1_int:-x0_x1_int)>(y0_y1_int>0?y0_y1_int:-y0_y1_int)){
        //保证x0,y0在直线左端,作为线头
            if(x0_int>x1_int){
                int temp=x0_int;
                x0_int=x1_int;
                x1_int=temp;
                temp=y0_int;
                y0_int=y1_int;
                y1_int=temp;
            }
        //x0,y0,x1,y1确定下来,接下来可以计算a,b,c了,因为下面代码都默认x0,y0为左端点。    
        //a=y0-y1,b=x1-x0,c=x0y1-x1y0
            int a=y0_int-y1_int;
            int b=x1_int-x0_int;
            int c=x0_int*y1_int-x1_int*y0_int;
            int _2a=a+a;
            int _2b=b+b;
            int _2c=c+c;
            //也可以定位pt_write的初始位置了。
            char*pt_write=pt_memBuffer+(x0_int<<2)+y0_int*bytes_w;
            *pt_write=0xff;
            if(y0_int>y1_int){
                //误写成+b,划线结果竟也不差
                int _2Fm=_2a*x0_int+_2b*y0_int+(_2a-b+_2c);
                for(int x=x0_int+1;x<=x1_int;x++){//中点划线法从x0+1处开始描点。
                    //pt_write要线性推移,_2Fm也要线性推移
                    //之所以用线性递增,是为了避免乘法运算——毕竟它与x,y是线性关系,就更要利用
                    if(_2Fm>0){//(a>0,_2Fm>0)-->(xm>xline)此时中点落在直线下面,或者说直线在中点上面。y--
                        _2Fm+=-_2b;//_2Fm(x)向_2Fm(x+1)转变
                        pt_write+=-bytes_w;    //显存指针上移一行
                    }
                    //下面两句是x递增引起的基本递增部分,不受中点上下关系影响。
                    pt_write+=4;//显存指针水平向右移动一个像素
                    _2Fm+=_2a;//_2Fm(x)向_2Fm(x+1)转变------_2Fm(x)指x横坐标处中点代入ax+by+c的值的2倍。
                    *(pt_write)=0xff;//默认是蓝色
                }
            }
            //直线往右下方走
            else{
                int _2Fm=_2a*x0_int+_2b*y0_int+(_2a+b+_2c);
                for(int x=x0_int+1;x<=x1_int;x++){
                    if(_2Fm<0){//此时中点落在直线上面,y递增了
                        _2Fm+=_2b;
                        pt_write+=bytes_w;    
                    }
                    //这是x递增引起的基本递增部分,不受中点上下关系影响。
                    pt_write+=4;
                    _2Fm+=_2a;
                    //pt_write要线性推移,Fm也要线性推移
                    //之所以用线性递增,是为了避免乘法运算——毕竟它与x,y是线性关系,就更要利用
                    *(pt_write)=0xff;
                }
            }
    }
    else{
    //保证x0,y0在直线上端
            if(y0_int>y1_int){
                int temp=x0_int;
                x0_int=x1_int;
                x1_int=temp;
                temp=y0_int;
                y0_int=y1_int;
                y1_int=temp;
            }
        //x0,y0,x1,y1确定下来,可以计算a,b,c了,因为下面代码都默认x0,y0在直线上端。    
            int a=y0_int-y1_int;
            int b=x1_int-x0_int;
            int c=x0_int*y1_int-x1_int*y0_int;
            int _2a=a+a;
            int _2b=b+b;
            int _2c=c+c;
            //也可以计算pt_write了。
            char*pt_write=pt_memBuffer+(x0_int<<2)+y0_int*bytes_w;
            if(x1_int>x0_int){
                //误写成+b,划线结果竟也不差
                int _2Fm=_2a*x0_int+_2b*y0_int+(a+_2b+_2c);
                for(int y=y0_int+1;y<=y1_int;y++){
                    //pt_write要线性推移,Fm也要线性推移
                    //之所以用线性递增,是为了避免乘法运算——毕竟它与x,y是线性关系,就更要利用
                    if(_2Fm>0){//(_2Fm>0,a<0)-->(xm<xline),此时中点落在直线左面,x++                        _2Fm+=_2b;
                        _2Fm+=_2a;//其实是x++带来_2Fm增加_2a
                        pt_write+=4;//x++带来pt_write+4
                    }
                    //这是x递增引起的基本递增部分,不受中点上下关系影响。
                    pt_write+=bytes_w;
                    _2Fm+=_2b;
                    *(pt_write)=0xff;
                }
            }
            //直线往左下方走
            else{
                int _2Fm=_2a*x0_int+_2b*y0_int+(-a+_2b+_2c);
                for(int y=y0_int+1;y<=y1_int;y++){
                    //pt_write要线性推移,Fm也要线性推移
                    //之所以用线性递增,是为了避免乘法运算——毕竟它与x,y是线性关系,就更要利用
                    if(_2Fm<0){//(_2Fm<0,a<0)-->(xm>xline),此时中点落在直线右面,x--
                        _2Fm-=_2a;//x--造成_2Fm-=_2a
                        pt_write-=4;//x--造成pt_write-=4
                    }
                    //这是x递增引起的基本递增部分,不受中点上下关系影响。
                    pt_write+=bytes_w;
                    _2Fm+=_2b;
                    *(pt_write)=0xff;
                }
            }
    }
}

 在网上见到的最通俗的入门讲解,竟是一个大学的课件:

http://course.cug.edu.cn/21cn/%BC%C6%CB%E3%BB%FA%CD%BC%D0%CE%D1%A7/Chapter2/CG_Txt_2_008.htm

原文地址:https://www.cnblogs.com/weiweishuo/p/2953037.html