rloc.cpp

LinPacker是一个优化矩形布局的工具

/***************************************************************************
 *   Copyright (C) 2003 by ita                                             *
 *   [e-mail]                                                    *
 *                                                                         *
 *   This program is free software{}; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation{}; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 ***************************************************************************/

#include "rloc.h"
#include "algorithm"

using namespace  std;


	bool
Rloc::superposition(int t1, int t2)
{
	float x1,x2,y1,y2;
	float l1,l2,L1,L2;
	float valx,valy;

	l1 = vecteur[curseurE][t1].getLargeur()/2.0;
	l2 = vecteur[curseurE][t2].getLargeur()/2.0;
	L1 = vecteur[curseurE][t1].getLongueur()/2.0;
	L2 = vecteur[curseurE][t2].getLongueur()/2.0;

	x1 = vecteur[curseurE][t1].posx + l1;
	x2 = vecteur[curseurE][t2].posx + l2;
	y1 = vecteur[curseurE][t1].posy + L1;
	y2 = vecteur[curseurE][t2].posy + L2;

	valx = x2 - x1;
	valy = y2 - y1;

	if (valx < 0)
	{
		valx *= -1;
	}

	if (valy < 0)
	{
		valy *= -1;
	}

	if ( (valx < (l1 + l2) ) and (valy < (L1 + L2) ) )
	{
		return 1;
	}
	return 0;
};

	void	
Rloc::ajouterRect(int lo,int la,int xpos,int ypos,bool orient,int num)
{
	temp.push_back( rectangle(lo,la,xpos,ypos,orient,num) );
};

Rloc::Rloc()
{
	limite= 10;
	nbRect = 10;
	population = 1000;
	KeepR = 2;
	MutaR = 10;

	points.resize(2000,lieu(0,0));

};

Rloc::~Rloc()
{
};

	void
Rloc::Fitness(int k)
{
	curseurE = k; 

	int maxTaille = 0;

	for ( int i = 0 ; i < nbRect ; i++)
	{

		actualiserPoints(i);

		int idx = -1;
		int j = 0;

		while (j < nombreLieux)
		{

			vecteur[k][i].posx = points[j].posx;
			vecteur[k][i].posy = points[j].posy;


			if (positionPossible(i))
			{
				if (idx >= 0)
					cout <<"ceci ne devrait pas s'afficher"<<endl;

				idx = j;
				break;
			}
			j++;
		}

		if (idx < 0)
		{
			maxTaille = 1000000;
			goto end;
		}

		if (maxTaille < vecteur[k][i].getYHaut())
			maxTaille = vecteur[k][i].getYHaut();
	}

end :
	catalogue[k].val = maxTaille;

};



	void
Rloc::actualiserPoints( int index)
{
	int k = curseurE;
	nombreLieux = 0;
	if ( index )
	{
		for ( int i = 0; i <index;i++)
		{
			points[nombreLieux] = lieu(vecteur[k][i].posx,
					vecteur[k][i].getYHaut());
			nombreLieux++;
			points[nombreLieux] = lieu(vecteur[k][i].getXMax(),
					vecteur[k][i].posy );
			nombreLieux++;
		}

		std::sort(points.begin(),points.begin()+nombreLieux);
	}
	else
	{
		points[0] = lieu(0,0);
		nombreLieux = 1;
	}
}

	void
Rloc::Iterer()
{
	int k;
	int seuil = ((MutaR+KeepR)*population)/100;

	for ( k=(KeepR*population)/100; k<seuil ; k++)
	{
		Mutation(catalogue[k].idx);
	}

	for ( k=seuil ;k<population;k++)
	{
		Crossover(catalogue[k].idx);
	}

	for ( k=0;k<population;k++)
	{
		Fitness(catalogue[k].idx);
	}

	for (int j=0;j<population;j++)
	{
		catalogue[j].idx = j;
	}
	
	std::sort(catalogue.begin(),catalogue.end());
}


	bool
Rloc::positionPossible(int idx)
{
	if (vecteur[curseurE][idx].getXMax() > limite )
	{
		return 0;
	}

	for ( int i = 0 ; i < idx ; i++)
	{
		if ( vecteur[curseurE][idx].posy < vecteur[curseurE][i].getYHaut())
			if ( superposition (idx, i) )
				return 0;
	}
	return 1;
};


	void
