ブレゼンハムのアルゴリズム
ピクセルの格子上に直線を引くアルゴリズム。整数の加算だけで済み、浮動小数点も除算も要らない。
Jack Bresenhamが1962年にIBMでCalcompのプロッタ向けに考案し、1965年に発表した。要は誤差項を一歩ずつ積み上げる方式で、主軸に沿って1ピクセル進むたびに誤差の符号を見て、もう一方の座標を進めるか据え置くかを決める。使うのは加算・減算・比較だけなので、1960年代のハードウェアでも高速だった。
円を同じ要領で描く中点円アルゴリズムもあり、考え方はフォントのラスタライズからドット絵エディタの直線ツールまで生き残っている。画面で見る直線のほとんどは、この誤差項を通ってきたと言って差し支えない。