ライン・ルーチン (1)線分描画のアルゴリズム

になるので、x = 0, 1, ... 5 を代入して y = 0, 0.6, ... 3 を求め、その結果を順にプロットしていけばよいことになります(当然、各点の座標値は整数でなければならないため、実際には計算値の小数部を四捨五入して (0,0),(1,1),...(5,3) をプロットします)。
しかし、傾きが急な線分 (m > 1) の場合、Y座標の増分が1より大きくなって、とびとびにプロットされる事になるため、「X座標を変化させつつY座標を求める」のではなく「Y座標を変化させつつX座標を求める」ことになります。

ここで 0≦m＜1の場合のみを考えます。この時、直線の傾きは右上がりで 45°より小さくなります。
上の例では各座標毎にxを代入してyを求めていましたが、xが1増えるとyはmずつ増加する事に着目すると、

と初期化しておいて、あとはmを加えていくだけで、各座標でのyの値を順に求める事ができます。
さらに0≦m＜1の条件下では、ある点(x,y)の次にプロットされるべき点は

のいずれかになります。すなわち真の線分が2点の中点より下側なら(1)の点を、上側なら(2)の点を選択すればよい事になり、求めたyの小数部に着目した場合

する事と同じことになります(小数部が0.5の場合はどちらでもかまわないのですが、四捨五入のイメージで(2)にしています)。

以上から、yの実数値とそれを整数化した値との差をEで表したとき、y = m( x - x0 ) + y0 を描画するアルゴリズムは次のような形になります。

x = x0, y = y0 で初期化する。この時(x,y)は真の線分上に存在するのでE = 0に初期化できる。
点(x,y)をプロットする。
xに1を加える。
Eにm(0≦m＜1)を加える。結果が1/2以上になった場合、真の線分は(x,y+1)に近いことを意味するので、yに1を加え、Eが新たなy座標との誤差を示すようEから1を引く。
x = x1になるまで2)～4)を繰り返す。

このアルゴリズムは、1962年に Jack E. Bresenhamによって開発された「ブレセンハムの線分発生アルゴリズム(Bresenham's line algorithm)」と呼ばれるもので、ライン・ルーチン以外にもグラデーションや矩形の拡大・縮小を行うアルゴリズムなど、様々な処理で活用されています。

さて、このアルゴリズムを整数演算のみで行う場合はもうすこし工夫が必要です。

まずはEの初期値を0ではなく-1/2とします。これはEの値の比較を1/2で行う代わりに0で行うためです。不等式

Eの初期値とmはまだ小数を含んでいるため、これらを整数化することを考えます。上に示したようにEの比較方法を変更することにより、Eは符号だけが意味を持つようになり値自体が必要なくなります。また、mはEの増分として使用されるだけです。よって、E, m およびyが1増加したときのEの補正値(=1)に適当な数をかけてもアルゴリズムは破綻しません。それぞれに2(x1-x0)をかける事で

m≧1の場合は yを 1ずつ増やしながら同様の処理を繰り返せばよいことになります。この時

となります。また、m<0の場合はx(またはy)を1ずつ減らしながら処理を行うことで対処できます。

以下に、「ブレセンハムの線分発生アルゴリズム」のサンプル・プログラムを示します。

/* 座標定義用構造体 */
typedef struct Coord
{
  int x;
  int y;
} Coord;

/* 点描画用関数 */
void pset( Coord c, unsigned int col )
{
  :
}

void line( Coord c0, Coord c1, unsigned int col )
{
  int i;

  Coord d; /* 二点間の距離 */
  d.x = ( c1.x > c0.x ) ? c1.x - c0.x : c0.x - c1.x;
  d.y = ( c1.y > c0.y ) ? c1.y - c0.y : c0.y - c1.y;

  Coord s; /* 二点の方向 */
  s.x = ( c1.x > c0.x ) ? 1 : -1;
  s.y = ( c1.y > c0.y ) ? 1 : -1;

  /* 傾きが1より小さい場合 */
  if ( d.x > d.y ) {
    int E = -d.x;
    for ( i = 0 ; i <= d.x ; i++ ) {
      pset( c0, col );
      c0.x += s.x;
      E += 2 * d.y;
      if ( E >= 0 ) {
        c0.y += s.y;
        E -= 2 * d.x;
      }
    }
  /* 傾きが1以上の場合 */
  } else {
    int E = -d.y;
    for ( i = 0 ; i <= d.y ; i++ ) {
      pset( c0, col );
      c0.y += s.y;
      E += 2 * d.x;
      if ( E >= 0 ) {
        c0.x += s.x;
        E -= 2 * d.y;
      }
    }
  }
}

サンプル・プログラムでは、傾きが 0≦m＜1と m≧1の二つの場合で処理を分けています。傾きが負の方向である場合を考慮するため、二点の方向を表す変数 sを利用して、x, y方向の座標値の増減を行なっています。以上の事を考慮すれば、どのような処理を行なっているかは簡単に理解できると思います。

( x+1, y )	--- (1)
( x+1, y+1 )	--- (2)

Eの初期値	-1/2	→	-(x1-x0)
Eの増分	(y1-y0)/(x1-x0)	→	2(y1-y0)
Eの補正値	1	→	2(x1-x0)

Eの初期値	-(y1-y0)
Eの増分	2(x1-x0)
Eの補正値	2(y1-y0)