potraceをjavascriptに移植した

生存報告

 ( ^ω^)とりあえず生きてます。

potraceとは

 potraceとはラスター画像からSVG等のベクター画像を作成するソフトです。無料で使えてソースも公開されているオープンソースなソフトです(参考資料1)。元はCで書かれていますが、pythonActionScriptC#に移植されていたりします。

だから何ができるの?

左が元のビットマップ画像、右がそれをpotraceでトレースした画像

C→javascript(´・ω・`)ActionScriptJavaScript(゚∀゚)

 ActionScriptJavaScriptは兄弟みたいなものなので移植はとっても簡単です。今回は参考資料2をパクって参考にしてjavascriptに移植してみました。

処理フロー

  1. imgタグで画像を読み込み
  2. 画像をcanvasに転写
  3. 画像をグレースケールに変換
  4. 画像を二値化
  5. 画像の輪郭の数だけpathを取得(potrace)
  6. よく分からない処理をしてベジェ曲線のポイントリストを作成(potrace)
  7. ベジェ曲線canvasに描画

6のよく分からない処理は参考資料1のTechnical documentationのpdfを見てください。私は見てもさっぱりでした。(;^ω^)

コード

上記の処理フローの6番は参考資料2のActionScriptと全く同じです。

canvasにフィルターをかける

 canvasからイメージのピクセルを取得したり、設定したりする方法は参考資料3に載っています。contextからgetImageDataするとピクセルのrgbaが並んで入った配列が得られます。結果として配列の長さはピクセル数×4となります。
 このピクセルデータに対してactionscriptのColorMatrixFilter(参考資料4)+applyfilterと同様の処理をするスクリプトが以下です。ピクセルデータdataに対してrectの範囲でフィルターfをかけます。

applyFilter:function(rect,pt,f){
	for(var y=rect.y; y < rect.y +rect.height;y++){
		for(var x = rect.x;x < rect.x + rect.width;x++){
			var r =this._data.data[x*4 +y*this.width*4],
				g = this._data.data[x*4 +y*this.width*4+1] ,
				b = this._data.data[x*4 +y*this.width*4+2] ,
				a = this._data.data[x*4 +y*this.width*4+3];
			this._data.data[x*4 +y*this.width*4] = r*f[0] + g*f[1] + b*f[2] +a*f[3]+f[4]; //Rnew
			this._data.data[x*4 +y*this.width*4+1] = r*f[5] + g*f[6] + b*f[7] +a*f[8]+f[9]; //Gnew
			this._data.data[x*4 +y*this.width*4+2] = r*f[10] + g*f[11] + b*f[12] +a*f[13]+f[14]; //Bnew
			this._data.data[x*4 +y*this.width*4+3] = r*f[15] + g*f[16] + b*f[17] +a*f[18]+f[19]; //Anew
		}
	}
},
画像のグレースケールと二値化

 上記のapplyfilterに以下のフィルターをかけます。

var filter = [
	0.298912, 0.586611, 0.114478, 0, 0,
	0.298912 ,0.586611, 0.114478 ,0 ,0,
	0.298912 ,0.586611, 0.114478 ,0 ,0,
	0 , 0, 0, 1, 0
];

 この後、rgbのいずれかのピクセル値に対してしきい値をとると画像を二値化できます。

XOR

 画像を二値化すると色は白と黒だけになり、この状態で反転させるとお互いの領域が逆転します。これをパスのぐるりでやると以下のようにパスで囲まれた黒の領域が消滅します。この時、パスで囲まれた白の領域は反転して黒となり、パス化されるのを待ちます。

□■■■□
□□■■□
□□■■□
□■■■□

■■■■□
■■■■□ ↓
□□■■□
□■■■□

■■■■□
■■■■□
■■■■□
■■■■□ ↓

■■■■□
■■■■□
□□□□□ ↑
□□□□□ 

□□□□□ ↑
□□□□□
□□□□□ 
□□□□□ 

実際のサンプル

 以下の画像のようにトレースすることが出来ました。対応ブラウザはFireFoxchromesafariIE9です。

URL:http://www28095u.sakura.ne.jp/jstrace/(追記 2013/06/28 Chromeで動かなくなってしまいました。サンプルは下記の追記を参照してください)

実際のサンプルの注意点

もっさりしているのは仕様です。おそらくこれ以上劇的には早くなりません。画像は最低でも1pxの白い枠取りがされている必要があります。ローカルに保存しても動きません。画像はインターネットから拝借いたしました。コードはnitoyon氏とPeter Selinger.氏がすべての権利を有します。

追記 2013/06/28 サンプルコード

defghi1977氏によりコードの高速化とサンプルの補充が行われました。感謝。
 http://www.h2.dion.ne.jp/~defghi/img2svg/potraceHtml.htm

JSとcanvasで縦組みエンジンを作ろう( ・∀・) その3


例によってサンプルのみです。Google App Engineでギコ文庫というアプリを作ってみました。

ギコ文庫http://gikobunko.appspot.com


ギコ文庫はWebテキストを縦書き+アンチエリアスで読めるかも知れないサービスです。

URLを入れて実行を押すと、htmlが生成される。

js側の方は調整してないので表示がグダグダなのがわかる。
縦書き用のフォントはIPAフォントのダウンロード || OSS iPediaのIPAexフォントを利用した。ライセンスは詳しく調べてない。問題ありそう。

細かい解説や技術情報は今週末になると思います。あくまでサンプルです。実用に耐えられるようには出来ていません。

JSとcanvasで縦組みエンジンを作ろう( ・∀・) その1


○| ̄|_ <編集中に記事が消えました…サンプルのみです。

サンプル

 青空文庫から宮沢賢治、「グスコーブドリの伝記」をサンプルに選びました(参考資料1)。IEFireFoxChromeSafariで見れると思います。マウスホイールで拡大、縮小が出来ます。

 サンプル:グスコーブドリの伝記

参考資料

  1. 宮沢賢治 グスコーブドリの伝記


追記:2010/5/17,24

縦組

文字を縦に組み上げることを縦組といいます。以下の資料が詳しいです。

日本語組版処理の要件(日本語版)


この文書は,CSSSVGおよびXSL-FOなどの技術で実現が求められる一般的な日本語組版の要件を記述したものです.この文書は,主としてJIS X 4051(日本語組版規則)に基づいていますが,一部,JIS X 4051に記載されていない事項にも言及しています.

日本語組版では文字は正方形の外枠を持ちます。

これはバウンディングボックスとは違います。縦組の場合、一辺は送り幅と同じに、センターラインを分割するように位置します。
縦書きフォントにおいて、送り幅は全グリフ共通で、以下のように上辺と下辺が一致します。

以下にバウンディングボックス、外枠、文字、センターラインをtypeface.jsでの表現を示します。
 

uuCanvas

typeface.jsがieに用意したvmlバックエンドは汎用性が有りません。置き換え可能な物にexcanvas.jsが有りますが、遅すぎて使い物になりませでした。
そこでFlashで描画するuuCanvas.jsを用います。国産の実用性のあるJSライブラリです。

uuCanvas.js - README

uuCanvas.jsHTML5::Canvas 互換機能を提供する JavaScript ライブラリです。

使用方法はリンク先を参照してください。

文字の大きさ

 typeface.jsにおけるこの議論は少々複雑です。
 freetypeによって1EM=256unit定義のfontより抜き出されたグリフは解像度1000dpiの仮想空間に100ptで展開されます。この時、x[unit]の大きさは、参考資料1より


になります。typeface.jsではこの座標値を縮小して表示します。72dpiの画面に12ptで表示される大きさx'[px]は

となります。これは

と等しいですが、typeface.jsでは大きく描いて、scaleで縮小しています。

簡単な禁則処理

 「、」や「。」が行頭に現れると見栄えが悪いので、行末に書きます。このように特定の約物の位置を調整することを禁則処理といいます。サンプルでは「、」と「。」が行末にこないようにmatch関数で調べて禁則処理を行っています。

行間、行数

 一行に43文字、行間は適度に開けています。詳しい基本版面の設計は後に回します。

参考資料

  1. TrueType Fundamentals

typeface.jsで日本語を

 Web製作者がクライアントのフォントレンダリングに手を加えることは今のところ出来ない。しかし、typeface.jsを使うとそれを擬似的に実現することができる。

typeface.js -- Rendering text with Javascript, <canvas>, and VML


With typeface.js you can embed custom fonts in your web pages so you don't have to render text to images.

仕組みはこうである。使用するフォントのFontファイルより輪郭のベクターデータ、メトリクス、著作情報等を抜き出し、それをJSON形式にして、jsファイルに書き込む。使用したいhtmlでそれを読み込み、jsのレンダリングエンジンが、対象テキストから分解された文字をcanvasに描く。最後にcanvasを対象テキストと置き換える。

typeface.jsはフォントを変換する際に、予め大きいポイント(以下pt)で行い、それをjsの方で縮小することでアンチエイリアスを実現する。

なんとも強引な方法ではあるが、一応の解決を見る事はできる。問題はFontファイルからJSON形式のフォントに変換するところだが、このあたりはオンラインの変換ツールを用意することで解決している。ただし、このオンライン変換ツールは日本語には対応していない。変換は出来るのだが、実際に試してみると上手くいかない。配布されている変換スクリプトも、動作させることは難しい(前回の記事参照のこと)。

そこで今回は、FontファイルからJSON形式のフォントを作成し、実際に表示させるところまでを行った。

準備

 フォントライブラリには定番のFreeType2(以下FreeType)を、言語にはC++を使用し、CUIのアプリケーションを作成する。FreeTypeは参考資料1を見て、環境にセットアップしておく。変換するフォントはMS Pゴシックを使用する。TTCファイルの分割には参考資料2を利用する。

typeface.jsの修正

 typeface.jsではグリフのインデックスに文字そのものを利用している。これではUnicode対応のエディタ等でしか開けない等、不便が多いので10進のUnicodeにする。以下のようにface.glyphsのインデックスにはすべて、charCodeAt(0)を付ける。

//var glyph = face.glyphs[char];
var glyph = face.glyphs[char.charCodeAt(0)];

文字サイズの設定

 ライブラリ、フォントファイルの読み込みのコードの後には、文字サイズの設定が必要である。これをしないとパスの取得時におかしくなる。また、ここで設定する大きさでフォントからベクター、ラスターのどちらが読み込まれるかが決定する。

	error = FT_Set_Char_Size(
		face, /* handle to face object */
		100*64, /* 文字幅:ptの1/64の大きさを設定する。今は100ptに設定してある。 */
		100*64, /* char_height in 1/64th of points */
		1000, /* horizontal device resolution */
		1000); /* vertical device resolution */

グリフを読み込み

 任意のグリフのベクターデータを読みだすには以下の手順を取る。

  1. cmapで支持されたエンコーディングで文字を文字コードに変換する。 //Unicode: A -> 65
  2. FT_Load_Char関数で文字コードを元に、faceにグリフをセットする。
  3. faceのグリフスロットよりFT_Get_Glyph関数でグリフgを取り出す。
  4. g->formatにてグリフのフォーマットを確認し、アウトランであることを確認する。
  5. グリフgをアウトライングリフ(FT_OutlineGlyph)ogにキャストする。
  6. og->outlineにてアウトラインデータを取り出す。
  7. FT_Outline_Decompose関数を使用し、パス形式で出力する。同関数の使い方は参考資料3にサンプルがある。注意点として、文字サイズを64倍したものを設定しているので、出力時には64で割ったものを出す必要がある。

 格納されているグリフを順次処理するには上記の処理を以下の処理で括ればいい。

  1. FT_Get_First_Char関数で最初の文字コードとグリフインデックス(cmapにて文字コードにつけられているインデックス番号のこと)を読みだす。
  2. 上記の処理を行う。
  3. FT_Get_Next_Char関数を使用して次の文字の文字コードとグリフインデックスを読みだす。
  4. グリフインデックスが0になるまで処理を繰り返す。

グリフ固有のメトリクス

 メトリクスとはグリフの位置関係情報のことである。アセンダやディセンダ、バウンディングボックス(文字に内接する長方形のこと)といったものがそれに当たる。このあたりの解説はFreeTypeチュートリアルの2(参考資料4)に詳しい。

以下の画像はwikipediaの「書体」の項目より引用させてもらっている。


typeface.jsでは各グリフのバウンディングボックス情報と送り幅(advance)を必要とする。これは以下のようなコードでとることができる。

FT_BBox bbox;
FT_Glyph_Get_CBox( g, FT_GLYPH_BBOX_UNSCALED, &bbox );
fprintf(fw,"\"x_min\":%.2f",DOUBLE_FROM_26_6(bbox.xMin));

この方法でとるバウンディングボックス情報とface->glyph->metricsでとることのできる情報から求まるバウンディングボックス情報は同じである。送り幅はこちらの方法でとる。

fprintf(fw,",\"ha\":%.2f,\n",DOUBLE_FROM_26_6(face->glyph->metrics.horiAdvance));

全体のメトリクス

 typeface.jsはディセンダやアセンダ、行間、全グリフの最小、最大バウンディングボックス情報といったものを求める。ここで注意するのはスケーリングされた情報を取る必要がある点である。スケーリングされたディセンダやアセンダ、行間はface->size->metricsより取得出来る。

//face->ascender; 
DOUBLE_FROM_26_6(face->size->metrics.ascender);

JSON形式のフォントには最小、最大バウンディングボックス情報の項目もあるが、これらはtypeface.jsでは必要とされない。その為適当で良い。

著作情報及びその他の情報

 familyName、css〜のみが必要とされる。original_font_informationにある著作情報はレンダリング時には必要とされない。時間があれば付け加えればいい。

サンプルコード

 長いので省略。必要とあればコメント欄へ。

結果

 MSPゴシックの大きさは約8MB、これを今回プログラムで変換したところ約20MBもの大きさとなった。これを修正したtypeface.jsと共に読み込み、適当なテキストを充てがった結果が以下である。

16pxで表示(上がネイティブ、下がレンダリングテキスト)

12pxで表示(上がネイティブ、下がレンダリングテキスト)

レンダリングの結果は上々といったところだ。感触としてはPDFで文字を表示したときに似ている。少なくともネイティブで表示した時よりも好感が持てるだろう。ただ、フォントサイズがあまりにも巨大なために実用性は無きに等しい。これを解決するには、テキストごとにフォントを作成するしかないが、これはそんなに難しくはないだろう。

次回以降の課題としては、これを利用した縦書きへの挑戦が上げられる。JSでの縦書き処理を行うスクリプトは幾つかあるが、フォントの縦書きレンダリングにまで踏み込んだ物は現在確認出来ていない。期待しておいて欲しい。

ベクター→ビットマップ

白黒はっきりつける程度の能力

              /\___
         |ヽ.   , '"::|l 閻 l|::::::`ヽ./|
        |:::::\'::::,.r-y-y-、___/:::::/
        |::_r'ァ'-':: ̄i:::::::i::::`ーヽ二<]
       [>r'7:::/::ヽ!、ハ::::ハ_;!::ィハ:::::Y::Yト、
          Y:::::|:ハア;ニ; レ' ,ア;ニ;ヽ!ハ|:::::| iヽ.
      //レヘレi ! !_r!   !_r! ノ|::ト、|:::| \〉
        |__|/ く|:::|"       "|:::|ソ::::;イ
          |::i>、   ̄  ,.イ|::|ヘ:::::::|
          ゝイ_;!ィ`7二T<、!_|::ハヘ/
            ,'  .Y/::::`T´::::::7ゝヽ.!
         .〈  /i::::::::Ф:::::::::|l   〉
           ,' ` ハ::::::::Ф:::::::::7 ´ ',
        /   く::::::::::ハ:::::::::::>   ヽ.
         .く`ヽ. /アー-'T'ー‐イ\  />、
(参考資料1)


 東方というゲームには「四季映姫・ヤマザナドゥ」というキャラクターがいて、何でも物事の白黒をはっきり付けることができるそうです(参考資料2)。

近年のプログラム言語では殆どがグラフィカルな出力APIを持っていて、ディスプレイ上に四角や丸や三角を描くことができます。ところがディスプレイは、実際にはピクセルと呼ばれる格子に区切られており、そこに絵を描くにはどのピクセルにどの色を塗るかを判断しなくてはいけません。ここで問題。四角や丸の中を塗りつぶすのはどうしているのでしょうか。

 このブログは開設当初から文字について扱ってきました。ですからこの問題を文字について考えてみます。

 文字に服するOpenTypeフォントにおいて、文字の形状は二次ベジェ曲線の連続で表されます(参考資料3)。これらの曲線の終端は、次の曲線の始点となり、最終的には最初の曲線の始点が最後の曲線の終点となります。こうして文字を形作る輪郭の一つができます。複雑な文字の場合はこの輪郭(パス)が複数存在します。下の図は小文字の「i」ですが、輪郭が二つあるのが分かります。

 これで文字の描画は終了とはなりません。次にパスの中を塗りつぶさなくてはいけません。TrueTypeの仕様書は、この問題の解決のヒントを教えてくれました。下の図を見てください。

塗りつぶさない部分から無限遠に向かって直線を引いたとき、パスとの交差数は必ず偶数になります。一方、塗りつぶす部分は必ず奇数になります。つまり、ピクセルごとに無限遠に向かって直線を引き、交差数を調べてピクセルを塗りつぶすかそうでないかを判断すればいいことになります。

 そんなわけで、今回は簡単な二次ベジェ曲線で構成されるパスを定義し、その中を塗りつぶす「四季映姫・ヤマザナドゥ(ラスタライザ)」を作ってみることにしました。

canvasで二次ベジェ曲線

 前回に引き続き、グラフィカル要素にはcanvas要素を、制御プログラムにはJavaScriptを使用しました。CanvasAPIには二次ベジェ曲線を描く関数(quadraticCurveTo)がすでに用意されています。

BezierCurve2.prototype = {
	_p1x:0,//始点
	_p1y:0,
	_p2x:0,//制御点
	_p2y:0,
	_p3x:0,//終点
	_p3y:0,
	draw:function(context){
		context.beginPath();
		context.lineWidth =1;
		context.moveTo(this._p1x,this._p1y);
		context.quadraticCurveTo(this._p2x,this._p2y,this._p3x,this._p3y);
		context.stroke();
	}
}

二次ベジェ曲線と直線の交点

 二次ベジェ曲線は複雑な定義を持ちますが、その正体は二次曲線です(参考資料4)。ですから二次ベジェ曲線と直線の交点というのは放物線と直線の交点の問題になります。これは判別式の符号がどうであるかによってすぐわかります。詳細は参考資料5を見てください。

//線分(x0,y0)(x1,y1)を直線cx+by+e=0の式に
Vector.prototype = {
	cal:function(){
		this._c = this._y0 - this._y1;
		this._d = this._x1 - this._x0;
		this._e = (this._y1 - this._y0) * this._x0 - (this._x1 - this._x0)*this._y0;
	}
}

//ベジェ曲線と線分は交差しているか?
function isAcross(v,bc2){
	var m = v._d*bc2._p3y + v._d*bc2._p1y + v._c*bc2._p3x + v._c*bc2._p1x - 2*v._d*bc2._p2y - 2*v._c*bc2._p2x;
	var n = -2*v._d*bc2._p1y - 2*v._c*bc2._p1x + 2*v._d*bc2._p2y + 2*v._c*bc2._p2x;
	var l = v._d*bc2._p1y + v._c*bc2._p1x + v._e;


	var D = n*n - 4*m*l;
	if( D>0 ){

		D = Math.sqrt(D);
		var t0 = 0.5*(-n+D)/m;
		var t1 = 0.5*(-n-D)/m;
		var count =0;

		//解が0〜1にあれば交点
		if( t0>=0 && t0<=1 ){
			var x = (1-t0)*(1-t0)*bc2._p1x +2*t0*(1-t0)*bc2._p2x + t0*t0 *bc2._p3x;
			var y = (1-t0)*(1-t0)*bc2._p1y +2*t0*(1-t0)*bc2._p2y + t0*t0 *bc2._p3y;

			if(Math.min(v._x0,v._x1) < x && x < Math.max(v._x0,v._x1)){
				if(Math.min(v._y0,v._y1) < y && y < Math.max(v._y0,v._y1)){
					count++;
				}
			}

		}
		if( t1>=0 && t1<=1 ){
			var x = (1-t1)*(1-t1)*bc2._p1x +2*t1*(1-t1)*bc2._p2x + t1*t1 *bc2._p3x;
			var y = (1-t1)*(1-t1)*bc2._p1y +2*t1*(1-t1)*bc2._p2y + t1*t1 *bc2._p3y;

			if(Math.min(v._x0,v._x1) < x && x < Math.max(v._x0,v._x1)){
				if(Math.min(v._y0,v._y1) < y && y < Math.max(v._y0,v._y1)){
					count++;
				}
			}
		}
		return count;
		
	}else if(D==0){
		var t2 = 0.5*-n/m;
		if( t2>=0 && t2<=1 ){
			var x = (1-t2)*(1-t2)*bc2._p1x +2*t2*(1-t2)*bc2._p2x + t2*t2 *bc2._p3x;
			var y = (1-t2)*(1-t2)*bc2._p1y +2*t2*(1-t2)*bc2._p2y + t2*t2 *bc2._p3y;
			if(Math.min(v._x0,v._x1) < x && x < Math.max(v._x0,v._x1)){
				if(Math.min(v._y0,v._y1) < y && y < Math.max(v._y0,v._y1)){
					return 1;
				}
			}else{
				return 0;
			}
		}else{
			return 0;
		}
	}else{
		//交点なし
		return 0;
	}
}

グリッドを描いて仮想ピクセルにする

 わかりやすいようにグリッドを描いて、その中を塗りつぶすことにします。

//グリッドを描く
function drawGrid(context){
	context.strokeStyle="rgb(100, 100, 100)";
	//縦線を引く
	for(var i=0;i<1000;i=i+gridSpace){
		context.beginPath();
		context.lineWidth =1 ;
		context.moveTo(i,0);
		context.lineTo(i,1000);
		context.stroke();
	}
	//横線を引く
	for(var i=0;i<1000;i=i+gridSpace){
		context.beginPath();
		context.lineWidth =1 ;
		context.moveTo(0,i);
		context.lineTo(1000,i);
		context.stroke();
	}
}

四季映姫・ヤマザナドゥ(ラスタライザ)

 準備は完了です。あとは白黒はっきり付けるだけです。

//bc2,bc2_2は輪郭を作っている曲線オブジェクト。時間がなくてグローバルにしてしまいました。
function rasterize(context){
	drawGrid(context);
	v = new Vector(999,999,0,0);

	for(var i=0;i<1000;i=i+gridSpace){
		for(var j=0;j<1000;j=j+gridSpace){
			var count=0;
			v.set(i+gridSpace/2,j+gridSpace/2,2);
			count+=isAcross(v,bc2);
			count+=isAcross(v,bc2_2);
			if(count%2 == 1){
				context.fillStyle="rgb(0, 0, 0)";
				context.fillRect(i, j, gridSpace, gridSpace);
			}
		}
	}
}

サンプル

 赤い点はドラッグしたら動きます。離れた点は制御点です。

=>Be'zier Curve Test

反省点

  • クソみたいなコード
  • 重い
  • 英語読めない

Canvasに色々描いてみた

canvas要素

 HTMLの仕様に図形を描くことができるcanvas要素というものがあります(参考資料1)。JavaScriptとの親和性がとってもいいのが特徴なのです。ここに色々描いて現実逃避してみます。

画面ぴったりに

 どうでもいいことなのですが、canvasの大きさを画面ぴったりにします。bodyのマージンとパディングを0にすることが必要です。以下のコードはjQueryが必要です。

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=shift_jis">
<title></title>
<script language="javascript" type="text/javascript" src="jquery-1.4.2.min.js">
</script>
<script language="javascript" type="text/javascript" src="init.js">
</script>
</head>
<body id="body1" onload="init();">
</body>
</html>
function init(){
	var c=canvasHWSet();
}

function canvasHWSet(){
	$(document.body).css({"margin":0,"padding":0});//重要!
	var width = $(document.body).width();
	var height = $(window).height();
	var canvas = $("<canvas id='canvas2'><canvas>").css({
		"cursor":"pointer"
	});
	canvas.attr("width",width);
	canvas.attr("height",height);

	$(document.body).append(canvas);
	return [canvas,width,height];
};

ベクトルクラス

 ベクトルクラスを定義して、描画メソッドを追加します。これで簡単にベクトルを描くことができます。x0,y0からx1,y1に向かう定義です。drawメソッドはコンテキストを引数に取り、それに対して自身を描画します。

function Vector() {
    this.initialize.apply(this, arguments);
}
Vector.prototype = {
	initialize:function(x0,y0,x1,y1){
		this._x0 = x0;
		this._y0 = y0;
		this._x1 = x1;
		this._y1 = y1;
	},
	_x0:0,
	_y0:0,
	_x1:0,
	_y1:0,
	draw:function(context){
		context.beginPath();
		context.lineWidth =1;
		context.moveTo(this._x0,this._y0);
		context.lineTo(this._x1,this._y1);
		context.stroke();
	},
	clone:function(){
		var v = new Vector(this._x0,this._y0,this._x1,this._y1);
		return v;
	}
}

function init(){
	var c=canvasHWSet();
	var context = c[0].get(0).getContext("2d");
	var nv = new Vector(100,100,200,200);
	nv.draw(context);

ベクトルの向きを変える

 あるベクトルを角度θだけ向きを変えるには回転の概念を使います。詳しくは参考資料3を見てください。あるベクトルXの終点から角度θだけ回転させた同じ大きさのベクトルYを得るには、Xを原点に持って行き、そこから回転をかけて、それをXの終点に持っていくという操作をします。なぜこんな面倒な関数が必要なのかは後でわかります。

//このメソッドは今のベクトルに角度deg[°]だけ回転させ、さらにその始点を今のベクトルの終点からにしたベクトルをnewして返す。
Vector.prototype = {
	newFromEndPointRotate:function(deg){
		var rad = 0.0174532925 * deg;//degreeをradianに変換する
		var xx = this._x1 -this._x0;
		var yy = this._y1 -this._y0;
		var x = xx * Math.cos(rad) - yy * Math.sin(rad);
		var y = xx * Math.sin(rad) + yy * Math.cos(rad);
		return (new Vector(this._x1 , this._y1,this._x1 + x,this._y1 + y));
	}
}

L-system

 今回はcanvasフラクタル図形を描いてみます。フラクタル図形を簡単に描くためにL-systemと呼ばれる仕組みを利用します。以下にwikipedia(参考資料2)の例を挙げます。

例 2:フィボナッチ数列
  V : A, B
  S : なし
  初期値: A
  規則 : (A → B), (B → AB)

計算を進めると、以下のような文字列となる。
  n = 0 : A
  n = 1 : B
  n = 2 : AB
  n = 3 : BAB
  n = 4 : ABBAB
  n = 5 : BABABBAB
この文字列の各文字数を n=0 から順に数えると、フィボナッチ数列(1 1 2 3 5 8 13 21 34 55 89 …)となっている。

 要は文字列の置換えの繰り返しです。ただし、規則は同時に適用させることに注意してください。単純にreplaceしてはいけません。以下の関数はwikipediaのコッホ曲線の規則を参考にして作成したものです。初期値と回数を引数にとり、返値として置き換え後の文字列を返します。

function makeKochCurve(n,omega){
	var text=omega;
	for(var i=0;i<n;i++){
		var buff="";
		for(var j=0;j<text.length;j++){
			switch(text.charAt(j)){
			case "F":
				buff +="F+F-F-F+F";break;
			case "-":
			case "+":
				buff +=text.charAt(j);
			}
		}
		text = buff;
	}
	return text;
}

コッホ曲線を描く

 wikipediaを参考にしてコッホ曲線を描いてみます。文字列の置き換えは先程作成しました。次はこの文字列を図形に置き換える必要があります。文字列の中の+と−は現在のベクトルから90°または-90°回転させる命令です。これらを簡単に行うのがベクトルクラスのnewFromEndPointRotateメソッドです。これによって現在のベクトルから簡単に回転したベクトルを得ることができます。

function onClick(event){
	var context =  event.data.c[0].get(0).getContext("2d");
	var test =makeKochCurve(3,"F");
	var cv = false; //current vector
	var ca =false; //current angle

	for(var i=0;i<test.length;i++){
		switch(test.charAt(i)){
		case "F":
			if(!cv){
				//Y軸は下に向かって正。なのでそのままだと下向きなる。よって図形を上下反転させるためにマイナスである。
				cv = new Vector(event.pageX,event.pageY,event.pageX -10,event.pageY);
				cv.draw(context);
			}else{
				cv = cv.newFromEndPointRotate(ca);
				cv.draw(context);
			}
			ca = 0;
			break;
		case "-":ca -= 90;break;
		case "+":ca +=  90;break;
		}
	}
}

サンプル:クリックした場所から図形を描きます(FireFoxのみ確認)
=>http://www28095u.sakura.ne.jp/lsystem/makeKochCurve/

シェルピンスキーの三角形を描く

 setInterval関数を利用して、1ベクトルづつ描いていくのを眺めてみます。

	var timeID = setInterval(function(){
		if(test.length < i) clearInterval(timeID);
		switch(test.charAt(i)){
		case "A":
		case "B":
			if(!cv){
				cv = new Vector(event.pageX,event.pageY,event.pageX -5,event.pageY);
				cv.draw(context);
			}else{
				cv = cv.newFromEndPointRotate(ca);
				cv.draw(context);
			}
			ca=0;
			break;
		case "-":ca =ca -60;break;
		case "+":ca =ca+  60;break;
		}
		i++;
	},1);

サンプル:クリックした場所から図形を描きます(FireFoxのみ確認)
=>http://www28095u.sakura.ne.jp/lsystem/makeSierpinskiGasket/

Fractal plantを描いてみる

 英語版のwikipediaに載っています。特徴的なのは今までと違って[と]の二つの記号が出てきている点です。それぞれその時の値と角度を「保存する」のとそれを「読み出す」のになります。これは丁度スタックの考え方です。arrayに用意されているpushとpopメソッドを利用して簡単に実装できます。また、Fのみが描画命令で、Xは含まないことに注意して下さい。

	var cv = false; //current vector
	var ca =false; //current angle
	var stack =[];//stack

	var i=0;
	var timeID = setInterval(function(){
		if(test.length < i) clearInterval(timeID);
		switch(test.charAt(i)){
		case "F":
			if(!cv){
				cv = new Vector(event.pageX,event.pageY,event.pageX -5,event.pageY);
				cv.draw(context);
			}else{
				cv = cv.newFromEndPointRotate(ca);
				cv.draw(context);
			}
			ca = 0;
			break;
		case "[":
			stack.push([cv.clone(),ca]);
			break;
		case "]":
			var c = stack.pop();
			cv = c[0];
			ca = c[1];
			break;

		case "-":ca -= 25;break;
		case "+":ca +=  25;break;
		}
		i++;
	},1);

サンプル:クリックした場所から図形を描きます(FireFoxのみ確認)
=>http://www28095u.sakura.ne.jp/lsystem/makeFractalPlant/

終わり

      ._
       \ヽ, ,、
        `''|/ノ
         .|
     _   |
     \`ヽ、|
      \, V
         `L,,_
         |ヽ、)  ,、
        /    ヽYノ
       /    r''ヽ、.|
      |     `ー-ヽ|ヮ
      |       `|
      |.        |
      ヽ、      |
        ヽ____ノ


┼ヽ  -|r‐、. レ |
d⌒) ./| _ノ  __ノ 

