ブレゼンハムのアルゴリズム
線分の始点は明らかに直線上にある。
f ( x 0 , y 0 ) = 0 {\displaystyle f(x_{0},y_{0})=0}
この場合、直線は始点と終点を整数座標で指定することで定義される。
傾きは1以下なので、問題は次の点を ( x 0 + 1 , y 0 ) {\displaystyle (x_{0}+1,y_{0})} と ( x 0 + 1 , y 0 + 1 ) {\displaystyle (x_{0}+1,y_{0}+1)} のどちらにすべきかということに帰結する。直観的には x 0 + 1 {\displaystyle x_{0}+1} のときの直線の通る位置がどちらの点に近いかで選択すればよい。そこで、2点の中間点を考える。
f ( x 0 + 1 , y 0 + 1 / 2 ) {\displaystyle f(x_{0}+1,y_{0}+1/2)}
の計算結果が負なら中間点は直線より下にあり、正なら中間点は直線より上にある。中間点が直線より下なら、直線は ( x 0 + 1 , y 0 ) {\displaystyle (x_{0}+1,y_{0})} に近いのでその点を選び、逆なら ( x 0 + 1 , y 0 + 1 ) {\displaystyle (x_{0}+1,y_{0}+1)} を選べばよい。この中間点における関数の値のみで選択すべき点が決まる。
右図において、青い点 (2,2) は直線上にあり、緑の (3,2) と (3,3) が次に選択すべき点の候補である。黒い点 (3, 2.5) はその2つの候補点の中間点である。
中間点の関数値を求める場合と同様、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})} を選ぶ。