OpenEdv-开源电子网

 找回密码
 立即注册
正点原子全套STM32/Linux/FPGA开发资料,上千讲STM32视频教程免费下载...
查看: 20269|回复: 32

Bresenham算法画线、画圆

[复制链接]

10

主题

86

帖子

2

精华

中级会员

Rank: 3Rank: 3

积分
491
金钱
491
注册时间
2012-2-11
在线时间
8 小时
发表于 2013-1-5 14:02:16 | 显示全部楼层 |阅读模式

 以前我都没注意在LCD上画线、画圆,这两天想在LCD画线、画圆,就找资料找到了Bresenham算法,还找了一些分析文档,觉得好就分享给大家,知道的高手不要拍砖~
废话少说看图、看资料:

先看程序(程序分析自己看资料):

/***********************************************************
* 函数名称:LCD_DrawLine
* 函数功能:LCD画线函数
*           入口参数: x1,y1(起点坐标)x2,y2(终点坐标)c(颜色)  
*   出口参数:无
***********************************************************/

// 交换整数 a 、b 的值   
__inline void swap_int(u16 *a, u16 *b)  
{   
    *a ^= *b;   
    *b ^= *a;   
    *a ^= *b;   
}   
 
// Bresenham's line algorithm   
 
void LCD_DrawLine(u16 x1, u16 y1, u16 x2, u16 y2, u16 c)  
{       
    u16 dx =abs( x2 - x1), // 水平距离  
        dy =abs( y2 - y1), // 垂直距离  
        yy = 0;         // 角度是否大于45°标志
 
 int ix ,   
        iy,   
        cx ,   
        cy ,   
        n2dy,   
        n2dydx ,   
        d ;
    if(dx < dy)  // 当斜率大于 1 时,dx、dy 互换, 即角度大于45°
    {   
        yy = 1;              // 设置标志位 
        swap_int(&x1, &y1);  // 交换坐标 
        swap_int(&x2, &y2);   
        swap_int(&dx, &dy);   
    }       
    ix = (x2 - x1) > 0 ? 1 : -1; // 判断是否加1还是减一   
    iy = (y2 - y1) > 0 ? 1 : -1;   
    cx = x1;  //  x初值 
    cy = y1;  //  y初值 
    n2dy = dy * 2;       // 求要比较的各个差值
    n2dydx = (dy - dx) * 2;   
    d = dy * 2 - dx;    

// 如果直线与 x 轴的夹角大于45度   
    if(yy) 
    {  
        while(cx != x2) // 计数是否达到终点 
        {   
            if(d < 0) 
            {   
                d += n2dy;   
            }  
            else  
            {   
                cy += iy;   
                d += n2dydx;   
            }   
            LCD_DrawPoint( cy, cx, c); // 画点  
            cx += ix;   
        }   
    } 
 
// 如果直线与 x 轴的夹角小于45度   
    else  
    {  
        while(cx != x2)  
        {   
            if(d < 0) 
            {   
                d += n2dy;   
            } 
            else  
            {   
                cy += iy;   
                d += n2dydx;   
            }   
            LCD_DrawPoint( cx, cy, c);   
            cx += ix;   
        }   
    }   
}  

/**********************************************************
* 函数名称:LCD_DrawRectangle
* 函数功能:LCD画矩形函数
*           入口参数: x1,y1(对角线起点坐标)x2,y2(对角线终点坐标)color(颜色)  
*   出口参数:无
***********************************************************/

void LCD_DrawRectangle(u16 x1, u16 y1, u16 x2, u16 y2, u16 color)
{
 LCD_DrawLine(x1,y1,x2,y1,color);
 LCD_DrawLine(x1,y1,x1,y2,color);
 LCD_DrawLine(x1,y2,x2,y2,color);
 LCD_DrawLine(x2,y1,x2,y2,color);
}

/**********************************************************
* 函数名称:LCD_Drawcircle
* 函数功能:在指定位置画一个指定大小的圆
*           入口参数: (x,y)-(中心点坐标)r(半径)
*                     fill(为是否填充)   c(颜色)  
*   出口参数:无
***********************************************************/
  