麻雀待ち判定

makeplex salon:あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ


この問題ができたから優秀な人材とは限らないけれど、できない人は“ほぼ確実に”優秀ではない――プログラマーの皆さまの実力を計るコーディングスキル判定問題を用意しました。あなたはこの問題が解けるでしょうか?

          ____
        /_ノ  ヽ、_\
 ミ ミ ミ  o゚((●)) ((●))゚o      ミ ミ ミ    こんなん余裕だおwwwwwwwwwwww
/⌒)⌒)⌒. ::::::⌒(__人__)⌒:::\   /⌒)⌒)⌒)
| / / /     |r┬-|    | (⌒)/ / / //
| :::::::::::(⌒)    | |  |   /  ゝ  :::::::::::/
|     ノ     | |  |   \  /  )  /
ヽ    /     `ー'´      ヽ /    /
 |    |   l||l 从人 l||l      l||l 从人 l||l
 ヽ    -一''''''"~~``'ー--、   -一'''''''ー-、
  ヽ ____(⌒)(⌒)⌒) )  (⌒_(⌒)⌒)⌒))


            |
           20時間後
            |
            ↓

  ::::::::  ::    ::     :::::  ::  :::
  ::::::  ::   ____   :::::  ::::  :::
  ::::::  :::: /  :::  \ :::   :::   :: 調子こいてごめんなさい
  ::::  ::::/   ::     \::  :::  ::
 ::::  /:::    ─    ─ \ ::  ::  
 :::  |  ::   .(_)  (_)  | :  ::::
  :::   \     (__人__)  ,/ :  :::
  ::  ノ      ` ⌒´   \ :   :::
  /´               ヽ  :::
 |    l              \:::
 ヽ    -一''''''"~~``'ー--、   -一'''''''ー-、.
  ヽ ____(⌒)(⌒)⌒) )  (⌒_(⌒)⌒)⌒))


