ブレゼンハムのアルゴリズム(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) という座標のピクセルに接して上にある）。

各ピクセルの中心が、その整数座標に正確に対応するものとする。

直線の両端のピクセルの座標は (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だけ増加することになる。描画すべき線分の方程式は次のようになる。 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 が分数であるためコンピュータでは計算が遅くなる点であり、さらに浮動小数点数を使った場合は加算によって誤差が蓄積していく点である。整数のみを使った方が高速化され正確になる。そこで上の例で分数または小数になっている全ての数（定数0.5も含む）に deltax をかけて整数にするという技法を使う。ただしそうするとメインループ内で除算が必要になる。そのため error の初期値を変更し、初期値を0として0.5を越えるまでカウントアップするのではなく、初期値を0.5（に deltax をかけた値）にし、0になるまでカウントダウンするように変更する。新たなプログラムの擬似コードは次のようになる。 function line(x0, y0, x1, y1) boolean steep := abs(y1 - y0) > abs(x1 - x0) if steep then swap(x0, y0) swap(x1, y1) if x0 > x1 then swap(x0, x1) swap(y0, y1) int deltax := x1 - x0 int deltay := abs(y1 - y0) int error := deltax / 2 int ystep int y := y0 if y0 < y1 then ystep := 1 else ystep := -1 for x from x0 to x1 if steep then plot(y,x) else plot(x,y) error := error - deltay if error < 0 then y := y + ystep error := error + deltax

なお、このプログラムは (x0, y0) と (x1, y1) の位置関係がどうであっても描画できるようにしているが、基本形と逆転していると描画順序が反転する。破線を描く場合など描画順序が重要な場合、2つめのswapを排除して次のように簡略化する必要がある。function line(x0, y0, x1, y1) boolean steep := abs(y1 - y0) > abs(x1 - x0) if steep then swap(x0, y0) swap(x1, y1) int deltax := abs(x1 - x0) // 修正 int deltay := abs(y1 - y0) int error := deltax / 2 int ystep int y := y0 int inc // 追加 if x0 < x1 then inc := 1 else inc := -1 // 追加 if y0 < y1 then ystep := 1 else ystep := -1 for x from x0 to x1 with increment inc // 修正 if steep then plot(y,x) else plot(x,y) // increment により描画順序が制御される error := error - deltay if error < 0 then y := y + ystep error := error + deltax
単純化

誤差を両方向同時に計算すれば、初期化部分の swap を排除できる。 function line(x0, y0, x1, y1) dx := abs(x1-x0) dy := abs(y1-y0) if x0 < x1 then sx := 1 else sx := -1 if y0 < y1 then sy := 1 else sy := -1 err := dx-dy loop setPixel(x0,y0) if x0 = x1 and y0 = y1 exit loop e2 := 2*err if e2 > -dy then err := err - dy x0 := x0 + sx end if if e2 < dx then err := err + dx y0 := y0 + sy end if end loop
導出

ブレゼンハムのアルゴリズムは2段階で導出される。第一段階は傾きを係数とする通常の直線の方程式を別の形式に変換するものである。そして、その新しい方程式を使い、誤差の累積という考え方に基づいて直線を描画する。
直線の方程式y=f(x)=.5x+1 or f(x,y)=x-2y+2正と負の半平面

傾きを係数とする直線の方程式は次のとおりである。 y = f ( x ) = m x + b {\displaystyle y=f(x)=mx+b}

ここで m が傾き、b がy軸上の値（y軸との交点）である。この方程式は x についての関数だが、これを x と y の関数に変換することで扱いやすくする。傾きを Δ y / Δ x {\displaystyle \Delta y/\Delta x} と表し、代数学的変換を施す。 y = m x + b y = ( Δ y ) ( Δ x ) x + b ( Δ x ) y = ( Δ y ) x + ( Δ x ) b 0 = ( Δ y ) x − ( Δ x ) y + ( Δ x ) b {\displaystyle {\begin{aligned}y&=mx+b\\y&={\frac {(\Delta y)}{(\Delta x)}}x+b\\(\Delta x)y&=(\Delta y)x+(\Delta x)b\\0&=(\Delta y)x-(\Delta x)y+(\Delta x)b\end{aligned}}}