__inline void draw_circle_8( u16 xc, u16 yc, u16 x, u16 y, u16 c)  
 {   
     // 参数 c 为颜色值   
     LCD_DrawPoint( xc + x, yc + y, c);   
     LCD_DrawPoint( xc - x, yc + y, c);   
     LCD_DrawPoint( xc + x, yc - y, c);  
     LCD_DrawPoint( xc - x, yc - y, c);   
     LCD_DrawPoint( xc + y, yc + x, c);  
     LCD_DrawPoint( xc - y, yc + x, c);   
     LCD_DrawPoint( xc + y, yc - x, c);   
     LCD_DrawPoint( xc - y, yc - x, c);   
 }      
//Bresenham's circle algorithm   
void LCD_Drawcircle( u16 xc, u16 yc, u16 r, u16 fill, u16 c) 
 {   
     // (xc, yc) 为圆心,r 为半径   
     // fill 为是否填充   
     // c 为颜色值      
     // 如果圆在图片可见区域外,直接退出   
  
    int x = 0, y = r, yi, d;   
        d = 3 - 2 * r;

     if(xc + r < 0 || xc - r >= 240 || yc + r < 0 || yc - r >= 320)  
     { 
         return; 
     }    
     if(fill) 
     {   
         // 如果填充(画实心圆)   
         while(x <= y)  
         {   
             for(yi = x; yi <= y; yi ++)   
             { 
                 draw_circle_8(xc, yc, x, yi, c);   
             } 
             if(d < 0)  
             {   
                 d = d + 4 * x + 6;   
             }  
             else  
             {   
                 d = d + 4 * (x - y);   
                 y --;   
             }   
  
             x++;   
         }   
     }  
     else  
     {   
         // 如果不填充(画空心圆)   
         while (x <= y)  
         {   
             draw_circle_8(xc, yc, x, y, c);   
             if(d < 0)  
             {   
                 d = d + 4 * x + 6;   
             }  
             else  
             {   
                 d = d + 4 * (x - y);   
                 y --;   
             }   
             x ++;   
         }   
     }   
 }  




 



Bresenham分析.doc

74.5 KB, 下载次数: 1739

Bresenham直线算法与画圆算法.doc

179.5 KB, 下载次数: 2623

Bresenham算法.pdf

193.82 KB, 下载次数: 2172

TFTLCD_2.zip

450.9 KB, 下载次数: 1668

多努力一点点,少遗憾一点点!!!
正点原子逻辑分析仪DL16劲爆上市
回复

使用道具 举报

530

主题

11万

帖子

34

精华

管理员

Rank: 12Rank: 12Rank: 12

积分
165536
金钱
165536
注册时间
2010-12-1
在线时间
2117 小时
发表于 2013-1-5 14:10:31 | 显示全部楼层
回复 支持 反对

使用道具 举报

10

主题

86

帖子

2

精华

中级会员

Rank: 3Rank: 3

积分
491
金钱
491
注册时间
2012-2-11
在线时间
8 小时
 楼主| 发表于 2013-1-5 16:30:57 | 显示全部楼层
回复【2楼】正点原子:
谢谢分享
---------------------------------
原子哥!向你看齐~~
多努力一点点,少遗憾一点点!!!
回复 支持 反对

使用道具 举报

36

主题

1105

帖子

5

精华

论坛大神

Rank: 7Rank: 7Rank: 7

积分
2201
金钱
2201
注册时间
2012-2-8
在线时间
35 小时
发表于 2013-1-5 17:04:47 | 显示全部楼层

谢谢分享!
论坛里面貌似比较少人去学习画线和画圆算法的原理,

Bresenham 算法最精妙的地方在于它的迭代的思想, 把算法的时间复杂度按一定比例地降低. 不仅在GUI中可以运用, 在一些控制算法中也是非常有意义的. 这也是数学迷人的地方, 呵呵.


对于画线算法介绍的比较好的在 wiki 上: http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

对于画圆算法, 我这里也有份资料介绍的比较好的, 在附件里

之前找过这方面的资料, 记得网上还一有篇关于画圆算法的论文, 开始以为很神奇, 分析完后发现它和一般的算法相比根本就没有重大的改进, 做着一样的事情, 反而把分析搞的相当复杂, 简直就是扯蛋. 看着实在无语 ...

