纳金网

标题: [as3基础应用]Bresenham直线扫描算法 [打印本页]
作者: .    时间: 2013-3-20 09:31
标题: [as3基础应用]Bresenham直线扫描算法
http://boycy.webs.com/Bresenham.swf 动画地址：http://boycy.webs.com/Bresenham.swf
Bresenham算法讲的是如何将一条直线方程绘制在电脑显示屏上。
首先，我们要知道，电脑显示器是点阵构成。每个点的坐标均是整数。第二点，绘制到显示器上的直线必须是看起来连续的。这个连续的具体表现就是，如果两个个点它是连续的，那么一个点必须在另一个点的四周八个像素位置的一个。
出于这些要求，要把直线绘制到显示器上，必须将直线转换成连续的离散点（这个连续是显示器意义上的连续）。这个转换应该不是准确的，他是一种近似的装换，将直线上的点（大部分是小数）转换成近似的整数点。
现在我们试着用比较笨的方法转换下看。
直线y=x：x为1，y计算出来为1；x为2，y计算出来为2。。。那么转换好的点是(1,1),(2,2),(3,3)...因为直线比较特殊，转换出来的点均是准确的并连续的。那么我们再看一条直线。
直线y=0.5*x：x为1，y计算出来为0.5，因为需要整数，故将y四舍五入为1；x为2，y为1；x为3，y计算好四舍五入为2。。。那么转换好的点是(1,2),(2,1),(3,2)...这里出现小数，那么我们就要取近似值，进行四舍五入。四舍五入的算法是int(num+0.5)。那么我们再看一条直线。
直线y=1.5*x：x为1，y四舍五入为2，x为2，y为3，x为3，y四舍五入为5。。。出来的点是(1,2),(2,3),(3,5)...如果仔细观察这些点，发现什么？对，(2,3)和(3,5)出现了不连续，为了实现连续，我们应该在(2,4)或(3,4)补上一个点。那么出来的点就是(1,2),(2,3),(3,4),(3,5)...
以上是最笨的方法，虽然实现了绘制，可是每次都要代入直线方程，而且需要进行四舍五入，还要判断是否连续。那么，下面，我们改进这个算法。
回想直线方程通式y=kx+b，其中，k表示斜率，其物理意义，如果将x理解为时间，y理解为路程的话，那么k就是速度，其表示每增加单位时间，路程的增量。是否所有启发，我们可以通过这个将耗时耗力的乘法踢掉了。
注意理解，如果将x看成时间，y看成路程，那么，每增加一个单位时间，也就是x++，那么y就会增加k。这样，我们就能通过递推方式算出y。
拿y=0.5*x这个直线开刀。当x为1，这个第一步要代入方程算出y为0.5，通过四舍五入得出点(1,1)。然后x++得到2，原来y算出的那个0.5加上一个k（k=0.5），变成了1，得到点(2,1)，x再执行x++，y再执行y+k得到1.5，于是得到点(3,2)。是不是和上面用傻方法算出的一样呢？
不过，这个方法尚未消除判断不连续问题。
其实，如果你眼尖，或者对数字比较敏感，你会发现，如果直线的k绝对值在0和1之间，则不会发生不连续的情况。那是因为我们刚才的方法是以x作为自变量，y作为因变量，x每次均递增1，而y的增量则不明确。可是为了要连续，y增量的绝对值必须小于1，否则两点会因为y增加过猛而不连续。而y的增量正好是k。故k绝对值在0和0之间时，不会发生不连续。为了解决这个问题，我们适当选择自变量和因变量，来确保因变量每次的增量都在0和1范围内。
对于直线y=1.5*x，我们确定这个直线的自变量为y，因变量为x，x的增量为2/3（就是1/k，k原来是1.5，所以1/k是2/3）。那么y为1计算出x为2/3，四舍五入为1，得到点(1,1)，y自加为2，x增加2/3变成4/3，四舍五入为1，得到点(2,1)，以此类推。。观察发现出来的点均是连续的。
现在，我们从方程代入和连续点判断上做了优化，接下来我们来做四舍五入的优化。
对于因变量的增量限定为1以内的计算，四舍五入很大程度上都是在做无用功。比如一个值为0.2的数其增量我们规定是0.1，通过四舍五入算法int(0.2+0.5)后得出0.2四舍五入后的值是0，那么我们做一次增加增量，0.2+0.1得0.3，然后四舍五入int(0.3+0.5)为0 ，再增量，0.4，四舍五入int(0.4+0.5)得0，直到再增量为0.5，int(0.5+0.5)才为1。.int()这个运算符是强制取整，相对于加减和比较运算，这个运算开销有点大。那么我们就换一个思路，从一开始，我们就进行整数运算，将是否进位交给另外一个变量判断。对于一个整数n，在(n-0.5)到(n+0.5)（不包括）范围内的数，都将四舍五入成n。
那么对于一个数字，number它四舍五入的结果为整数inta，那么我们相信，number可以表示成(inta+b)，b的范围是[-0.5,0.5)，如果number得到了一个增量c（c是小于1的），而且b+c还是在[-0.5,0.5)范围内，那么得到增量后的number四舍五入后的结果应该还是inta；如果b+c的值大于0.5，那么得到增量后的number四舍五入后的结果应该是inta+1，同理b+c的值小于-0.5，得到增量后的number四舍五入后的结果应该是inta-1。
通过这个原理，我们可以设计一个算法。
设number是每次都要增加k的一个数，inta是number每次增加个k后四舍五入得到的整数。
k的范围是[0,1]
如果设一个b使number==inta+b+0.5
那么 b==number-inta-0.5
b的范围是[-1,0)
现在要给number加k，那么得到b’==number+k-inta-0.5
且得到number'==inta+b‘+0.5==inta+b+k+0.5
如果b+k+0.5大于0.5，那么inta+b+k+0.5四舍五入的结果为inta+1。
那么新的number'=inta+b+k+0.5=inta'-1+b+k+0.5
那么最终得到新的b''=b+k-1
如果b+k+0.5没有大于0.5，inta没有增加，那么最终得到新的b''=b+k
然后，反复迭代，从代替了直接进行四舍五入，提高了效率。
这样，我们绘制直线的优化工作就做好了
以下是代码
var datas:BitmapData=newBitmapData(550,400,false,0x000000);//位图数据
var map:Bitmap=new Bitmap(datas);//位图显示对象
this.addChildAt(map,0);
var theSize:int=5;//控制一个像素点的大小
//根据像素点的大小，在指定坐标绘制一个像素（其实是绘制一个矩形）
function drawPixel(thex:int,they:int):void
{
       varstartx:int=theSize*thex;//矩形的左上角x坐标
       varstarty:int=theSize*they;//矩形的左上角y坐标
       if(startx>400||starty>550||startx+theSize<0||starty+theSize<0)return;//如果矩形超出范围,则退出
       datas.fillRect(newRectangle(startx,starty,theSize,theSize),0xffffff);//在位图上绘制矩形
}
//根据Bresenham算法绘制直线，直线又两点式表示
functiondarwLine(x1:Number,y1:Number,x2:Number,y2:Number):void
{
       varxadd:int;//x每次的增量，实际上只有1和-1两个值
       varyadd:int;//y每次的增量
       vark:Number;//直线斜率
       vardx:int;//绘制像素的x坐标
       vardy:int;//绘制像素的y坐标
       vare:Number;//一个中间值，用来快速进行四舍五入，是算法高速的关键
       if(x2>=x1)xadd=1;//要是第一个点在第二个点的左边，那么从第一个点绘制到第二个点，x坐标应该是单调递增的
       el***add=-1;//否则就单调递减
       if(y2>=y1)yadd=1;//同理，如果第一个点在第二个点下方，那么从第一个点绘制到第二个点，y坐标是单调递增的
       elseyadd=-1;//否则单调递减
       k=(y2-y1)/(x2-x1);//算出直线斜率
       k=(k>0)?k-k);//取斜率绝对值
       dx=int(x1+0.5);//将第一个点的x坐标四舍五入，作为第一个绘制点x的坐标
       dy=int(y1+0.5);//将第一个点的y坐标四舍五入，作为第一个绘制点的y坐标
       //Bresenham算法绘制直线对斜率要求是绝对值在0和1之间，所以要对斜率进行判断，如果斜率大于1，那么需要对x和y对换对待
       if(k>1)//斜率大于1，那么把x看成y，把y看成x，这样x随着y的变化而变化
       {
              varmy:int//终点y坐标
              k=1/k;//将斜率求倒数，因为x和y对换了嘛
              e=x1-dx-0.5;//中间变量起始值。这个其中原理在最开始讲过
              my=int(y2+0.5);//求助终点坐标值
              drawPixel(dx,dy);//绘制第一个点
              while(dy!=my)//到达终点才停止循环
              {
                     dy+=yadd;//每一次循环，y都要自增一下（或自减）
                     e+=k;//中间变量加上斜率
                     if(e>=0)//如果e值超出
                     {
                            dx+=xadd;//那么因变量要增加（或减少）一个
                            e--;//e值倒退1
                     }
                     drawPixel(dx,dy);//绘制计算出来的点
              }
       }
       //一下同理，就是x和y换一下
       else
       {
              varmxx:int;
              e=y1-dy-0.5;
              mxx=int(x2+0.5);
              drawPixel(dx,dy);
              while(dx!=mxx)
              {
                     dx+=xadd;
                     e+=k;
                     if(e>=0)
                     {
                            dy+=yadd;
                            e--;
                     }
                     drawPixel(dx,dy);
              }
       }
}
/*****
****UI
**/
b1.addEventListener(MouseEvent.CLICK,bt1Click);
b2.addEventListener(MouseEvent.CLICK,bt2Click);
function bt1Click(e:Event):void
{
       theSize=int(t1.text);
       darwLine(Number(t2.text),Number(t3.text),Number(t4.text),Number(t5.text));
}
function bt2Click(e:Event):void
{
       datas.fillRect(newRectangle(0,0,550,400),0x000000);
}
【来源：互联网】
更多精彩教程，尽在web3D纳金网http://www.narkii.com/college/ 动画地址：http://boycy.webs.com/Bresenham.swf
Bresenham算法讲的是如何将一条直线方程绘制在电脑显示屏上。
首先，我们要知道，电脑显示器是点阵构成。每个点的坐标均是整数。第二点，绘制到显示器上的直线必须是看起来连续的。这个连续的具体表现就是，如果两个个点它是连续的，那么一个点必须在另一个点的四周八个像素位置的一个。
出于这些要求，要把直线绘制到显示器上，必须将直线转换成连续的离散点（这个连续是显示器意义上的连续）。这个转换应该不是准确的，他是一种近似的装换，将直线上的点（大部分是小数）转换成近似的整数点。
现在我们试着用比较笨的方法转换下看。
直线y=x：x为1，y计算出来为1；x为2，y计算出来为2。。。那么转换好的点是(1,1),(2,2),(3,3)...因为直线比较特殊，转换出来的点均是准确的并连续的。那么我们再看一条直线。
直线y=0.5*x：x为1，y计算出来为0.5，因为需要整数，故将y四舍五入为1；x为2，y为1；x为3，y计算好四舍五入为2。。。那么转换好的点是(1,2),(2,1),(3,2)...这里出现小数，那么我们就要取近似值，进行四舍五入。四舍五入的算法是int(num+0.5)。那么我们再看一条直线。
直线y=1.5*x：x为1，y四舍五入为2，x为2，y为3，x为3，y四舍五入为5。。。出来的点是(1,2),(2,3),(3,5)...如果仔细观察这些点，发现什么？对，(2,3)和(3,5)出现了不连续，为了实现连续，我们应该在(2,4)或(3,4)补上一个点。那么出来的点就是(1,2),(2,3),(3,4),(3,5)...
以上是最笨的方法，虽然实现了绘制，可是每次都要代入直线方程，而且需要进行四舍五入，还要判断是否连续。那么，下面，我们改进这个算法。
回想直线方程通式y=kx+b，其中，k表示斜率，其物理意义，如果将x理解为时间，y理解为路程的话，那么k就是速度，其表示每增加单位时间，路程的增量。是否所有启发，我们可以通过这个将耗时耗力的乘法踢掉了。
注意理解，如果将x看成时间，y看成路程，那么，每增加一个单位时间，也就是x++，那么y就会增加k。这样，我们就能通过递推方式算出y。
拿y=0.5*x这个直线开刀。当x为1，这个第一步要代入方程算出y为0.5，通过四舍五入得出点(1,1)。然后x++得到2，原来y算出的那个0.5加上一个k（k=0.5），变成了1，得到点(2,1)，x再执行x++，y再执行y+k得到1.5，于是得到点(3,2)。是不是和上面用傻方法算出的一样呢？
不过，这个方法尚未消除判断不连续问题。
其实，如果你眼尖，或者对数字比较敏感，你会发现，如果直线的k绝对值在0和1之间，则不会发生不连续的情况。那是因为我们刚才的方法是以x作为自变量，y作为因变量，x每次均递增1，而y的增量则不明确。可是为了要连续，y增量的绝对值必须小于1，否则两点会因为y增加过猛而不连续。而y的增量正好是k。故k绝对值在0和0之间时，不会发生不连续。为了解决这个问题，我们适当选择自变量和因变量，来确保因变量每次的增量都在0和1范围内。
对于直线y=1.5*x，我们确定这个直线的自变量为y，因变量为x，x的增量为2/3（就是1/k，k原来是1.5，所以1/k是2/3）。那么y为1计算出x为2/3，四舍五入为1，得到点(1,1)，y自加为2，x增加2/3变成4/3，四舍五入为1，得到点(2,1)，以此类推。。观察发现出来的点均是连续的。
现在，我们从方程代入和连续点判断上做了优化，接下来我们来做四舍五入的优化。
对于因变量的增量限定为1以内的计算，四舍五入很大程度上都是在做无用功。比如一个值为0.2的数其增量我们规定是0.1，通过四舍五入算法int(0.2+0.5)后得出0.2四舍五入后的值是0，那么我们做一次增加增量，0.2+0.1得0.3，然后四舍五入int(0.3+0.5)为0 ，再增量，0.4，四舍五入int(0.4+0.5)得0，直到再增量为0.5，int(0.5+0.5)才为1。.int()这个运算符是强制取整，相对于加减和比较运算，这个运算开销有点大。那么我们就换一个思路，从一开始，我们就进行整数运算，将是否进位交给另外一个变量判断。对于一个整数n，在(n-0.5)到(n+0.5)（不包括）范围内的数，都将四舍五入成n。
那么对于一个数字，number它四舍五入的结果为整数inta，那么我们相信，number可以表示成(inta+b)，b的范围是[-0.5,0.5)，如果number得到了一个增量c（c是小于1的），而且b+c还是在[-0.5,0.5)范围内，那么得到增量后的number四舍五入后的结果应该还是inta；如果b+c的值大于0.5，那么得到增量后的number四舍五入后的结果应该是inta+1，同理b+c的值小于-0.5，得到增量后的number四舍五入后的结果应该是inta-1。
通过这个原理，我们可以设计一个算法。
设number是每次都要增加k的一个数，inta是number每次增加个k后四舍五入得到的整数。
k的范围是[0,1]
如果设一个b使number==inta+b+0.5
那么 b==number-inta-0.5
b的范围是[-1,0)
现在要给number加k，那么得到b’==number+k-inta-0.5
且得到number&#39;==inta+b‘+0.5==inta+b+k+0.5
如果b+k+0.5大于0.5，那么inta+b+k+0.5四舍五入的结果为inta+1。
那么新的number&#39;=inta+b+k+0.5=inta&#39;-1+b+k+0.5
那么最终得到新的b&#39;&#39;=b+k-1
如果b+k+0.5没有大于0.5，inta没有增加，那么最终得到新的b&#39;&#39;=b+k
然后，反复迭代，从代替了直接进行四舍五入，提高了效率。
这样，我们绘制直线的优化工作就做好了
以下是代码
var datas:BitmapData=newBitmapData(550,400,false,0x000000);//位图数据
var map:Bitmap=new Bitmap(datas);//位图显示对象
this.addChildAt(map,0);
var theSize:int=5;//控制一个像素点的大小
//根据像素点的大小，在指定坐标绘制一个像素（其实是绘制一个矩形）
function drawPixel(thex:int,they:int):void
{
       varstartx:int=theSize*thex;//矩形的左上角x坐标
       varstarty:int=theSize*they;//矩形的左上角y坐标
       if(startx>400||starty>550||startx+theSize<0||starty+theSize<0)return;//如果矩形超出范围,则退出
       datas.fillRect(newRectangle(startx,starty,theSize,theSize),0xffffff);//在位图上绘制矩形
}
//根据Bresenham算法绘制直线，直线又两点式表示
functiondarwLine(x1:Number,y1:Number,x2:Number,y2:Number):void
{
       varxadd:int;//x每次的增量，实际上只有1和-1两个值
       varyadd:int;//y每次的增量
       vark:Number;//直线斜率
       vardx:int;//绘制像素的x坐标
       vardy:int;//绘制像素的y坐标
       vare:Number;//一个中间值，用来快速进行四舍五入，是算法高速的关键
       if(x2>=x1)xadd=1;//要是第一个点在第二个点的左边，那么从第一个点绘制到第二个点，x坐标应该是单调递增的
       el***add=-1;//否则就单调递减
       if(y2>=y1)yadd=1;//同理，如果第一个点在第二个点下方，那么从第一个点绘制到第二个点，y坐标是单调递增的
       elseyadd=-1;//否则单调递减
       k=(y2-y1)/(x2-x1);//算出直线斜率
       k=(k>0)?k-k);//取斜率绝对值
       dx=int(x1+0.5);//将第一个点的x坐标四舍五入，作为第一个绘制点x的坐标
       dy=int(y1+0.5);//将第一个点的y坐标四舍五入，作为第一个绘制点的y坐标
       //Bresenham算法绘制直线对斜率要求是绝对值在0和1之间，所以要对斜率进行判断，如果斜率大于1，那么需要对x和y对换对待
       if(k>1)//斜率大于1，那么把x看成y，把y看成x，这样x随着y的变化而变化
       {
              varmy:int//终点y坐标
              k=1/k;//将斜率求倒数，因为x和y对换了嘛
              e=x1-dx-0.5;//中间变量起始值。这个其中原理在最开始讲过
              my=int(y2+0.5);//求助终点坐标值
              drawPixel(dx,dy);//绘制第一个点
              while(dy!=my)//到达终点才停止循环
              {
                     dy+=yadd;//每一次循环，y都要自增一下（或自减）
                     e+=k;//中间变量加上斜率
                     if(e>=0)//如果e值超出
                     {
                            dx+=xadd;//那么因变量要增加（或减少）一个
                            e--;//e值倒退1
                     }
                     drawPixel(dx,dy);//绘制计算出来的点
              }
       }
       //一下同理，就是x和y换一下
       else
       {
              varmxx:int;
              e=y1-dy-0.5;
              mxx=int(x2+0.5);
              drawPixel(dx,dy);
              while(dx!=mxx)
              {
                     dx+=xadd;
                     e+=k;
                     if(e>=0)
                     {
                            dy+=yadd;
                            e--;
                     }
                     drawPixel(dx,dy);
              }
       }
}
/*****
****UI
**/
b1.addEventListener(MouseEvent.CLICK,bt1Click);
b2.addEventListener(MouseEvent.CLICK,bt2Click);
function bt1Click(e:Event):void
{
       theSize=int(t1.text);
       darwLine(Number(t2.text),Number(t3.text),Number(t4.text),Number(t5.text));
}
function bt2Click(e:Event):void
{
       datas.fillRect(newRectangle(0,0,550,400),0x000000);
}
【来源：互联网】
更多精彩教程，尽在web3D纳金网http://www.narkii.com/college/



欢迎光临 纳金网 (http://rs.narkii.com/club/) Powered by Discuz! X2.5