ブレゼンハムのアルゴリズム
この選択は誤差の蓄積によって一般化される。
以上でアルゴリズムの導出が完了した。性能上問題となるのは、Dの初期値で1/2という係数を使っている点である。ここで必要なのは累積差分の正負の符号だけなので、全てを2倍にしても結果には影響しない。
その結果、次のように整数のみでこのアルゴリズムを実装できる。
f ( x , y ) = x − 2 y + 2 {\displaystyle f(x,y)=x-2y+2} で表される直線の (0,1) から (6,4) までをこのアルゴリズムで計算した場合の経過を以下に示す。dx=6、dy=3 である。
D=2*3-6=0
plot(0,1)
1から6までループ x=1: D≤0: plot(1,1), D=6 x=2: D>0: y=2, plot(2,2), D=6+(6-12)=0 x=3: D≤0: plot(3,2), D=6 x=4: D>0: y=3, plot(4,3), D=6+(6-12)=0 x=5: D≤0: plot(5,3), D=6 x=6: D>0: y=4, plot(6,4), D=6+(6-12)=0
この描画結果を右図に示す。描画は座標上の交点(青い点)またはピクセル(黄色い四角形)で示されている。
中間点での関数値を求める代わりに、2点における関数値の差を使うことができる。それにより整数のみで計算可能となり、浮動小数点数を使うより一般に高速となる。この代替技法を導出するため、その差を次のように定義する。
D = f ( x 0 + 1 , y 0 + 1 / 2 ) − f ( x 0 , y 0 ) {\displaystyle D=f(x_{0}+1,y_{0}+1/2)-f(x_{0},y_{0})}
始点では f ( x 0 , y 0 ) = 0 {\displaystyle f(x_{0},y_{0})=0} であるため、この式は中間点の関数値を求めることと等価である。この式を変形すると次のようになる。
D = [ A ( x 0 + 1 ) + B ( y 0 + 1 / 2 ) + C ] − [ A x 0 + B y 0 + C ] = A + 1 2 B {\displaystyle {\begin{aligned}D&=\left[A(x_{0}+1)+B(y_{0}+1/2)+C\right]-\left[Ax_{0}+By_{0}+C\right]\\&=A+{\frac {1}{2}}B\end{aligned}}}