bresenham画圆算法-推荐.doc

48 KB, 下载次数: 1390

https://github.com/roxma
回复 支持 反对

使用道具 举报

10

主题

86

帖子

2

精华

中级会员

Rank: 3Rank: 3

积分
491
金钱
491
注册时间
2012-2-11
在线时间
8 小时
 楼主| 发表于 2013-1-5 19:32:38 | 显示全部楼层
回复【4楼】Pony279:

谢谢分享!论坛里面貌似比较少人去学习画线和画圆算法的原理, 
Bresenham 算法最精妙的地方在于它的迭代的思想, 把算法的时间复杂度按一定比例地降低. 不仅在GUI中可以运用, 在一些控制算法中也是非常有意义的. 这也是数学迷人的地方, 呵呵.
对于画线算法介绍的比较好的在 wiki 上: http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
对于画圆算法, 我这里也有份资料介绍的比较好的, 在附件里之前找过这方面的资料, 记得网上还一有篇关于画圆算法的论文, 开始以为很神奇, 分析完后发现它和一般的算法相比根本就没有重大的改进, 做着一样的事情, 反而把分析搞的相当复杂, 简直就是扯蛋. 看着实在无语 ...
---------------------------------
呵呵!谢谢分享啊~~
多努力一点点,少遗憾一点点!!!
回复 支持 反对

使用道具 举报

3

主题

59

帖子

0

精华

初级会员

Rank: 2

积分
104
金钱
104
注册时间
2012-12-25
在线时间
3 小时
发表于 2013-1-5 21:50:03 | 显示全部楼层
xue xi le!! zan!
回复 支持 反对

使用道具 举报

6

主题

123

帖子

1

精华

金牌会员

Rank: 6Rank: 6

积分
1279
金钱
1279
注册时间
2012-5-27
在线时间
200 小时
发表于 2013-2-7 21:29:01 | 显示全部楼层
这个真的很好,我看了一遍后,今天专门重新搜索了一遍,又看一遍,好的东西需要多次细细品味,才能品出其中的精华来。
赞一个
回复 支持 反对

使用道具 举报

14

主题

27

帖子

0

精华

初级会员

Rank: 2

积分
103
金钱
103
注册时间
2013-4-17
在线时间
0 小时
发表于 2013-6-19 16:04:33 | 显示全部楼层
谢谢分享噶。
回复 支持 反对

使用道具 举报

34

主题

805

帖子

4

精华

论坛大神

Rank: 7Rank: 7Rank: 7

积分
1865
金钱
1865
注册时间
2011-3-29
在线时间
140 小时
发表于 2013-6-19 17:02:08 | 显示全部楼层
回复【4楼】Pony279:
---------------------------------
有没有研究过凸多边形填充算法?三角形的也可以。
业余程序玩家。
回复 支持 反对

使用道具 举报

36

主题

1105

帖子

5

精华

论坛大神

Rank: 7Rank: 7Rank: 7

积分
2201
金钱
2201
注册时间
2012-2-8
在线时间
35 小时
发表于 2013-6-19 20:53:52 | 显示全部楼层
回复【9楼】ofourme:
---------------------------------
木有哦,很久没做这方面的东西了。
https://github.com/roxma
回复 支持 反对

使用道具 举报

7

主题

42

帖子

0

精华

初级会员

Rank: 2

积分
94
金钱
94
注册时间
2013-8-11
在线时间
0 小时
发表于 2013-9-27 08:30:10 | 显示全部楼层
回复 支持 反对

使用道具 举报

2

主题

12

帖子

0

精华

初级会员

Rank: 2

积分
81
金钱
81
注册时间
2013-8-30
在线时间
8 小时
发表于 2013-9-27 12:09:14 | 显示全部楼层
呵呵,虽然不懂软件,支持一个。
蓝牙相关,QQ:215835581,http://ljq200.taobao.com/
回复 支持 反对

使用道具 举报

5

主题

48

帖子

0

精华

初级会员

Rank: 2

积分
91
金钱
91
注册时间
2013-8-10
在线时间
0 小时
发表于 2013-12-1 18:49:08 | 显示全部楼层
谢谢!   有空要好好研究
机会,抓住一次就够了
回复 支持 反对

