ブレゼンハムのアルゴリズム(Bresenham's line algorithm)は、与えられた始点と終点の間に連続した点を置き、近似的な直線を引くためのアルゴリズム。ブレゼンハムの線分描画アルゴリズム、ブレゼンハムアルゴリズムとも。コンピュータのディスプレイに直線を描画するのによく使われ、整数の加減算とビットシフトのみで実装できるので多くのコンピュータで使用可能である。コンピュータグラフィックスの分野の最初期のアルゴリズムの1つである。これを若干拡張すると、円を描くことができる。
アンチエイリアスをサポートした直線描画アルゴリズム（例えば、Xiaolin Wu's line algorithm
）もあるが、ブレゼンハムのアルゴリズムの高速性と単純さは今も重要である。プロッターやビデオカードのGPUといったハードウェアで使用されている。ソフトウェアでは多くのグラフィックスライブラリ（英語版）で使用している。非常に単純なので、ビデオカードのファームウェアなどに実装されていることが多い。1962年、IBMのジャック・ブレゼンハムが開発した。2001年、ブレゼンハムは次のように記している[1]。
当時私はサンノゼのIBMの開発研究室で働いていた。Calcomp製プロッター (Calcomp plotter
) が1407タイプライター型コンソール経由で IBM 1401 に接続されていた。このアルゴリズムは1962年夏には使われており、開発したのは1カ月ほど前だったかもしれない。当時プログラムは無償で交換されるものだったので、Calcomp（Jim Newland と Calvin Hefte）もそのコピーを持っていた。1962年秋、私がスタンフォードに戻ったときもコピーをスタンフォードの計算センターのライブラリに入れた。この直線描画ルーチンについて、1963年コロラド州デンバーで開催されたACM全国大会で発表した。ただし、その年は発表内容が出版されることはなく、単に日程表などに私の発表の題名が掲載されただけだった。その後IBMの Systems Journal が発表した論文を掲載したいと申し出てきたので、よろこんで提供し、1965年に出版された。
ブレゼンハムのアルゴリズムは後に修正を加えられ、円を描画するアルゴリズムにもなっている。こちらのアルゴリズムは midpoint circle algorithm などと呼ばれている。
アルゴリズムブレゼンハムのアルゴリズムで描画した直線の例。左上端の格子が (0,0) で、直線は (1,1) から (11,5) までひかれている。
以下が成り立つものとして説明していく。
左上端が原点 (0,0) で、ピクセルの座標は右方向と下方向に向かって大きくなる（例えば、(7,4) という座標のピクセルは (7,5) という座標のピクセルに接して上にある）。
各ピクセルの中心が、その整数座標に正確に対応するものとする。
いま、x が横方向、y が縦方向の座標であるとして、直線の両端のピクセルの座標が (x0, y0) と (x1, y1) として与えられたとする。
まず、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だけ増加することになる。描画すべき線分の方程式は次のようになる。 y − y 0 y 1 − y 0 = x − x 0 x 1 − x 0 {\displaystyle {\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}}}
x を順次与えて y を求め、最も近い整数値にするので、この式を次のように変形する。 y = y 1 − y 0 x 1 − x 0 ( x − x 0 ) + y 0 {\displaystyle y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}}
傾き ( y 1 − y 0 ) / ( x 1 − x 0 ) {\displaystyle (y_{1}-y_{0})/(x_{1}-x_{0})} は線分の両端の座標のみから求められるので事前に計算しておくことができる。x を順次増やして y を求めるが、最初の値は y 0 {\displaystyle y_{0}} であり、それに傾きを繰り返し加算すればよいことになる。
実際には傾きを加算し続けると精度が悪くなる（カハンの加算アルゴリズム参照）。しかし y を整数値に丸めた値と傾きを加算し続けた値の差のみを保持するようにすれば、その値は -0.5 から 0.5 の間で変化するだけであり、精度は悪くならない。すなわち、x を1ずつ増加させ、差に傾きを加算した結果が 0.5 を超えたら y をインクリメントして差から1を引けばよい。
以下の擬似コードでは、plot(x,y) でピクセル描画を行い、abs は絶対値を返すものとする。 function line(x0, x1, y0, y1) int deltax := x1 - x0 int deltay := y1 - y0 real error := 0 real deltaerr := abs (deltay / deltax) // deltax != 0 と仮定（垂直な線は扱わない） // この除算は分数を保持する形で行う必要がある。 int y := y0 for x from x0 to x1 plot(x,y) error := error + deltaerr if error ? 0.5 then y := y + 1 error := error - 1.0 この技法の問題は、error や deltaerr が分数であるためコンピュータでは計算が遅くなる点であり、さらに浮動小数点数を使った場合は加算によって誤差が蓄積していく点である。整数のみを使った方が高速化され正確になる。
最適化
