//Generowanie obrazów - algorytm genetyczny
//(c) 2011 by Tomasz Lubinski
//www.algorytm.org

/* canvas data */
var bestCanvas;             //canvas with best image
var currentCanvas;          //canvas with current image
var width;                  //width of the image
var height;                 //height of the image
var pointsNum;              //number of point in the image (width*height)
var maxDifference;          //maximum difference between images (width*height*sqrt(255*255*3))
var originalImageData;      //data that describes source image
var bestSimilarityInHtml;   //html element where information about results will be placed
var threadId = -1;

/* genetic algorithm parameters */
var elementsNum = 50;          //number of elements
var elementType = 0;           //element type (0 - triangle, 1 - circle)
var population = 50;           //number of images in population
var elite = 10;                //number of images in elite
var mutationProbability = 0.3; //probability of mutation of the element during reproduction
var mutationSize = 10.0;       //size of the mutation (0-100)
var geneticImages;             //array with images in current generation
var bestSimilarity = 0;        //similarity of the best image
var generation = 0;            //number of generation

/* class that represents image generated by genetic algorithm */
function geneticImage(elementsNum)
{
	this.smilarity = 0;                    // how this image is similar to original image
	this.elements = new Array(elementsNum);// elements that build an image
	
	//initialize with random values
	this.init = function()
	{
		for (var i=0; i<this.elements.length; i++)
		{
			if (elementType == 0)
			{
				this.elements[i] = new geneticImageElementTriangle();
			}
			else
			{
				this.elements[i] = new geneticImageElementCircle();				
			}
			this.elements[i].init()
		}
	}
		
	//calculate similarity
	this.calculateSimilarity = function(originalImageData, canvas)
	{
		this.draw(canvas);
		var imageData = canvas.getContext("2d").getImageData(0, 0, width, height);
		var distance = 0.0;
		for (var i=0; i<pointsNum; i++)
		{
			index = i*4;
			distance += Math.sqrt(
				(originalImageData.data[index+0]-imageData.data[index+0])*(originalImageData.data[index+0]-imageData.data[index+0])+
				(originalImageData.data[index+1]-imageData.data[index+1])*(originalImageData.data[index+1]-imageData.data[index+1])+
				(originalImageData.data[index+2]-imageData.data[index+2])*(originalImageData.data[index+2]-imageData.data[index+2]));
		}
		this.similarity = ((maxDifference - distance) * 100.0) / maxDifference;
	}
	
	//draw an image from elements
	this.draw = function(canvas)
	{
		//clear
		canvas.width = canvas.width
		var ctx = canvas.getContext("2d");
		//put white background
		ctx.fillStyle = "rgba(255, 255, 255, 1)";
		ctx.fillRect(0, 0, width, height);
		//draw all elements
		for (var i=0; i<this.elements.length; i++)
		{
			this.elements[i].draw(ctx)
		}
	}
}

/* class that represents one element of the image generated by genetic algorithm (triangle) */
function geneticImageElementTriangle()
{
	//cooridnates
	this.x1 = 0;
	this.y1 = 0;
	this.x2 = 0;
	this.y2 = 0;
	this.x3 = 0;
	this.y3 = 0;
	//color
	this.r = 0;
	this.g = 0;
	this.b = 0;
	this.a = 0;
	
	//initialize with random values
	this.init = function()
	{
		this.x1 = Math.random()*width;
		this.y1 = Math.random()*height;
		this.x2 = this.x1 + Math.random()*4.0 - 2.0;
		this.y2 = this.y1 + Math.random()*4.0 - 2.0;
		this.x3 = this.x1 + Math.random()*4.0 - 2.0;
		this.y3 = this.y1 + Math.random()*4.0 - 2.0;
		this.r = Math.random()*256.0;
		this.g = Math.random()*256.0;
		this.b = Math.random()*256.0;
		this.a = Math.random();
	}
	
	//draw an element on the canvas
	this.draw = function(ctx)
	{
		ctx.beginPath();
		ctx.fillStyle = "rgba(" + Math.floor(this.r) + "," + Math.floor(this.g) + "," + Math.floor(this.b) + "," + this.a + ")";
		ctx.moveTo(this.x1, this.y1);
		ctx.lineTo(this.x2, this.y2);
		ctx.lineTo(this.x3, this.y3);
		ctx.fill();
		ctx.closePath();
	}
	
	this.clone = function()
	{
		var r = new geneticImageElementTriangle();
		r.x1 = this.x1;
		r.y1 = this.y1;
		r.x2 = this.x2;
		r.y2 = this.y2;
		r.x3 = this.x3;
		r.y3 = this.y3;
		r.r  = this.r;
		r.g  = this.g;
		r.b  = this.b;
		r.a  = this.a;
		
		var mutation = Math.random();
		var noChangesProbability = 1.0 - mutationProbability;
		var parameterMutationProbability = mutationProbability / 4.0;
		
		if (mutation < noChangesProbability)
		{
		}
		else if (mutation < noChangesProbability + parameterMutationProbability)
		{
			r.x1 += gaussRandom()*width;
			if (r.x1 > width) r.x1 = width;
			else if (r.x1 < 0) r.x1 = 0;
			
			r.y1 += gaussRandom()*height;
			if (r.y1 > height) r.y1 = height;
			else if (r.y1 < 0) r.y1 = 0;
		}
		else if (mutation < noChangesProbability + 2.0 * parameterMutationProbability)
		{
			r.x2 += gaussRandom()*width;
			if (r.x2 > width) r.x2 = width;
			else if (r.x2 < 0) r.x2 = 0;
			
			r.y2 += gaussRandom()*height;
			if (r.y2 > height) r.y2 = height;
			else if (r.y2 < 0) r.y2 = 0;
		}
		else if (mutation < noChangesProbability + 3.0 * parameterMutationProbability)
		{
			r.x3 += gaussRandom()*width;
			if (r.x3 > width) r.x3 = width;
			else if (r.x3 < 0) r.x3 = 0;
			
			r.y3 += gaussRandom()*height;
			if (r.y3 > height) r.y3 = height;
			else if (r.y3 < 0) r.y3 = 0;
		}
		else
		{	
			r.r += gaussRandom()*255;
			if (r.r > 255) r.r = 255;
			else if (r.r < 0) r.r = 0;
		
			r.g += gaussRandom()*255;
			if (r.g > 255) r.g = 255;
			else if (r.g < 0) r.g = 0;
			
			r.b += gaussRandom()*255;
			if (r.b > 255) r.b = 255;
			else if (r.b < 0) r.b = 0;
			
			r.a += gaussRandom();
			if (r.a > 1) r.a = 1;
			else if (r.a < 0) r.a = 0;
		}
			
		return r;
	}
}

