ソートアルゴリズムの動きをgifに表示する

Bài đăng này đã không được cập nhật trong 2 năm

ソートアルゴリズムの動きを可視化したいので.gifファイルを作るためのプログラムを作成したい。方法として、２つの段階を踏む。一段回目は数値リストを座標の図として表した画像ファイルを生成するフェーズ。二段階目は生成した複数の画像からgifファイルを作成するフェーズ。第１段階から順に作成する

座標図を作成する

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]、右下が[最大値, 最大値]というように左上から右下に向かって座標の値が大きくなるという設計になっている。そのため、横軸に当たるインデックスはそのままでいいとして、縦軸の指定にはひねりが必要だ。縦軸の座標を求める式：縦軸の最大値ーリストの中身の値 縦軸の最大値は、０から始まっているので高さー１で求めることができるので、 png[ index, length - array[index] - 1]でピクセルを指定できる。

課題

ピクセル１つで１マスとして作成しているので点が非常に小さく、画像自体のサイズも小さい。
サイズを大きくしようとしてリストの長さを大きくしても点の小ささ自体は変わらないため、結局拡大しないと点が見えない。要は１ピクセル１マスで図を作成するのは無理があるという話解決方法としては

1マスを4, 9, 16ピクセルなどに設定する
作成した画像を、外部プログラムで拡大して保存する１は該当するピクセルを指定するのに手間がかかり、２は次の段階で使うGemで簡単にできそうなので、２を採用する。

gifを作成する

Gem

今回使用するのはRmagick だ。 rubyで画像ファイルを扱うgemとして有名なgemだ。

Rmagick

gifファイルの作り方

Magick::ImageList.new()でリストを作る
Magick::Image.read(".filename.png")で読み込む
２で読み込んだファイルをlist.push()でリストに追加する
list.delayで画像が切り替わる時間を設定する(1/100秒で設定)
list.write("filename.gif")でgifファイルとして保存する注意すべきは３で画像をリストに追加するとき Magick::Image.readでは画像を配列データで読み込んでいるため、そのままリストに追加することができない。なので追加するときは、

list.push(img[0])

としてやればいいらしい。

画像を拡大する

Rmagickには画像のサイズを変更する方法として resizeメソッド scaleメソッド thumbnailメソッド sampleメソッドの４つがあり、今回は画像の粗さなどは関係ないため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ファイルを作成するソートが完了したら２つめのクラスを呼び出し、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

できたファイル