それでもなんとか形になった。あっているかは不明。そのうち「やる夫と作る麻雀ゲーム」ってのをやりたいなぁ(,,゚Д゚)。

=> 麻雀テスト

////////////////////
//gnagaoka(George.Nagaoka@gmail.com)
//
///////////////////


function string2list(string){
	if(string.match(/[^1-9]/)){
		alert("1-9以外が含まれています。")
		return false;
	}
	if(string.length > 13){
		alert("多牌です。");
		return false;
	}else if(string.length < 13){
		alert("少牌です。");
		return false;
	}

	var list = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,"List"];
	/*
	listの構造は以下の通り
		0-8:+1した牌の個数 ex) 3:2→4が2つ
		9-10:100である必要がある
		11:順子の数
		12:刻子の数
		13:雀頭の数
		14:待ちのリスト
	*/

	for(var i=0;i<13;i++){
		if(list[parseInt(string[i])-1] >=4){
			alert("同一牌が5つになりました。処理を中止します。");
			return false;
		}
		list[parseInt(string[i])-1]++;
	}
	return list;
}

var stack=[];

function copyList(list,list2){
	for(var i=0;i<list.length;i++){
		list2[i] = list[i];
	}
}

function checkShuntu(list,startIndex,list2){//順子
	if(list[startIndex] && list[startIndex+1] && list[startIndex+2]){
		copyList(list,list2);
		list2[startIndex]--;
		list2[startIndex+1]--;
		list2[startIndex+2]--;
		list2[11]++;
		list2[14] += "(" + (startIndex+1) + (startIndex+2) + (startIndex+3) + ")";
		return true;
	}
	return false;
}

function checkKoutu(list,startIndex,list2){//刻子
	if(list[startIndex] >=3){
		copyList(list,list2);
		list2[startIndex] = list2[startIndex] -3;
		list2[12]++;
		list2[14] += "(" + (startIndex+1) + (startIndex+1) + (startIndex+1) + ")";
		return true;
	}
	return false;
}

function checkZyantou(list,tmpstack){ //雀頭は多くても一つ
	var flag=false;
	for(var i=0;i<9;i++){
		if(list[i] >=2){
			var list2 =[];
			copyList(list,list2);
			list2[i] = list2[i] -2;
			if(!checkStack(list2)){
				tmpstack.push(list2);
				flag=true;
			}
			list2[13]++;
			list2[14] += "(" + (i+1) + (i+1) + ")"
		}
	}
	return flag;
}




function main(string){
	stack=[];
	stack.push(string2list(string));
	var count=0;
	while(stack.length !=0 ){
		count++;
		var s = stack.pop();
		var matitext="";
		if(matitext=checkList(s)){
			alert(matitext);
		}
		if(count >100) break;//安全装置
	}
}


function checkList(list){
	var result="";
	if(list[13] == 1 && (list[11]+list[12]) == 3 ){//3面子+雀頭が存在
		if(result=checkMatiMentu(list)){
			return result;
		}else{
			return false;
		}
	}

	if((list[11]+list[12]) ==4){ //4面子が存在
		if(result=checkMatiZyantou(list)){//雀頭のまちはあるか?
			return result;
		}else{
			return false;
		}
	}

	if((list[11]+list[12])  == 3){ //3面子が存在
		var ts=[];
		if(checkMentu(list,ts)){//シュンツorコウツはまだあるか?
			stack = ts.concat(stack);
			return false;
		}else{
			var ts=[];
			if(checkZyantou(list,ts)){//雀頭はあるか?
				stack = ts.concat(stack);
			}else{
				return false;
			}
		}
	}

	var ts=[];
	if(!checkMentu(list,ts) && (list[11]+list[12])  <= 2){ //面子2個以上ないとき、役は完成しない。
		return false;
	}
	stack = ts.concat(stack);
}

