ソートアルゴリズムの動きをgifに表示する
Bài đăng này đã không được cập nhật trong 3 năm
ソートアルゴリズムの動きを可視化したいので.gif
ファイルを作るためのプログラムを作成したい。
方法として、2つの段階を踏む。
一段回目は数値リストを座標の図として表した画像ファイルを生成するフェーズ。
二段階目は生成した複数の画像からgifファイルを作成するフェーズ。
第1段階から順に作成する
座標図を作成する
Gem
今回はchunky_pngというGemを使用する。 ピクセルごとにデータをいじってpngファイルを作成できるらしい。 数値を画像に反映したい今回の要件にピッタシだ。
Chunky_png
png
ファイルの作成方法
png = ChunkyPNG::Image.new(16, 16, ChunkyPNG::Color::TRANSPARENT)
png[1,1] = ChunkyPNG::Color.rgba(10, 20, 30, 128)
png[2,1] = ChunkyPNG::Color('black @ 0.5')
png.save('filename.png', :interlace => true)
まずChunkyPNG::Image.new(height, width, default-color)
で指定したサイズでdefault-color一色に設定された配列を作成し、
次に色を付けたいピクセルを指定して色を設定する。
最後に名前を設定して保存
これだけで簡単に作れる。
実装
条件として配列が以下を満たしていることを前提にして実装する
- 中身の値が0以上配列の長さ以下である
require 'chunky_png'
class ArrayToPng
def create array, name
length = array.length
png = ChunkyPNG::Image.new(length, length, ChunkyPNG::Color.rgb(255, 255, 255))
length.times do |i|
png[i, length - array[i] - 1] = ChunkyPNG::Color('black @ 0.5')
end
png.save("./img/#{name}.png", :interlace => true)
end
end
指定のサイズで白一色のピクセルのデータを作成し、
リストのインデックスを横軸、中身を縦軸して座標図になるようにピクセルを塗りつぶす。
このときに注意すべき点はピクセルの指定の仕方だ。
このGemでは一番左上が[0, 0]、右下が[最大値, 最大値]というように左上から右下に向かって座標の値が大きくなるという設計になっている。
そのため、横軸に当たるインデックスはそのままでいいとして、縦軸の指定にはひねりが必要だ。
縦軸の座標を求める式:縦軸の最大値ーリストの中身の値
縦軸の最大値は、0から始まっているので高さー1
で求めることができるので、
png[ index, length - array[index] - 1]
でピクセルを指定できる。
課題
- ピクセル1つで1マスとして作成しているので点が非常に小さく、画像自体のサイズも小さい。
- サイズを大きくしようとしてリストの長さを大きくしても点の小ささ自体は変わらないため、結局拡大しないと点が見えない。 要は1ピクセル1マスで図を作成するのは無理があるという話 解決方法としては
- 1マスを4, 9, 16ピクセルなどに設定する
- 作成した画像を、外部プログラムで拡大して保存する 1は該当するピクセルを指定するのに手間がかかり、 2は次の段階で使うGemで簡単にできそうなので、2を採用する。
gifを作成する
Gem
今回使用するのはRmagick だ。 rubyで画像ファイルを扱うgemとして有名なgemだ。
Rmagick
gifファイルの作り方
Magick::ImageList.new()
でリストを作るMagick::Image.read(".filename.png")
で読み込む- 2で読み込んだファイルを
list.push()
でリストに追加する list.delay
で画像が切り替わる時間を設定する(1/100秒で設定)list.write("filename.gif")
でgifファイルとして保存する 注意すべきは3で画像をリストに追加するときMagick::Image.read
では画像を配列データで読み込んでいるため、そのままリストに追加することができない。 なので追加するときは、
list.push(img[0])
としてやればいいらしい。
画像を拡大する
Rmagickには画像のサイズを変更する方法として resizeメソッド scaleメソッド thumbnailメソッド sampleメソッド の4つがあり、今回は画像の粗さなどは関係ないためsampleメソッドを使用する それぞれの特色はこちらのサイトを参照 サイズ変更は以下のように行う
img.sample(倍率)
実装
まず条件として、gifに使用する画像データを一つのフォルダに保存しておき、 最初のフレームから順に、0.png, 1.png, 2.png・・・という名前で保存する。
require 'rubygems'
require 'rmagick'
class CreateGif
def create max, name
list = Magick::ImageList.new
(max + 1).times do |i|
list.push Magick::Image.read("./img/#{i}.png")[0].sample 4
end
list.delay = 5
list.write "./gif/#{name}.gif"
end
end
使用するまで
使い方
ソートのアルゴリズムの中で、数値に変更があったときに毎回一つ目のクラスを呼び出し、pngファイルを作成する ソートが完了したら2つめのクラスを呼び出し、gifファイルを作成する。
例
奇偶転置ソートで実際に使ってみた ソートのアルゴリズムは以下の通り
def odd_even array
flag = true
process = 0
while flag
flag = false
1.step(array.length - 1, 2) do |i|
if array[i] < array[i - 1]
array[i], array[i - 1] = array[i - 1], array[i]
flag = true
process += 1
ArrayToPng.new.create array, process
end
end
2.step(array.length - 1, 2) do |i|
if array[i] < array[i - 1]
array[i], array[i - 1] = array[i - 1], array[i]
flag = true
process += 1
ArrayToPng.new.create array, process
end
end
end
CreateGif.new.create process, "oddeven"
end
できたファイル
All rights reserved