/* class that represents one element of the image generated by genetic algorithm (circle) */
function geneticImageElementCircle()
{
	//cooridnates
	this.x1 = 0;
	this.y1 = 0;
	this.rad = 0;
	//color
	this.r = 0;
	this.g = 0;
	this.b = 0;
	this.a = 0;
	
	//initialize with random values
	this.init = function()
	{
		this.x1 = Math.random()*width;
		this.y1 = Math.random()*height;
		this.rad = Math.random()*3.0;
		this.r = Math.random()*256.0;
		this.g = Math.random()*256.0;
		this.b = Math.random()*256.0;
		this.a = Math.random();
	}
	
	//draw an element on the canvas
	this.draw = function(ctx)
	{
		ctx.fillStyle = "rgba(" + Math.floor(this.r) + "," + Math.floor(this.g) + "," + Math.floor(this.b) + "," + this.a + ")";
		ctx.beginPath();
		ctx.arc(this.x1, this.y1, this.rad, 0, Math.PI*2, false);
		ctx.closePath();
		ctx.fill();
	}
	
	this.clone = function()
	{
		var r = new geneticImageElementCircle();
		r.x1 = this.x1;
		r.y1 = this.y1;
		r.rad = this.rad;
		r.r  = this.r;
		r.g  = this.g;
		r.b  = this.b;
		r.a  = this.a;
		
		var mutation = Math.random();
		var noChangesProbability = 1.0 - mutationProbability;
		var parameterMutationProbability = mutationProbability / 3.0;
		
		if (mutation < noChangesProbability)
		{
		}
		else if (mutation < noChangesProbability + parameterMutationProbability)
		{
			r.x1 += gaussRandom()*width;
			if (r.x1 > width) r.x1 = width;
			else if (r.x1 < 0) r.x1 = 0;
			
			r.y1 += gaussRandom()*height;
			if (r.y1 > height) r.y1 = height;
			else if (r.y1 < 0) r.y1 = 0;
		}
		else if (mutation < noChangesProbability + 2.0 * parameterMutationProbability)
		{
			r.rad += gaussRandom()*((width+height)/4.0);
			if (r.rad > ((width+height)/2.0)) r.rad = ((width+height)/2.0);
			else if (r.rad < 0) r.rad = 0;
		}
		else
		{	
			r.r += gaussRandom()*255;
			if (r.r > 255) r.r = 255;
			else if (r.r < 0) r.r = 0;
		
			r.g += gaussRandom()*255;
			if (r.g > 255) r.g = 255;
			else if (r.g < 0) r.g = 0;
			
			r.b += gaussRandom()*255;
			if (r.b > 255) r.b = 255;
			else if (r.b < 0) r.b = 0;
			
			r.a += gaussRandom();
			if (r.a > 1) r.a = 1;
			else if (r.a < 0) r.a = 0;
		}
			
		return r;
	}
}