function checkMatiZyantou(list){ //単騎待ち
	for(var i=0;i<9;i++){
		if(list[i] ==1){
			return list[14] + "[" + (i+1) + "]";
		}
	}
	return false;

}

function checkMatiMentu(list){
	for(var i=0;i<9;i++){
		if(list[i] && list[i+1]){//両面or辺張待ち
			return list[14]+"[" + (i+1) + (i+2) + "]";
		}
		if(list[i] && list[i+2]){ //嵌張待ち
			return  list[14]+"[" + (i+1) + (i+3) + "]";
		}

		if(list[i] == 2){ //単騎待ち
			return  list[14]+"[" + (i+1) + (i+1) + "]";
		}
	}
	return false;
}

function checkStack(list){
	for(var i=0;i<stack.length;i++){
		for(var j=0;j<14;j++){
			if(stack[i][j] != list[j]) break;
			if(j==13) return true;
		}
	}
	return false;
}

function checkMentu(list,tmpstack){
	var flag=false;

	for(var i=0;i<9;i++){
		var list2=new Array();
		if(checkShuntu(list,i,list2)){
			if(!checkStack(list2)){
				tmpstack.push(list2);
				flag=true;
			}
		}
		var list2=new Array();
		if(checkKoutu(list,i,list2)){
			if(!checkStack(list2)){
				tmpstack.push(list2);
				flag=true;
			}
		}
	}
	return flag;
}

function printList(list,option){
	var listString =option +"\n";
	for(var i=0;i<15;i++){
		listString += i+1 + ":" +  list[i] + "\n";
	}
	alert(listString);
}