ブレセンハム(Bresenham)のアルゴリズム - pyopyopyo - Linuxとかプログラミングの覚え書き -

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;
	       }
	  }
     }
}