ブレゼンハム

４日ぐらい前からちょっと悩んでいたのですが、今日やっとすっきりしました。
なので、日記に書いてみます。

格子状のピクセルデータに点を打ちながら直線を描く処理を考えてみます。

例えばマウスでスクリーン上の任意の２点をクリックし、その間に線を描くという処理なんかに使えます。

任意の２点を通る直線の式は簡単で

となります。

どんなコンピュータ言語でも、浮動小数点を使えば簡単に計算できますね。
計算後無理矢理、整数にすれば答えはでます。

しかし、与えられる任意の２点が整数の場合はブレゼンハムというアルゴリズムを使うと計算時間が最適化されます。

ブレゼンハムは上記の式に対して、割算は行わずにあるxに対応するyを求める方法です。
手順を簡単に説明しますと、
xは からまで1づつ増やす。
そのさい、yは数式通りに増やすと小数点が出てきてしまうので、を考えます。
まずxを1ふやしたら、を分増やす。

とを比べて小さいならそのまま。
大きいならを行い、元のyに１加えます。
としていけば、整数同士の演算のみで処理できるので最適です。

これをc言語で書くなら

x = start_x;
y = start_y;
y_dash = 0;
dy = end_y - start_y;
dx = end_x - start_x;
while( end_x - x != 0 ){
  y_dash += dy;
  x++;
  if( y_dash >= dx ){
    y++;
    y_dash -= dx;
  }
  ピクセルに色を付ける関数( x, y, 色の値);
}

もちろん、右肩あがりかどうかや、xでなくyを変数にするべきかなどの判定や処理も必要ですがコンセプトとしては上記の事で充分です。