/* random with normal distribution */
function gaussRandom()
{
		var x = Math.random();
		var y = Math.random();
		
		var r = 0.003 * mutationSize * Math.sqrt(-2.0 * Math.log(x)) * Math.cos(2.0 * Math.PI * y);
		if (r<-1.0) r=0;
		if (r>1.0) r=0;
		return r;		
}

/* reproduct new image from "mother" and "father" */
function reproduct(mother, father)
{
	r = new geneticImage(elementsNum);
	
	for (var i=0; i<mother.elements.length; i++)
	{
		if (Math.random() < 0.5)
		{
			r.elements[i] = mother.elements[i].clone();
		}
		else
		{
			r.elements[i] = father.elements[i].clone();
		}					
	}
	return r;
}

/* perform one step of genetic algorithm */
function generate()
{
	//increment generation counter
	generation++;
	
	//calculate similarity
	for (var i=0; i<population; i++)
	{
		geneticImages[i].calculateSimilarity(originalImageData, currentCanvas);
	}
	
	//find elite
	for (var i=0; i<elite; i++)
	{
		var currentBest = geneticImages[0].similarity;
		var currentBestIndex = 0;
		for (var j=1; j<population-i; j++)
		{
			if (currentBest < geneticImages[j].similarity)
			{
				currentBest = geneticImages[j].similarity;
				currentBestIndex = j;
				
			}
		}	
		//add to elite
		eliteImages[i] = geneticImages[currentBestIndex];
		geneticImages[currentBestIndex] = geneticImages[population-i-1];
	}
	
	//show if new best is found
	if (bestSimilarity < eliteImages[0].similarity)
	{
		bestSimilarity = eliteImages[0].similarity;
		eliteImages[0].draw(bestCanvas);
	}
	bestSimilarityInHtml.innerHTML = "Pokolenie: " + generation + "<br/>Najlepsze dopasowanie: "+bestSimilarity + "%<br/>Aktualne dopasowanie: " + eliteImages[0].similarity + "%";
	
	//create next generation
	var i = 0;
	var mother = 0;
	var father = 0;
	while (i<population)
	{
		if (mother != father)
		{
			geneticImages[i] = reproduct(eliteImages[mother], eliteImages[father]);
			i++;
			if (i >= population) break;
		}
		
		father++;
		if (father >= elite)
		{
			mother++;
			father = 0
		}
		if (mother >= elite)
		{
			mother = 0;
			father = 1;
		}
	}
}

/* start generating images */
function stop()
{
	clearInterval(threadId);
}

/* start generating images */
function start()
{
	//stop, if thread is running
	if (threadId != -1)
	{
		stop();
	}
	
	//initialize data
	pointsNum = width*height;                          // number of points in the image
	maxDifference = width*height*Math.sqrt(255*255*3); // maximum distance between two images
	bestSimilarityInHtml = document.getElementById("bestSimilarity");
	bestSimilarity = 0;
	generation = 0;
	isRunning = true;

	//create initial population
	geneticImages = new Array(population);
	eliteImages = new Array(elite);
	for (var i=0; i<population; i++)
	{
		geneticImages[i] = new geneticImage(elementsNum, width, height);
		geneticImages[i].init();
	}

	//start generation	
	threadId = setInterval("generate()", 0);
}

/* load image pointed by param_file to canvas */
function loadImage(imgSrc) 
{
	var canvas = document.getElementById("original");
	var ctx = canvas.getContext("2d");
	
	//add file:// if user specified local path
	if (imgSrc.indexOf("//") == -1 && imgSrc.indexOf(".") != 0) 
	{
		imgSrc = "file:///" + imgSrc;
	}
	
	//load file into canvas
	var img = new Image();
  	img.onload = function(){
		bestCanvas = document.getElementById("best");
		currentCanvas = document.getElementById("current");
		width = img.width;
		height = img.height;
 		canvas.width = width;
  		canvas.height = height;
 		bestCanvas.width = width;
  		bestCanvas.height = height;  
  		currentCanvas.width = width;
  		currentCanvas.height = height;		
    		ctx.drawImage(img,0,0);
		// replace transparent with white
		try 
		{
    			originalImageData = ctx.getImageData(0, 0, width, height);
  		} catch(e) 
  		{
  			netscape.security.PrivilegeManager.enablePrivilege("UniversalBrowserRead");
  			originalImageData = ctx.getImageData(0, 0, width, height);
  		}
		for (var i=0; i<height; i++)
		{
			for (var j=0; j<width; j++)
			{
				index = (i*width+j)*4;
				if (originalImageData.data[index+3] == 0)
				{
					originalImageData.data[index+3] = 255;
					originalImageData.data[index+0] = 255;
					originalImageData.data[index+1] = 255;
					originalImageData.data[index+2] = 255;
				}
			}
		}
  	}
  	img.src = imgSrc;
}