ブレゼンハムのアルゴリズム
1962年、IBMのジャック・ブレゼンハムが開発した。2001年、ブレゼンハムは次のように記している。
当時私はサンノゼのIBMの開発研究室で働いていた。Calcomp製プロッター (Calcomp plotter) が1407タイプライター型コンソール経由で IBM 1401 に接続されていた。このアルゴリズムは1962年夏には使われており、開発したのは1カ月ほど前だったかもしれない。当時プログラムは無償で交換されるものだったので、Calcomp(Jim Newland と Calvin Hefte)もそのコピーを持っていた。1962年秋、私がスタンフォードに戻ったときもコピーをスタンフォードの計算センターのライブラリに入れた。
この直線描画ルーチンについて、1963年コロラド州デンバーで開催されたACM全国大会で発表した。ただし、その年は発表内容が出版されることはなく、単に日程表などに私の発表の題名が掲載されただけだった。その後IBMの Systems Journal が発表した論文を掲載したいと申し出てきたので、よろこんで提供し、1965年に出版された。
ブレゼンハムのアルゴリズムは後に修正を加えられ、円を描画するアルゴリズムにもなっている。こちらのアルゴリズムは midpoint circle algorithm などと呼ばれている。
傾きを係数とする直線の方程式は次のとおりである。
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}}}
この最後の式を x と y の関数として次のように表せる。
点 (2,2) はこの直線上にある。
f ( 2 , 2 ) = x − 2 y + 2 = ( 2 ) − 2 ( 2 ) + 2 = 2 − 4 + 2 = 0 {\displaystyle f(2,2)=x-2y+2=(2)-2(2)+2=2-4+2=0}
また、点 (2,3) は直線上にはない。
f ( 2 , 3 ) = ( 2 ) − 2 ( 3 ) + 2 = 2 − 6 + 2 = − 2 {\displaystyle f(2,3)=(2)-2(3)+2=2-6+2=-2}
点 (2,1) も同様である。
f ( 2 , 1 ) = ( 2 ) − 2 ( 1 ) + 2 = 2 − 2 + 2 = 2 {\displaystyle f(2,1)=(2)-2(1)+2=2-2+2=2}
(2,1) と (2,3) はこの直線をはさんで反対側にあり、どちら側になるかは f(x,y) の値が正か負かで決まる。すなわち、直線は平面を2つの半平面に分割するものであり、f(x,y) が負になる半平面と正になる半平面が存在する。この性質はアルゴリズムの導出において重要である。