Bresenham’s line algorithm

布雷森汉姆直线演算法

一、使用方法

二、算法推导

d = 2·Δy-Δx

递推式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

当d≥0时：

{ 
    d=d+2·(Δy－Δx)；       
    y++；       
    x++；      
    }  
    
否则：  
{ 
    d=d+2·Δy；       
    x++；      
    }

采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。

三、直线Bresenham算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

　　// 条件：0≤m≤1且x1<x2
　　//1.输入线段的两个端点坐标和画线颜色：x1，y1，x2，y2，color；
　　//2.设置象素坐标初值：x=x1，y=y1；
　　//3.设置初始误差判别值：p=2·Δy-Δx；
　　//4.分别计算：Δx=x2-x1、Δy=y2-y1；
　　//5.循环实现直线的生成：
　　　for(x=x1；x<=x2；x++)
　　　{ SetPixel(dc,x,y,color) ；
　　　　if(p>=0)
　　　　　{ y=y+1；
　　　　　　p=p+2·(Δy-Δx)；
　　　　　}
　　　　else
　　　　　{ p=p+2·Δy；
　　　　　}
　　　}

参考资料

维基百科-布雷森漢姆直線演算法

The Bresenham Line-Drawing Algorithm

CSDN-直线的Bresenham算法

百度文库-直线的Bresenham算法-地质大学课件

个人笔记-bresenham算法的FPGA的实现1

知乎-游戏编程里面有哪些经典或者很酷的算法？

• ← Previous Post
• Next Post →