ブレゼンハムのアルゴリズム
ブレゼンハムのアルゴリズムは2段階で導出される。第一段階は傾きを係数とする通常の直線の方程式を別の形式に変換するものである。そして、その新しい方程式を使い、誤差の累積という考え方に基づいて直線を描画する。
Patrick-Gilles Maillot's Thesis MICAD '87 proceedings on CAD/CAM and Computer Graphics, page 591 - ISBN 2-86601-084-1. ブレゼンハムのアルゴリズムを応用して3次元グラフィックスで隠れて見えない直線を削除する技法を示したもの
Line Thickening by Modification To Bresenham's Algorithm, A.S. Murphy, IBM Technical Disclosure Bulletin, Vol. 20, No. 12, May 1978. ブレゼンハムのアルゴリズムを拡張して太い線を描画する技法を示したもの
一般に次のように取り決める。
左上端が原点 (0,0) で、ピクセルの座標は右方向と下方向に向かって大きくなる(例えば、(7,4) という座標のピクセルは (7,5) という座標のピクセルに接して上にある)。
各ピクセルの中心が、その整数座標に正確に対応するものとする。
直線の両端のピクセルの座標は (x0, y0) と (x1, y1) であり、x が横方向、y が縦方向の座標である。
このアルゴリズムは当初、1つの象限のみを対象とし、線分は右下に向かう方向のみ(すなわち、x0≤x1 かつ y0≤y1)で、その傾きは1未満(すなわち、 x 1 − x 0 {\displaystyle x_{1}-x_{0}} の方が y 1 − y 0 {\displaystyle y_{1}-y_{0}} より長い)でなければならなかった。その場合、 x 0 {\displaystyle x_{0}} と x 1 {\displaystyle x_{1}} の間の x のそれぞれの位置について、(このアルゴリズムでの計算で) y の位置が一意に定まり、 y 0 {\displaystyle y_{0}} と y 1 {\displaystyle y_{1}} の間の y のそれぞれの位置には複数のピクセルが描画されうることになる。
ブレゼンハムのアルゴリズムでは、x に対応した y の値(小数値)を計算し、それに最も近い整数値を描画すべきピクセルの座標とする。したがって、1つ前の x で求めた y の整数値と同じか、または1だけ増加することになる。描画すべき線分の方程式は次のようになる。