ブレセンハム(Bresenham)のアルゴリズム

FizzBuzz問題の次の問題として,直線の描画アルゴリズムなんてどうだろう?

直線描画のアルゴリズムといえばブレセンハム(Bresenham)のアルゴリズムが有名.知っていると知らないでは雲泥の差.試行錯誤するもよし,そのままブレセンハムを実装するもよし.力量を測る問題としては手頃な気がする.

void
draw_line(int ix1, int iy1, int ix2, int iy2) {
     int x = ix1;
     int y = iy1;
     int dx = abs(ix2 - ix1);
     int dy = abs(iy2 - iy1);
     int sx = (ix2>ix1)?1:-1;
     int sy = (iy2>iy1)?1:-1;

     if (dx >= dy) {
	  int err = 2*dy - dx;
	  int i = 0;
	  for(i=0; i<=dx; ++i) {
	       set(x,y,color);
	       
	       x += sx;
	       err += 2*dy;
	       if (err >= 0) {
		    y += sy;
		    err -= 2*dx;
	       }
	  }
     }else{
	  int err = 2*dx - dy;
	  int i = 0;
	  for(i=0; i<=dy; ++i) {
	       set(x,y,color);
	       
	       y += sy;
	       err += 2*dx;
	       if (err >= 0) {
		    x += sx;
		    err -= 2*dy;
	       }
	  }
     }
}

ゲームプログラマになる前に覚えておきたい技術
平山 尚(株式会社セガ)
秀和システム
売り上げランキング: 694
おすすめ度の平均: 5.0
5 ゲームを作りたい方へ
5 基礎を習得して凝り固まった頭が少しほぐれました
5 本物の初心者向け参考書
5 初級プログラマが一人でゲームをつくれるようになるための本。
5 良書です。が、ある程度のプログラミングスキルが必要
C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)
奥村 晴彦
技術評論社
売り上げランキング: 39159
おすすめ度の平均: 4.5
5 濃い一冊、名著
3 手っ取り早いけど。。。
5 困った時の助け舟
5 安心できる本
5 K&Rとともに、一番参照回数が多い本です