整数演算の場合
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/27 04:51 UTC 版)
「ブレゼンハムのアルゴリズム」の記事における「整数演算の場合」の解説
中間点での関数値を求める代わりに、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}}} 中間点の関数値を求める場合と同様、Dが正なら ( x 0 + 1 , y 0 + 1 ) {\displaystyle (x_{0}+1,y_{0}+1)} を選び、さもなくば ( x 0 + 1 , y 0 ) {\displaystyle (x_{0}+1,y_{0})} を選ぶ。 さらに2つ目の点の選択は次のようになる。 f ( x 0 + 2 , y 0 + 1 / 2 ) − f ( x 0 + 1 , y 0 + 1 / 2 ) = A = Δ y {\displaystyle f(x_{0}+2,y_{0}+1/2)-f(x_{0}+1,y_{0}+1/2)=A=\Delta y} f ( x 0 + 2 , y 0 + 3 / 2 ) − f ( x 0 + 1 , y 0 + 1 / 2 ) = A + B = Δ y − Δ x {\displaystyle f(x_{0}+2,y_{0}+3/2)-f(x_{0}+1,y_{0}+1/2)=A+B=\Delta y-\Delta x} この差が正なら ( x 0 + 2 , y 0 + 1 ) {\displaystyle (x_{0}+2,y_{0}+1)} を選び、さもなくば ( x 0 + 2 , y 0 ) {\displaystyle (x_{0}+2,y_{0})} を選ぶ。この選択は誤差の蓄積によって一般化される。 以上でアルゴリズムの導出が完了した。性能上問題となるのは、Dの初期値で1/2という係数を使っている点である。ここで必要なのは累積差分の正負の符号だけなので、全てを2倍にしても結果には影響しない。 その結果、次のように整数のみでこのアルゴリズムを実装できる。 plot(x0,y0, x1,y1) dx=x1-x0 dy=y1-y0 D = 2*dy - dx plot(x0,y0) y=y0 for x from x0+1 to x1 if D > 0 y = y+1 plot(x,y) D = D + (2*dy-2*dx) else plot(x,y) D = D + (2*dy) 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 この描画結果を右図に示す。描画は座標上の交点（青い点）またはピクセル（黄色い四角形）で示されている。
※この「整数演算の場合」の解説は、「ブレゼンハムのアルゴリズム」の解説の一部です。
「整数演算の場合」を含む「ブレゼンハムのアルゴリズム」の記事については、「ブレゼンハムのアルゴリズム」の概要を参照ください。
- 整数演算の場合のページへのリンク
