本文共 6229 字，大约阅读时间需要 20 分钟。
bresenham算法
Bresenham's algorithm was proposed to overcome the drawbacks of the DDA algorithm. First, let us see what the drawbacks of were,
提出了Bresenham算法以克服DDA算法的缺点。 首先，让我们看看的缺点是什么，
Drawbacks of DDA algorithm:
DDA算法的缺点：
The only drawback of the DDA algorithm was that it produces floating-point results which reduces the overall complexity. This problem was solved by Bresenham's line drawing algorithm.
DDA算法的唯一缺点是它会产生浮点结果，从而降低了总体复杂度。 Bresenham的线条绘制算法解决了这个问题。
Bresenham's line drawing algorithm is a second method of generating a line that was proposed after the DDA algorithm to overcome its limitations and drawbacks. It was developed by J.E. Bresenham in 1962. This algorithm is used for calculating intermediate coordinate points between the given source and ending points by only using integer addition and subtraction.
布雷森汉姆(Bresenham)的线条绘制算法是生成线条的第二种方法，该方法是DDA算法之后提出的，用于克服其局限性和缺点。 它由JE Bresenham在1962年开发。此算法仅通过使用整数加法和减法来计算给定源和终点之间的中间坐标点。
This algorithm determines the points which should be selected to form a close approximation to a line between two points.
该算法确定应选择的点以形成与两点之间的直线的近似值。
It is also an incremental method for creating a line.
这也是创建线的一种增量方法。
It is faster than the DDA algorithm as it does not involves the use of heavy operations such as multiplication and division.
它比DDA算法更快，因为它不涉及繁重的运算，例如乘法和除法。
Suppose we have to draw a line PQ with coordinates P (x1, y1) and Q (x2, y2).
假设我们必须绘制一条坐标为P(x1，y1)和Q(x2，y2)的直线PQ 。
To draw the line using Breshenam's line drawing algorithm, first of all, calculate the slope of the line from the given coordinates by using,
要使用Breshenam的线条绘制算法绘制线条，首先，使用，从给定的坐标计算线条的斜率，
m = dy/dx Where, dy = x2 - x1 dx = y2 - y1
There can be three values of slope (m) i.e.
斜率(m)可以有三个值，即
a. m < 1 b. m > 1 c. m = 1
On the basis of the value of the slope, the decision parameter is calculated which gives the decision about the selection of the next pixel point which has the least distance from the true line.
基于该斜率的值，计算决策参数，该决策参数给出关于与真实线的距离最小的下一像素点的选择的决策。
We'll be deriving the decision parameter Pk for slope (m < 1), to make things clear.
为了清楚起见，我们将得出坡度(m <1)的决策参数P k 。
Let us consider a straight line passing through a point A (xk+1, y),
让我们考虑一条通过点A(x k +1，y)的直线，
Where,
哪里，
xk+1 = xk + 1
and y satisfies the equation of the line i.e.
和y满足直线方程，即
y = m (xk + 1) + c ------(1)
The next pixel to the line will be either to its top or to its bottom.
该行的下一个像素将在其顶部或底部。
If we choose the top pixel, the points at B will become,
如果我们选择顶部像素，则B点将变为
xk+1 = xk + 1 and y = yk + 1
If we choose bottom pixel, the points at C will become,
如果我们选择底部像素，则C点将变为
xk+1 = xk + 1 and y = yk
Since Bresenham's algorithm depends upon the distance, let's calculate it between A and B; and A and C.
由于Bresenham的算法取决于距离，因此让我们计算A和B之间的距离； 和A和C。
For A and B: let the distance be denoted as s.
对于A和B ：将该距离表示为s 。
s = ( yk + 1 ) - y
For A and C: let the distance be denoted as t.
对于A和C ：将该距离表示为t 。
t = y - yk
Now consider their difference:
现在考虑它们的区别：
(t – s) = y - yk - [ (yk + 1) - y] = 2y - 2yk - 1 ------(2)
When (t - s) < 0 => t < s, then the closest pixel will be C.
当(t-s)<0 => t <s时，最接近的像素为C。
When (t - s) > 0 => s < t, then the closest pixel will be B.
当(t-s)> 0 => s <t时，最接近的像素为B。
Putting the value of eq.(1) in eq.(2);
将等式(1)的值放在等式(2)中;
t – s = 2m ( xk + 1 ) + 2c - 2yk - 1
t – s = 2m(x k + 1)+ 2c-2y k -1
Now, substituting the value of m;
现在，代入m的值；
t – s = 2dy ( xk + 1 ) / dx + 2c - 2yk - 1
t – s = 2dy(x k + 1)/ dx + 2c-2y k -1
To remove dx from denominator, multiply dx on both sides;
要从分母中删除dx，请将两边的dx相乘；
dx (t - s) = dx ( 2dy ( xk + 1 ) / dx + 2c - 2yk – 1 )
dx(t-s)= dx(2dy(x k + 1)/ dx + 2c-2y k – 1)
let Pk = dx (t - s), thus introducing the decision variable
令P k = dx(t-s)，从而引入决策变量
Pk = 2dy . xk - 2dx . yk + b
P k = 2dy。 x k -2dx y k + b
B = 2dy + dx ( 2c – 1 )
B = 2dy + dx(2c – 1)
Let us calculate next decision variable:
让我们计算下一个决策变量：
Pk+1 = 2dy . xk+1 - 2dx . yk+1 + b
P k + 1 = 2dy。 x k + 1-2dx。 y k + 1 + b
Now, solve the difference Pk+1 - Pk
现在，求出差P k + 1 -P k
Pk+1 - Pk = 2dy . xk+1 - 2dx . yk+1 + b - ( 2dy . xk - 2dx . yk + b )
P k + 1 -P k = 2dy。 x k + 1-2dx。 y k + 1 + b-(2dy。x k -2dx。y k + b)
= 2dy . xk+1 - 2dx . yk+1 - 2dy . xk - 2dx . yk
= 2dy x k + 1-2dx。 y k + 1-2dy。 x k -2dx k
Since xk+1 = xk + 1
由于x k + 1 = x k + 1
Pk+1 - Pk = 2dy . (xk + 1) - 2dx . yk+1 - 2dy . xk - 2dx . yk
P k + 1 -P k = 2dy。 (x k +1)-2dx。 y k + 1-2dy。 x k -2dx k
Pk+1 = Pk + 2dy - 2dx . yk+1 - 2dx . yk
P k + 1 = P k + 2dy-2dx。 y k + 1-2dx。 k
Special Cases:
特别案例：
When Pk >= 0 => yk+1 = yk + 1 i.e. point B is chosen
当P k > = 0 => y k + 1 = y k +1时，即选择了点B
Pk+1 = Pk + 2dy - 2dx
P k + 1 = P k + 2dy-2dx
When Pk < 0 => yk+1 = yk i.e. point C is chosen
当P k <0 => y k + 1 = y k时，即选择点C
Pk+1 = Pk +2dy
P k + 1 = P k + 2dy
Now, we will calculate the initial decision variable by using
现在，我们将使用来计算初始决策变量
P0 = dx ( 2dy ( x0 + 1 ) / dx + 2c - 2y0 – 1 )
P 0 = dx(2dy(x 0 + 1)/ dx + 2c-2y 0 – 1)
Put c = y0 - x0. ( dy / dx )
把c = y 0 -x 0. (dy / dx)
We get
我们得到
P0 = 2dy – dx
P 0 = 2dy – dx
Algorithm:
算法：
Step1: Start
第一步：开始
Step2: Declare x1, y1, x2, y2.
步骤2：声明x1，y1，x2，y2。
Step3: Calculate dx = x2 - x1
步骤3：计算dx = x2-x1
Dy = y2 - y1
Dy = y2-y1
Step 4: Calculate slope, m = dy / dx.
步骤4：计算斜率，m = dy / dx。
Step5: For m < 1: Calculate initial decision variable: P = 2dy - dx.
步骤5：对于m <1：计算初始决策变量：P = 2dy-dx。
Step6: while (x1 <= x2)
步骤6：while(x1 <= x2)
if(P < 0):
如果(P <0)：
xk = xk + 1
x k = x k + 1
P = P + 2dy
P = P + 2dy
yk = yk
y k = y k
else :
其他：
xk = xk + 1
x k = x k + 1
P = P + 2dy - 2dx
P = P + 2dy-2dx
yk = yk + 1
y k = y k + 1
Step 7: Plot ( xk , yk )
步骤7：绘制(x k ，y k )
Step 8: End
步骤8：结束
It is faster because it does not involve floating-point calculations.
它更快，因为它不涉及浮点计算。
It involves only integer arithmetic. Hence, it is easier to implement.
它仅涉及整数算术。 因此，它更容易实现。
It also does not provide smooth lines though accuracy has been improved.
尽管精度有所提高，但它也不能提供平滑的线条。
翻译自:
bresenham算法
转载地址：http://xwvzd.baihongyu.com/