Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
スキャンラインシードフィルの実験その2(アルゴリズム高速化版)
#!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
@mieki256
Copy link
Author

mieki256 commented Dec 24, 2015

テスト画像

test

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment