phpThumbnailerで背景を埋める処理

11月 18th, 2008 admin

Index of /projects/phpThumbnailer
というPHPで画像のリサイズをしてくれるライブラリがあって、これが1ファイルでできている上にリサイズするだけなら

PLAIN TEXT
PHP:
  1. <?
  2. include("../class.Thumbnail.php");
  3. $tn_image = new Thumbnail("sample.jpg", 0, 0, 25);
  4. $tn_image->save("tn_sample.jpg");
  5. ?>

というシンプルさなのでとても重宝しています。
使い方とか、キャッシュをする方法は以前書いたのでこちらをご覧下さい。

Webアプリには必要十分なのですが唯一つ、画像のリサイズで空白を埋めるというのをやってほしかったので拡張をしました。
たとえばw100xh50の画像を50x50にリサイズしたときに、結果として50x25の画像を受け取るのではなく、50x50の画像ができあがって、縦の足りない部分は背景色を表示するというような感じです。

thumbnail.inc.phpに下記のメソッドを追加して使ってください。

PLAIN TEXT
PHP:
  1. /**
  2.      * Resizes image to maxWidth x maxHeight
  3.      *
  4.      * @param int $maxWidth
  5.      * @param int $maxHeight
  6.      * @param string $color
  7.      */
  8.     function resizeFar($maxWidth = 0, $maxHeight = 0, $color = "FFFFFF") {
  9.         $this->resize($maxWidth, $maxHeight);
  10.  
  11.         if($maxWidth> $this->currentDimensions['width'] || $maxHeight> $this->currentDimensions['height']){
  12.             if(function_exists("ImageCreateTrueColor")) {
  13.                 $this->workingImage = ImageCreateTrueColor($maxWidth, $maxHeight);
  14.             }else {
  15.                 $this->workingImage = ImageCreate($maxWidth, $maxHeight);
  16.             }
  17.             $color = imagecolorallocate($this->workingImage, hexdec('0x' . $color{0} . $color{1}), hexdec('0x' . $color{2} . $color{3}), hexdec('0x' . $color{4} . $color{5}));
  18.             imageFill($this->workingImage,0,0,$color);
  19.  
  20.             ImageCopy(
  21.                 $this->workingImage,
  22.                 $this->newImage,
  23.                 ($maxWidth - $this->currentDimensions['width']) / 2,
  24.                 ($maxHeight - $this->currentDimensions['height']) / 2,
  25.                 0,
  26.                 0,
  27.                 $this->currentDimensions['width'],
  28.                 $this->currentDimensions['height']
  29.             );
  30.             $this->newImage = $this->workingImage;
  31.         $this->currentDimensions['width'] = $maxWidth;
  32.         $this->currentDimensions['height'] = $maxHeight;
  33.         }
  34.     }

Posted in PHP | No Comments »

幅優先探索

11月 12th, 2008 admin

昨日に続き「アルゴリズムとデータ構造シリーズ」です。今回は第10章「バックトラック法と幅優先探索」の幅優先探索です。

幅優先探索

前回やったバックトラック法はとてもパワフルなアルゴリズムなのですが、必ずしも最適解が求まるわけではないという問題によっては不都合な特徴もあります。そこで総当たりかつ最適な解をみつけるためのアルゴリズムが幅優先探索法になります。
幅優先探索は、その名のとおり幅を優先させた探索で、まず１回目の試行でできるすべてのパターンをためし、次に２回目の試行でできるすべてのパターンをためし・・・とやっていく方法です。
バックトラック法が木構造を右手法で巡回したのに対し、こちらは1個目のノードをすべて試す、そしたら次に2階層目のノードを試すとやっていく感じです。

コード

セブンパズルというパズルを解くコードを書きました。

PLAIN TEXT
RUBY:
  1. class Pattern
  2.   attr_accessor :hash, :pattern_from
  3.  
  4.   def initialize(hash, pattern_from)
  5.     @hash = hash
  6.     @pattern_from = pattern_from
  7.   end 
  8. end
  9.  
  10. class SevenPuzzle
  11.   def initialize
  12.     @history = Array.new
  13.     @ans = Marshal.dump([1,2,3,4,5,6,7,0])
  14.   end
  15.  
  16.   def save_history(pattern, pattern_from)
  17.     hash = Marshal.dump(pattern)
  18.     @history.each do |a|
  19.       return if a.hash == hash
  20.     end
  21.    
  22.     @history.push(Pattern.new(hash, pattern_from))
  23.   end
  24.  
  25.   def solve
  26.     pattern = Array.new(8)
  27.  
  28.     queue_bottom = 0
  29.     until @history.size == 0 do
  30.       hash = @history.shift.hash
  31.       return true if hash == @ans
  32.  
  33.       pattern = Marshal.load(hash)
  34.      
  35.       blank_pos = pattern.index(0)
  36.  
  37.       if blank_pos> 3
  38.         pattern[blank_pos] = pattern[blank_pos - 4]
  39.         pattern[blank_pos - 4] = 0
  40.         save_history(pattern, queue_bottom)
  41.         pattern = Marshal.load(hash)
  42.       end
  43.  
  44.       if blank_pos <4
  45.         pattern[blank_pos] = pattern[blank_pos + 4]
  46.         pattern[blank_pos + 4] = 0
  47.         save_history(pattern, queue_bottom)
  48.         pattern = Marshal.load(hash)
  49.       end
  50.  
  51.       if blank_pos != 0 && blank_pos != 4
  52.         pattern[blank_pos] = pattern[blank_pos - 1]
  53.         pattern[blank_pos - 1] = 0
  54.         save_history(pattern, queue_bottom)
  55.         pattern = Marshal.load(hash)
  56.       end
  57.  
  58.       if blank_pos != 3 && blank_pos != 7
  59.         pattern[blank_pos] = pattern[blank_pos + 1]
  60.         pattern[blank_pos + 1] = 0
  61.         save_history(pattern, queue_bottom)
  62.         pattern = Marshal.load(hash)
  63.       end
  64.      
  65.       queue_bottom += 1
  66.     end
  67.     return false
  68.   end
  69. end
  70.  
  71. #initial pattern
  72. pattern = [2,7,4,3,0,5,1,6]
  73.  
  74. p = SevenPuzzle.new
  75. p.save_history(pattern, -1)
  76.  
  77. if p.solve
  78.     p 'done'
  79. else
  80.     p 'not found'
  81. end

まとめ

今回はキューを使って解きました。バックトラック法がスタックを使っていたのにたいして、こちらがキューを使うというのがなんだか面白いです。データ構造でも対になっているものがあるんですね。

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

Posted in アルゴリズムとデータ構造 | No Comments »

バックトラック法

11月 11th, 2008 admin

久しぶりに「アルゴリズムとデータ構造シリーズ」です。今回は第10章「バックトラック法と幅優先探索」のバックトラック法です。

バックトラック法

ある解を求めるときに、考えられるパターンをすべて試しながら解く方法のひとつです。迷路の右手法をイメージするといいんじゃないでしょうか。パワープレイすぎてスマートさはありませんが、結局この方法が早かったり、この方法でないと解けなかったりします。以前ナンプレに挑戦したときも結局このバックトラック法を使いました。

コード

今回はエイトクイーン問題をバックトラック法で解くようにしました。

PLAIN TEXT
RUBY:
  1. class Qween
  2.   def initialize(n)
  3.     @size = n
  4.     @board = Array.new
  5.     @size.times do |i|
  6.       @board[i] = Array.new
  7.       @size.times do |j|
  8.         @board[i].push(nil)
  9.       end
  10.     end
  11.   end
  12.  
  13.   def check(y,x)
  14.  
  15.     (0...x).each do |i|
  16.       return nil unless @board[y][i].nil?
  17.     end
  18.  
  19.     (x+1).times do |i|
  20.       if (y-i)>= 0 && (x-i)>= 0
  21.         return nil unless @board[y-i][x-i].nil?
  22.       end
  23.  
  24.       if (y+i) <@size && (x-i)>= 0
  25.         return nil unless @board[y+i][x-i].nil?
  26.       end
  27.     end
  28.     true
  29.   end
  30.  
  31.   def solve(x)
  32.     return true if x == @size
  33.  
  34.     (0...@size).each do |i|
  35.       if check(i,x)
  36.         @board[i][x] = true
  37.  
  38.  
  39.         if solve(x+1)
  40.           return true
  41.         else
  42.           @board[i][x] = nil
  43.         end
  44.       end
  45.     end
  46.     return nil
  47.   end
  48.  
  49.   def show
  50.     @board.each do |row|
  51.       row.each do |c|
  52.         print c ? 'Q' : '-'
  53.         print ' '
  54.       end
  55.       print "\n"
  56.     end
  57.   end
  58. end
  59.  
  60. q = Qween.new(ARGV[0].to_i
  61. )
  62. q.solve(0)
  63. q.show

結果

PLAIN TEXT
CODE:
  1. Q - - - - - - -
  2. - - - - - - Q -
  3. - - - - Q - - -
  4. - - - - - - - Q
  5. - Q - - - - - -
  6. - - - Q - - - -
  7. - - - - - Q - -
  8. - - Q - - - - -

たしかにQが縦にも横にも斜めにも重ならないように配置されています。

まとめ