Rloc::initialiser( int lim, int pop, int taille)
{
	int i,j;

	randomize();

	curseurE = 0;
	limite = lim;
	nbRect = taille;
	population = pop;

	empilement nono;
	nono.resize(nbRect);
	vecteur.clear();
	vecteur.resize(population,nono);
	
	catalogue.resize(population,pv(0,0));

	for (i=0;i< taille;i++)
	{
		temp[i].numero = i;
	}
	std::sort(temp.begin(),temp.end());

	for (i=0;i<population;i++)
	{
		catalogue[i].idx=i;
	}

	for (j=0;j<taille;j++)
	{
		for (i=0;i<population;i++)
		{
			vecteur[i][j] = temp[j];
		}
	}

};

	int
Rloc::randomize()
{
	int seed;

	ifstream infile ("/dev/urandom");
	infile>>seed;
	infile.close();

	srandom(seed*time(0));
	return 0;
};

	void	
Rloc::insereRect(int lo,int la)
{
	ajouterRect(lo,la,-1,-1,0,0);
};

	int
Rloc::getLimite()
{
	return limite;
};

	int	
Rloc::getTaille()
{
	return nbRect;
};	

	int
Rloc::getPopulation()
{
	return population;
}


	void
Rloc::toStringPoints()
{
	for ( unsigned int i = 0;i < points.size();i++)
	{
		cout <<points[i].posx<<" "<<points[i].posy<<endl;
	}
};

	void
Rloc::toStringRloc(int i)
{
	for ( int j = 0; j < nbRect; j++)
	{
		rectangle var = vecteur[i][j];
		cout    << var.getLargeur()/1000.  << " "  \
			<< var.getLongueur()/1000. << " "  \
			<< var.posx/1000.        << " "  \
			<< var.posy/1000.        << "\t\t |" \
			<< var.orientation << "\t " \
			<< var.numero <<endl; 
	}
	cout <<endl;
};

	int
Rloc::getHauteur()
{
	//cout<<"la valeur associ閑 au meilleur empilement est :"<< catalogue[0].val <<endl; 
	return catalogue[0].val;
}



	int *
Rloc::getTabRectangle( int i)
{
	int j = catalogue[0].idx;
	tab[0] = vecteur[j][i].posx;
	tab[1] = vecteur[j][i].posy;
	tab[2] = vecteur[j][i].getLargeur( );
	tab[3] = vecteur[j][i].getLongueur();
	tab[4] = vecteur[j][i].numero;
	tab[5] = (int) vecteur[j][i].orientation;

	return tab;
};

void
Rloc::SetRates(int keep,int muta)
{
	if (keep + muta > 95)
	{
		MutaR = 10;
		KeepR = 5;
	}
	else
	{
		MutaR = muta;
		KeepR = keep;
	}
}

int
Rloc::getMutaR()
{
	return MutaR;
};

int
Rloc::getKeepR()
{
	return KeepR;
}

int
Rloc::getCrossR()
{
	return (100 - MutaR - KeepR);
}

	void    
Rloc::Mutation(int i)
{

	int j,k,u;

	for (u = 0; u < (random()%nbRect); u++)
	{
		if (vecteur[i][u].orientation)
			vecteur[i][u].orientation = 0;
		else
			vecteur[i][u].orientation = 1;

	}
	for (u = 0; u < (random()%nbRect)*3; u++)
	{
		j = random()%nbRect;
		k = random()%nbRect;

		rectangle tempR = vecteur[i][j];
		vecteur[i][j] = vecteur[i][k];
		vecteur[i][k] = tempR;

	}
};


	void
Rloc::Crossover(int k)
{
	int seuil = (KeepR + MutaR) * population/100;

	int vec1 = catalogue[random()%seuil].idx;
	int vec2 = catalogue[random()%seuil].idx;

	for (int u=0;u<nbRect;u++)
	{
		if (rand()%2)
			vecteur[k][u] = vecteur[vec1][u];
		else
			vecteur[k][u].numero=1024;
	}

	int cV = 0;

	for (int u=0;u<nbRect;u++)
	{
		if (vecteur[k][u].numero == 1024)
		{
nextT:
			for (int v=0;v<nbRect;v++)
			{
				if (vecteur[k][v].numero == vecteur[vec2][cV].numero)
				{
					cV++;
					goto nextT; // i don't like goto but i don't have TIME
				} 
			}
			vecteur[k][u] = vecteur[vec2][cV];
		}
	}
};

void
Rloc::Reset()
{
	//temp.resize(0,rectangle(0,0,0,0,0,0));
	temp.clear();
	catalogue.clear();
}