/*
	ドロネー分割
	
	requires : 2d.js
	author:nakagawa[]ville.jp
	license:NYSL
*/
function MathDelaunay(width, height, points){
	this.rect = [
		{x : 0,     y: 0     },
		{x : width, y: 0     },
		{x : 0,     y: height},
		{x : width, y: height}
	];
	this.points = points;
	this.triangles = [ // 一番最初の三角形2個
		[this.rect[0], this.rect[1], this.rect[2]],
		[this.rect[1], this.rect[2], this.rect[3]]
	];
}
MathDelaunay.prototype = {
	split : function(){
		var triangles = this.triangles;
		for(var i=0, n=this.points.length; i<n; i++){
			var p = this.points[i];
			// 点pが外接円に含まれるような三角形を選ぶ
			var t = this._chooseTriangles(triangles, p);
	
			// 三角形をマージして多角形にする
			var poly = this._mergeTriangles(t.ok);

			// 多角形の各頂点と点pを結んで三角形に分割する
			// chooseTriangles()で選ばれなかった三角形は全部残す
			triangles = t.ng.concat(this._splitPolygon(poly, p));
		}
		return triangles;
	},
	// 点pが三角形tの外接円に含まれるか
	_test : function(t, p){
		// 円の中心からpまでの距離と円の半径を比較
		var circle = Math2D.getCircumscribedCircle(t);
		return circle.r2 >= Math2D.d2(p, circle.o);
	},
	// 点pが外接円に含まれるような三角形を選ぶ
	_chooseTriangles : function(triangles, p){
		var ok = [];
		var ng = [];
		for(var i=0, n=triangles.length; i<n; i++){
			if(this._test(triangles[i], p)){
				ok.push(triangles[i]);
			}else{
				ng.push(triangles[i]);
			}
		}
		return {ok:ok, ng:ng};
	},
	// 三角形の集合から辺の集合へ
	_triangles2edges : function(triangles){
		var edges = [];
		for(var i=0,n=triangles.length; i<n; i++){
			var t = triangles[i];
			edges.push(
				[t[0], t[1]],
				[t[1], t[2]],
				[t[2], t[0]]
			);
		}
		return edges;
	},
	// 複数の三角形をマージしてひとつの多角形にする
	_mergeTriangles : function(triangles){
		var polygon = [];
		// 各三角形を辺に分割して、重なる辺を取り除く
		var edges = this._triangles2edges(triangles);
		var n = edges.length;
		for(var i=0; i<n-1; i++){
			var e1 = edges[i];
			if(e1.skip) continue;
			var found = false;
			for(var j=i+1; j<n; j++){
				var e2 = edges[j];
				if(
					(e1[0].x == e2[0].x && e1[0].y == e2[0].y && e1[1].x == e2[1].x && e1[1].y == e2[1].y) ||
					(e1[0].x == e2[1].x && e1[0].y == e2[1].y && e1[1].x == e2[0].x && e1[1].y == e2[0].y) 
				){
					edges[j].skip = true;// 次以降のループでスキップする
					found = true;
					break;
				}
			}
			found || polygon.push([e1[0], e1[1]]);
		}
		// n-1ループでn番目が評価されていないので
		if(!edges[n-1].skip) polygon.push([edges[n-1][0], edges[n-1][1]]);
		return polygon;
	},
	// 多角形の各頂点と点pを結んで三角形に分割する
	_splitPolygon : function(polygon, p){
		var triangles = [];
		for(var i=0,n=polygon.length; i<n; i++){
			var edge = polygon[i];
			triangles.push([edge[0], edge[1], p]);
		}
		return triangles;
	}
};