使用道具 举报

5

主题

48

帖子

0

精华

初级会员

Rank: 2

积分
91
金钱
91
注册时间
2013-8-10
在线时间
0 小时
发表于 2013-12-3 20:09:34 | 显示全部楼层
回复【4楼】Pony279:
---------------------------------
word文档里面的算法能看懂,  但是原子写的那个不太懂, 他是做了什么改变吗?  求大神帮忙
机会,抓住一次就够了
回复 支持 反对

使用道具 举报

5

主题

36

帖子

0

精华

中级会员

Rank: 3Rank: 3

积分
369
金钱
369
注册时间
2013-10-15
在线时间
107 小时
发表于 2013-12-3 20:39:21 | 显示全部楼层
回复【楼主位】JZHG1992:
---------------------------------
好东西啊,自愧缺乏专研
非知之难,行之惟难;非行之难,终之斯难
回复 支持 反对

使用道具 举报

5

主题

48

帖子

0

精华

初级会员

Rank: 2

积分
91
金钱
91
注册时间
2013-8-10
在线时间
0 小时
发表于 2013-12-3 20:49:03 | 显示全部楼层

没有人哦

机会,抓住一次就够了
回复 支持 反对

使用道具 举报

3

主题

46

帖子

0

精华

中级会员

Rank: 3Rank: 3

积分
401
金钱
401
注册时间
2013-3-28
在线时间
38 小时
发表于 2014-2-20 16:14:37 | 显示全部楼层
来学习~~~~~~~~~~~
回复 支持 反对

使用道具 举报

5

主题

154

帖子

0

精华

中级会员

Rank: 3Rank: 3

积分
205
金钱
205
注册时间
2013-6-8
在线时间
2 小时
发表于 2014-2-20 18:42:27 | 显示全部楼层
回复【14楼】iDream:
---------------------------------
只是旋转了一下坐标轴而已,x变y轴, y变x轴, 然后就开始打点画线了
即使爬到最高的山上,一次也只能脚踏实地地迈一步。
回复 支持 反对

使用道具 举报

3

主题

46

帖子

0

精华

中级会员

Rank: 3Rank: 3

积分
401
金钱
401
注册时间
2013-3-28
在线时间
38 小时
发表于 2014-2-27 15:04:09 | 显示全部楼层
为什么要分大于45°和小于45°情况,求解?
回复 支持 反对

使用道具 举报

126

主题

820

帖子

0

精华

金牌会员

Rank: 6Rank: 6

积分
1683
金钱
1683
注册时间
2012-10-28
在线时间
62 小时
发表于 2014-6-24 11:27:31 | 显示全部楼层
好东西,收藏了
坚持学习!就能成功!
回复 支持 反对

使用道具 举报

0

主题

3

帖子

0

精华

新手上路

积分
34
金钱
34
注册时间
2015-1-1
在线时间
3 小时
发表于 2015-1-7 20:36:06 | 显示全部楼层
好,学LCD刚好用到
回复 支持 反对

使用道具 举报

3

主题

15

帖子

0

精华

新手上路

积分
47
金钱
47
注册时间
2015-1-25
在线时间
0 小时
发表于 2015-4-7 17:26:27 | 显示全部楼层
今天在学习LCD_DrawLine的代码,发现下面这个for,看似简单,竟然不懂,到这里一搜,果然,大有乾坤呀。
不过貌似论坛里,关注的比较少。。。

for(t=0;t<=distance+1;t++ )//画线输出 
{  
LCD_DrawPoint(uRow,uCol);//画点 
xerr+=delta_x ; 
yerr+=delta_y ; 
if(xerr>distance) 

xerr-=distance; 
uRow+=incx; 

if(yerr>distance) 

yerr-=distance; 
uCol+=incy; 

}  

回复 支持 反对

使用道具 举报

1

主题

24

帖子

0

精华

初级会员

Rank: 2

积分
74
金钱
74
注册时间
2014-12-5
在线时间
6 小时
发表于 2015-4-8 14:44:53 | 显示全部楼层
楼主有研究过 ili9320或者ssd1289画椭圆,圆弧,多边形,图表吗
回复 支持 反对

使用道具 举报

1

主题

24

帖子

0

精华

初级会员

