ブレゼンハムアルゴリズム

ブレゼンハムの線分描画アルゴリズムのこと。

処理に時間のかかる乗算や除算を使用せず、加算と減算のみで任意の2点間に直線を描画するアルゴリズム。しかし加減算しか使用しない代わりに分岐処理が非常に多く、過去のCPUならいざ知らず最近のものは分岐予測機能を持ちシフト演算も早いため、必ずしも効率的なアルゴリズムとはいえない。

具体的には、まず始点と終点の間の距離をXY方向ともに計測し、結果符号を座標更新時の方向用に記憶しておき計測値の絶対値をとる。そして、計測値の大きいほうをベース値、もう一方を更新値とし、カウンターをゼロクリアする。ここまでが初期化で、次からが実際の繰り返し処理となる。

まず、カウンターに更新値を加算、そしてカウンターがベース値を超えていたらベース値にしたほうの座標を更新し、カウンターからベース値を引いて、さらに加算値の方向の座標も更新する。これを座標が目的地にたどり着くまで繰り返す。

通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)