ブレゼンハムの直線アルゴリズムの理解(Ruby/SDL)

直線は引けたが、いまいちアルゴリズムの理解があやふやだったので、ウェブで色々調べてみた。

プロットするための計算式の考え方も含めて下記のサイトが分かりやすい。

参照：

http://sioramen.sub.jp/algorithm-bresenham/bresenham.html

傾きを足してって、近似値のyをプロットする部分は、

直観的に理解するために、サンプルプログラムを作成してみた。

ソース：

---

require 'sdl'

SCREEN_W, SCREEN_H = 640, 480

CELL_W = 64

A_W, A_H = SCREEN_W/CELL_W, SCREEN_H/CELL_W

def b_draw_line(x0,y0,x1,y1)

  dx = x1-x0

  dy = y1-y0

  px, py = x0, y0

  e = 0

  loop do

    yield(px,py)

    px += 1

    e += 2*dy

    if(e >= dx) then

      e -= 2*dx

      py += 1

    end

    if(px>x1) then break end

  end

end

def put_pixel(x,y)

  @area[y*A_W+x] = TRUE

end

def update_area()

  for y in 0..A_H do

    for x in 0..A_W do

      if(@area[y*A_W+x]==TRUE) then

        @screen.draw_rect(x*CELL_W, y*CELL_W, 64, 64,[255,255,255])

        @screen.fill_rect(x*CELL_W+1, y*CELL_W+1, 64-1, 64-1,[125,125,125])

      else

        @screen.draw_rect(x*CELL_W, y*CELL_W, 64, 64,[255,255,255])

      end

    end

  end

end

#---------------------------------------------------------------                     

@area = Array.new( A_W * A_H, FALSE)

SDL.init( SDL::INIT_VIDEO )

@screen = SDL.setVideoMode(640, 480, 16, SDL::SWSURFACE )

b_draw_line(0,0,10,7) {|x,y| put_pixel(x,y) }

update_area

CD = CELL_W/2

@screen.draw_line(0+CD,0+CD,10*CELL_W-CD,7*CELL_W-CD,[255,255,100])

screen.updateRect(0,0,0,0)

loop do

     while event = SDL::Event2.poll

     case event

     when SDL::Event2::Quit, SDL::Event2::KeyDown

          exit

     end

   end

end

---