領域表示

簡単な領域表示 正負で色分け

f(x,y)=x^3+y^3-xyが正の部分と負の部分を色分けして図示したい。
描画領域の全てのピクセルで値を計算すれば出来るけども、それじゃ芸が無いから別の方法を試す。


演算子の再定義

実数の四則演算(実数×実数→実数)を、範囲の演算(範囲×範囲→範囲)に変更する。
ある範囲でのf(x,y)値の正負を一度に評価して計算量削減できるはず。

例
[3〜4]＋[10〜20]=[13〜24]
[5〜8]×[-1〜2]=[-8〜16]


コードにするとこんな感じ

function add(x,y){return [x[0]+y[0],x[1]+y[1]];}
function sub(x,y){return [x[0]-y[1],x[1]-y[0]];}
function mult(x,y){
	var e,a=x[0]*y[0],b=x[0]*y[1],c=x[1]*y[0],d=x[1]*y[1];
	if(a>b){e=a;a=b;b=e;}if(c>d){e=c;c=d;d=e;}
	return [a<c?a:c,b<d?d:b];
}

これを使って、f(x,y)を書き換える。
演算子オーバーロードが使えたら楽なんだけど・・・

//function f(x,y){return x*x*x+y*y*y-xy}
function func(x,y){
	var xxx=mult(x,mult(x,x));
	var yyy=mult(y,mult(y,y));
	var xy=mult(x,y);
	return sub(add(xxx,yyy),xy);
}

このfuncはf(x,y)の範囲(値域)をゆるーく評価する関数になってる。

描画手順

1. ある広い領域x,yでfunc(x,y)を実行
2. 必ず正もしくは必ず負になるのなら色を塗って終わり
3. 正負判別できない時は、4分割した小さい領域で同じ操作をする

コード全体

<script>
function add(x,y){return [x[0]+y[0],x[1]+y[1]];}
function sub(x,y){return [x[0]-y[1],x[1]-y[0]];}
function mult(x,y){
	var e,a=x[0]*y[0],b=x[0]*y[1],c=x[1]*y[0],d=x[1]*y[1];
	if(a>b){e=a;a=b;b=e;}if(c>d){e=c;c=d;d=e;}
	return [a<c?a:c,b<d?d:b];
}
function func(x,y){
	var xxx=mult(x,mult(x,x));
	var yyy=mult(y,mult(y,y));
	var xy=mult(x,y);
	return sub(add(xxx,yyy),xy);
}

function start(){
	var canvas=document.getElementById("canvas");
	var context=canvas.getContext("2d");
	
	var queue=[[0,0,512]],index=0;
	function recursive(x,y,s){
		var xx=2*x/512-1,yy=1-2*y/512,d=2*s/512;
		var z=func([xx,xx+d],[yy-d,yy]);
		if(z[1]<0)context.fillStyle="red";
		else if(z[0]>0)context.fillStyle="blue";
		else{
			if(s!=1){
				queue.push([x,y,s/2]);
				queue.push([x+s/2,y,s/2]);
				queue.push([x,y+s/2,s/2]);
				queue.push([x+s/2,y+s/2,s/2]);
			}
			var c="0123456789abcdef",zm=-z[0]+1e-16,zp=z[1]+1e-16,zz=zm+zp;
			context.fillStyle="#"+c.charAt(parseInt(16*zm/zz))+"0"+c.charAt(parseInt(16*zp/zz));
		}
		context.fillRect(x,y,s,s);
	}
	
	function loop(){
		for(var i=0;i<256;i++){
			var p=queue[index++];
			if(!p)return;
			recursive(p[0],p[1],p[2]);
		}
		setTimeout(loop,0);
	}
	loop();
}

</script>
<body onload="start()">
<canvas width=512 height=512 id="canvas">


簡単な構文解析っぽいのを付けたサンプル
http://www.geocities.jp/flyinpng/calc20110528/


特徴
・計算完了する前に概形が見える
・計算オーダーはだいたいピクセル数の平方根に比例
・けどそこまで速くなくてしらみつぶしのほうがましな場合も

いつかどこかで何かに使えるかも。