登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

聊天机器

Chatbot's private blog

 
 
 

日志

 
 

Bresenham直线算法  

2010-08-05 14:21:15|  分类: 程序理论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

网上没有找到完整的介绍,很多都是错误。

自己推导了出来,作个备份

绝对原创!作者:聊天机器

 

BresenHam直线算法 - 启 - 聊天机器

  

如图所示,通过判断yyi 的距离d1 以及 y yi1 的距离d2 两者的大小,判断下一点y的位置。

假如d2 > d1 ,则下一点的y在上面的一格,否则则仍然在下一点的一格。

例如:

 

左边是经过的判断,右边是实际描点。这个图是CorelDraw正规画出来的,所以可以根据肉眼判断。

 

BresenHam直线算法 - 启 - 聊天机器

 

 

起始点A 此时描点(00

 

B点,此时x 1 假设 y 实际为 y1

由于由肉眼可以看出, y1 0 > 1 y1

所以描点(11

 

C点,此时x 2 假设 y 实际高度为y2.

同样肉眼看出,y2 1 > 2 y2

所以描点(22

 

D点,此时 x 3,假设y实际高度为y3

肉眼看出,y3 2 < 3 y3

所以描点(32

 

 

同时举例

 

BresenHam直线算法 - 启 - 聊天机器

 

BresenHam直线算法 - 启 - 聊天机器

  

 

公式推导过程:

 

假设y ax + b 为直线方程。

由于我们知道 起点(x1y1 以及 终点(x2y2

那么,设

dx = x2 – x1 

dy = y2 – y1

 

同时,直线有4象限方向,这里就只讨论一个象限的。所以保证 dx > 0 通俗点说,就是直线从左向右画的。(假如dx < 0 把起点跟终点互换一下就是了,简单)

 

那么 a = dy / dx

     b = y1 – a * x1 = y1 – dy / dx * x1

 

x xi 时,那么,判断 yi 在上方还是在下方,就只要判断 d1 – d2 是否大于0。假如大于0,则yi yi 1

 

d1- d2 = dy / dx * xi + b – yi – (yi + 1 – dy / dx * xi + b )     // yi 就是当前描的y点位置

 

 

两边同时乘以 dx 。由于保证dx 大于0,则d1 – d2 的符号没有受到影响

同时去掉括号,合并同类项

 

 

=> 2*dy * xi + 2*b* dx – 2*yi*dx - dx

 

b y1 – a * x1 = y1 – dy / dx * x1 代入公式

 

=2 * dy * xi + 2y1 * dx – 2*dy*x1 – 2*yi*dx

 

由于dy y1dxx1都是已经知道的

那么假设 p 2*y1*dx – 2*dy*x1 – dx        // 这样做还可以大大减少运算量

 

那么,只要判断 p + 2 *dy * xi – 2 * dx * yi 是否大于0就可以了

 

程序实现:// 要注意方向

     void DrawLine(int x1, int y1, int x2, int y2, char c)

     {

         int dx,dy,x,y,p,const1,const2,inc,tmp;

         dx = x2 - x1;

         dy = y2 - y1;

         if(dx*dy>=0)

              inc=1;

         else

              inc=-1;

         if(abs(dx)>abs(dy))

         {

              if(dx<0)

              {

                   tmp=x1;

                   x1=x2;

                   x2=tmp;

                   tmp=y1;

                   y1=y2;

                   y2=tmp;

                   dx=-dx;

                   dy=-dy;

              }

              if(dy>=0)
              {
                    p = 2*y1*dx - 2*dy*x1 - dx;
                    const1=2*dy;
                    const2=2*dx;
              }
              else
              {
                    p = -2*y1*dx + 2*dy*x1 - dx;
                    const1=-2*dy;
                    const2=-2*dx;
              }

              x=x1;

              y=y1;

              SetPixel(x,y,c);

 

              while(x<x2)

              {

                   x++;

 

                   if( p+const1*x - const2*y > 0 )

                   {

                       y+=inc;

                   }

                   SetPixel(x,y,c);

              }

       }

else

{

       // y 代替x 就是了

       …………..

      //  这里省略代码

}

}

 

 

 

  

 

PS:牛×的不是程序员,牛×的是数学家。

不要说数学家是疯子,否则,通过直接代替的话,现实社会就是:一群疯子把全世界的正常人玩弄在鼓掌之中。

 

8月13日更改了一下中间点稍为偏移的问题

 

  评论这张
 
阅读(581)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018