スキャンラインシードフィルによる塗り潰しの実験

scanlineseedfill.rb

#!ruby -Ks
# -*- mode: ruby; coding: sjis -*-
# Last updated: <2015/12/24 09:52:37 +0900>
#
# 塗り潰しアルゴリズム(Scanline Seed Fill Algorithm)の実験
# 画像の中をクリックすれば塗りつぶしができる。
# 画像の中をクリックすれば塗りつぶしできるはず。
#
# usage: ruby scanlineseedfill2.rb TEST.PNG
#
# 動作確認環境 : Windows7 x64 + Ruby 2.0.0p647 + DXRuby 1.4.2
#
# 以下参考ページ。
#
# ペイント・ルーチン (1)シード・フィル アルゴリズム
# http://fussy.web.fc2.com/algo/algo3-1.htm
#
# スキャンライン・シードフィル アルゴリズムによる塗り潰し
# http://www.serendip.ws/archives/4797

require 'dxruby'

# paint scanline seed fill
# @param sx [Integer] start x
# @param sy [Integer] start y
# @param paintcol [Array] paint color [a,r,g,b]
# @param img [Object] DXRuby Image
def paint_scanlineseedfill(sx, sy, paintcol, img)
  col = img[sx, sy]
  return if col == paintcol # 領域色と描画色が同じなら何もせずに戻る

  buf = []
  buf.push([sx, sy])

  while buf.length > 0
    lx, ly = buf.pop
    rx = lx
    next if img[lx, ly] != col # 処理済みシードなら無視

    # 左方向の境界を探す
    while 0 < lx
      break if img[lx - 1, ly] != col
      lx -= 1
    end

    # 右方向の境界を探す
    while rx < img.width - 1
      break if img[rx + 1, ly] != col
      rx += 1
    end

    # lx から rx までの線分を描画
    (lx..rx).each { |x| img[x, ly] = paintcol }

    # 真下のスキャンラインを操作
    if ly + 1 < img.height - 1
      scanline(lx, rx, ly + 1, col, img, buf)
    end

    # 真上のスキャンラインを操作
    if ly - 1 >= 0
      scanline(lx, rx, ly - 1, col, img, buf)
    end
  end
end

def scanline(lx, rx, ly, col, img, buf)
  while lx <= rx
    # 非領域色を飛ばす
    while lx <= rx
      break if img[lx, ly] == col
      lx += 1
    end

    break if rx < lx

    break if img[lx, ly] != col

    # 領域色を飛ばす
    while lx <= rx
      break if img[lx, ly] != col
      lx += 1
    end

    buf.push([lx - 1, ly])
  end
end

if ARGV.length != 1
  puts "usage: #{$0} PNG_File"
  exit
end

filepath = ARGV[0]
img = Image.load(filepath)

Window.loop do
  break if Input.keyPush?(K_ESCAPE)

  if Input.mousePush?(M_LBUTTON)
    mx = Input.mousePosX
    my = Input.mousePosY
    paint_scanlineseedfill(mx, my, [255, 0, 255, 0], img)
  end

  Window.draw(0, 0, img)
end