布雷森汉姆直线算法

2021-03-02 15:21:27 浏览:364

定义

布雷森汉姆直线算法(Bresenham's line algorithm)是用来描绘由两点所决定的直线的算法,它会算出一条线段在n 维光栅上最接近的点,以形成两点之间的直线近似值。

布雷森汉姆直线算法通常用于在位图图像中(例如在计算机屏幕上)绘制线条,算法仅使用整数加法,减法和移位操作,因此处理速度较快[1]

算法原理

图 1 n维栅格和连续直线示意图

假设有一连续直线Ax+By+C=0,如何用像素栅格来拟合连续直线呢?如图1所示,蓝点(x0,y0)位于此直线上,黑点在直线上但不在栅格上,应选择距离(x0+1,f(x0+1))点最近的栅格点作为近似点。为了找到近似点,计算两绿点中间点的函数值:f(x0+1,y0+1/2),如果这个值小于0的话,说明直线更靠近(x0+1,y0+1),反之,直线更靠近((x0+1,y0)点。

进一步的,可以使用点之间的差而不是中点处直线的取值正负来进行判断。假设f(x0,y0)=0,定义中点(x0+1,y0+1/2)和(x0,y0)的差为:

其可以转化为:

如果D大于0,则选择(x0+1,y0+1) ,否则选择(x0+1,y0) 。

接下来,对于第二个点,得到:

如果差值大于0,则选择(x0+2,y0+1) ,否则选择(x0+2,y0) 。

参考文献

[1] https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

作          者: 泮桥成像光电商城

出          处: https://www.ipanqiao.com/entry/337

版          权:本文版权归泮桥成像光电商城所有

免责声明:本文中使用的部分文字内容与图片来自于网络,如有侵权,请联系作者进行删除。

转          载:欢迎转载,但必须保留上述声明;必须在文章中给出原文链接;否则必究法律责任。

Copyright © 2019-2022 南京超维景生物科技有限公司 版权所有 www.ipanqiao.com苏ICP备20009590号-1
联系我们
立即做合同
微信客服
电话咨询

400-998-9826

17302548620

快速留言

泮桥成像光电商城专业人员会在24小时之内联系您

关闭 提交