ちなみにNクイーン問題は４x4以上ならすべて解があるそうです。個人的には４x4の解が一番かっこよく見えるかな。クイーン同士が仲良さそうで

PLAIN TEXT
CODE:
  1. - - Q -
  2. Q - - -
  3. - - - Q
  4. - Q - -

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。

Posted in アルゴリズムとデータ構造 | 2 Comments »

「CPUの創りかた」のTD4製作に必要な部品リスト

11月 10th, 2008 admin

先日作り終えた、「CPUの創りかた」のTD4製作に必要な部品リストです。
今後作られる方の参考になればと思います。部品の値段だけみれば全部で10,000円以下ですが、1個ずつ買えるものばかりではないので、なんだかんだで20,000円ぐらいかかると思っておいたほうがよいと思います。

またお金に余裕のある方はブレッドボードでの製作をオススメします。製作時間を半分以下に短縮できるからです。

部品リスト


名前
必要個数
抵抗1/4W 100Ω 2
抵抗1/4W 1kΩ 10
抵抗1/4W 10kΩ 9
抵抗1/4W 100kΩ 4
抵抗1/4W 3.3kΩ 1
抵抗1/4W 33Ω 1
電解コンデンサ 10μF16V 2
無極性電解コンデンサ 10μF 16V 1
セラミックコンデンサ 0.1μF 12
ダイオードアレイ B1 technology D5-1C 16
LED赤 4
74HC10 1
74HC14 1
74HC32 1
74HC74 1
74HC153 2
74HC154 1
74HC161 4
74HC283 1
74HC540 1
上記IC用のICソケット（各サイズ）
基板 サンハヤト ICB-98GU 1
4連ディップスイッチ 1
8連ディップスイッチ 16
上記ディップスイッチ用ICソケット 17
押しスイッチ 2
切り替えスイッチ 2
DC5V安定化電源(秋月電子 GF12-US0520) 1
電源プラグ 1
リード線(AWG30) 1
<< オススメ品 >>
クロック確認用LED 1
アドレス確認用LED 4
基板のスペーサ 4

入手先

必要なものは、各種パーツ屋、秋月電子通商を利用しました。
またダイオードアレイのダイオードアレイ　B1 technology D5-1Cはマイクロデバイス株式会社で買いました。

Posted in 未分類 | No Comments »

CPUを創りました！ 第16回 CPUの創りかた報告

11月 10th, 2008 admin

CSNagoyaの勉強会で11月9日に「CPUの創りかた」を開催しましたので報告します。
今回で16回目になるのですが、ついにCPUが動くようになりました。
第1回の開催が今年の3月ですので約8ヶ月もかかったことになりますね。しかし動くとは思わなかった。

披露

では、早速今回作成したCPUであるTD4を代表するアプリケーションの一つ「LEDチカチカ」をお見せしましょう。

見所を解説

00:15

電源をいれているように見えますが電源ではなく、クロックをスタートさせています。
右上の4連ミドリLEDが現在読み込んでいるメモリのアドレスを2進数であらわしています。
赤色の4連LEDが出力です。今回は順番に光らせるということをしています。

00:43

最大の見せ場がやってきました。
なんと通常の1Hz駆動から10Hzにクロックアップしています。つまり最初の10倍の速度で動いているのです。なんというポテンシャル・・・

そのほかの解説

dsc00360.jpg
全体はこんな感じ。横幅が25cmぐらいあるので結構大きいです。
CPUを作ったと言いましたが、このなかに入力装置や出力装置があり、これ単体で使えるので「パソコンを作った」ともいえます。
dsc00354.jpg
これは入力装置です。4bitもあります。いわゆるキーボードですね。
dsc00353.jpg
これはメモリです。読み込み専用のハードディスクだと思ってください。128bitの大容量！
一番左下をゼロ番地にしたという地味なミスを犯しました。
dsc00355.jpg
これは出力装置です。モニターに相当します。これも4bitもあります。

TD4でプログラミング

TD4はかなり硬派なのでプログラミングは物理的にメモリを操作してプログラムします。
たとえば出力に1100を送りたいとなれば、命令は1101なので
0番地と1番地のメモリを11001101としてやります。
dsc00361.jpg
そして0番地と1番地を読み込んでやると・・・
dsc00362.jpg
赤色のLEDが1100なので右からON ON OFF OFFとなります。見えにくいですが、左上のミドリのLEDは一番右だけが光っていて、いま1番地を読み込んでいることを示しています。

まとめ

これでひとまず完成です。デバッグも数時間で終り、変な泥沼にはまることなくほっとしています。次回は独自のアプリをつくるなど、しばらくこれで遊ぶ予定です。

Posted in CSNAGOYA | 1 Comment »

« Previous Entries