スキャンラインシードフィルの実験その2(アルゴリズム高速化版)

scanlineseedfill2.rb

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

require 'dxruby'

# 線分からシードを探してバッファに登録
# @param lx [Integer] 線分のx座標の範囲左側
# @param rx [Integer] 線分のx座標の範囲右側
# @param y [Integer] 線分のy座標
# @param oy [Integer] 親ラインy座標
# @param col [Array] 領域色
# @param img [Object] DXRuby Image
def scanline(lx, rx, y, oy, col, buf, img)
  while lx <= rx
    # 非領域色を飛ばす
    while lx < rx
      break if img[lx, y] == col
      lx += 1
    end

    break if img[lx, y] != col
    tlx = lx

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

    buf.push({ :lx => tlx, :rx => (lx - 1), :y => y, :oy => oy })
  end
end

# スキャンラインシードフィルで塗りつぶす
# @param x [Integer] 開始座標 x
# @param y [Integer] 開始座標 y
# @param paintcol [Array] 描画色
# @param img [Object] DXRuby Image
def paint_scanlineseedfill2(x, y, paintcol, img)
  col = img[x, y]
  return if col == paintcol # 領域色と描画色が同じなら何もせずに戻る

  buf = []
  buf.push({ :lx => x, :rx => x, :y => y, :oy => y })

  while buf.length > 0
    d = buf.pop
    lx = d[:lx]
    rx = d[:rx]
    ly = d[:y]
    oy = d[:oy]

    lxsav = lx - 1
    rxsav = rx + 1

    # 処理済みのシードなら無視
    next if img[lx, ly] != col

    # 左方向の境界を探す
    while lx > 0
      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 do |x|
      img[x, ly] = paintcol
    end

    # 真上のスキャンラインを走査
    if ly - 1 >= 0
      if ly - 1 == oy
        scanline(lx, lxsav, ly - 1, ly, col, buf, img)
        scanline(rxsav, rx, ly - 1, ly, col, buf, img)
      else
        scanline(lx, rx, ly - 1, ly, col, buf, img)
      end
    end

    # 真下のスキャンラインを走査
    if ly + 1 <= img.height - 1
      if ly + 1 == oy
        scanline(lx, lxsav, ly + 1, ly, col, buf, img)
        scanline(rxsav, rx, ly + 1, ly, col, buf, img)
      else
        scanline(lx, rx, ly + 1, ly, col, buf, img)
      end
    end
  end
end

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

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

collist = [
  C_GREEN,
  C_RED,
  C_BLUE
]
colidx = 0

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

  if Input.keyPush?(K_SPACE)
    colidx = (colidx + 1) % collist.length
  end

  if Input.mousePush?(M_LBUTTON)
    mx = Input.mousePosX
    my = Input.mousePosY
    fg_color = collist[colidx]
    paint_scanlineseedfill2(mx, my, fg_color, img)
  end

  Window.draw(0, 0, img)
end

テスト画像