Rank: 2

积分
74
金钱
74
注册时间
2014-12-5
在线时间
6 小时
发表于 2015-4-8 14:45:21 | 显示全部楼层
回复【2楼】正点原子:
---------------------------------
原子哥有研究过 ili9320或者ssd1289画椭圆,圆弧,多边形,图表吗
回复 支持 反对

使用道具 举报

530

主题

11万

帖子

34

精华

管理员

Rank: 12Rank: 12Rank: 12

积分
165536
金钱
165536
注册时间
2010-12-1
在线时间
2117 小时
发表于 2015-4-8 23:06:00 | 显示全部楼层
回复【24楼】justin_1ee:
---------------------------------
我们例程就支持画圆,综合实验就有椭圆/弧线的画法函数。
我是开源电子网www.openedv.com站长,有关站务问题请与我联系。
正点原子STM32开发板购买店铺http://openedv.taobao.com
正点原子官方微信公众平台,点击这里关注“正点原子”
回复 支持 反对

使用道具 举报

50

主题

159

帖子

0

精华

中级会员

Rank: 3Rank: 3

积分
437
金钱
437
注册时间
2014-8-15
在线时间
29 小时
发表于 2015-7-17 10:44:25 | 显示全部楼层
我想问下为什么d = 3-2*r啊?我看网上的d=5/4-r,即使去掉浮点数也是用d=1-r
初学STM32,很多不懂,但是我相信坚持一定可以成功,向原子哥学习
回复 支持 反对

使用道具 举报

86

主题

983

帖子

0

精华

论坛大神

Rank: 7Rank: 7Rank: 7

积分
1848
金钱
1848
注册时间
2013-4-15
在线时间
163 小时
发表于 2015-8-5 11:27:44 | 显示全部楼层
大有乾坤啊  下载下来研究研究  谢谢楼主分享
合肥-文盲
回复 支持 反对

使用道具 举报

86

主题

983

帖子

0

精华

论坛大神

Rank: 7Rank: 7Rank: 7

积分
1848
金钱
1848
注册时间
2013-4-15
在线时间
163 小时
发表于 2015-8-6 16:00:44 | 显示全部楼层
回复【19楼】mypear:
---------------------------------
因为推导这个公式的时候是按斜率k∈[0,1]推导的,然后推广的
合肥-文盲
回复 支持 反对

使用道具 举报

86

主题

983

帖子

0

精华

论坛大神

Rank: 7Rank: 7Rank: 7

积分
1848
金钱
1848
注册时间
2013-4-15
在线时间
163 小时
发表于 2015-8-7 05:44:15 | 显示全部楼层
发现原子哥的画直线算法好像不是Bresenham算法
合肥-文盲
回复 支持 反对

使用道具 举报

1

主题

8

帖子

0

精华

新手上路

积分
33
金钱
33
注册时间
2016-6-8
在线时间
6 小时
发表于 2016-9-23 16:34:55 | 显示全部楼层
学习学习
回复 支持 反对

使用道具 举报

13

主题

314

帖子

0

精华

高级会员

Rank: 4

积分
713
金钱
713
注册时间
2012-7-20
在线时间
102 小时
发表于 2016-9-24 15:09:06 来自手机 | 显示全部楼层
挺好的资料,支持
回复 支持 反对

使用道具 举报

2

主题

194

帖子

0

精华

高级会员

Rank: 4

积分
981
金钱
981
注册时间
2015-9-20
在线时间
148 小时
发表于 2016-10-2 00:38:28 | 显示全部楼层
哇,留个爪,方便以后能找到
回复 支持 反对

使用道具 举报

0

主题

3

帖子

0

精华

新手上路

积分
40
金钱
40
注册时间
2017-3-1
在线时间
3 小时
发表于 2017-11-28 00:59:52 | 显示全部楼层
感谢前辈,正好下载研究
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则



关闭

原子哥极力推荐上一条 /2 下一条

正点原子公众号

QQ|手机版|OpenEdv-开源电子网 ( 粤ICP备12000418号-1 )

GMT+8, 2025-6-9 22:15

Powered by OpenEdv-开源电子网

© 2001-2030 OpenEdv-开源电子网

快速回复 返回顶部 返回列表