/*************************************************************************************************************************************/
/* */
/* M A X I M I S A T I O N D E L A P L U S P E T I T E D I S T A N C E */
/* A L ' I N T E R I E U R D ' U N N U A G E D E P O I N T S */
/* P A R U N E M E T H O D E D U T Y P E " R E C U I T S I M U L E " : */
/* */
/* */
/* Author of '$xtc/recuit_si.32$c' : */
/* */
/* Jean-Francois COLONNA (LACTAMME, AAAAMMJJhhmmss). */
/* */
/*************************************************************************************************************************************/
#include "INCLUDES.01.I"
/* Introduit le 20051116102150... */
extern void *malloc();
static int dimX=0;
#define Xmin 0
#define Xmax (Xmin + (dimX-1))
/* Definition des abscisses. */
static int dimY=0;
#define Ymin 0
#define Ymax (Ymin + (dimY-1))
/* Definition des ordonnees. */
#define IMAGE(x,y) \
(*(image + (((((int)y)-Ymin)*dimX) + (((int)x)-Xmin)))) \
/* Acces a un point de l'image. */
#define store(n,x,y) \
{ \
IMAGE(x,y) = n; \
} \
/* Rangement d'un point valide d'une image. */
#define nPOINTS \
20 \
/* Nombre de points du nuage... */
#define nITERATIONS \
100000 \
/* Nombre d'iterations maximum... */
#define DELTA \
5.0 \
/* Plus grande variation possible des coordonnees {x,y}. */
#define PROBABILITE_D_ACCEPTATION_D_UNE_MAUVAISE_SOLUTION \
0.0 \
/* Probabilite d'accepter une mauvaise solution... */
extern double drand48();
#define ALEA \
((drand48() - 0.5)*DELTA) \
/* Plus grande variation possible des coordonnees {x,y}, en rappelant que : */ \
/* */ \
/* drand48() E [0,1] */ \
/* */ \
/* d'ou la translation de 0.5 qui permet d'avoir un deplacement algebrique : */ \
/* */ \
/* ALEA E [-0.5,+0.5] */ \
/* */ \
/* ce qui permet de se mouvoir dans n'importe quelle direction... */
extern double sqrt();
typedef struct point {
double x;
double y;
} point;
/* 'struct' de definition d'un point... */
#define X(P) \
(P.x)
#define Y(P) \
(P.y)
/* Definition de l'acces aux coordonnees d'un point. */
#define MINI(a,b) \
(((a) < (b)) ? (a) : (b)) \
/* Definition de la recherche du minimum. */
#define MAXI(a,b) \
(((a) > (b)) ? (a) : (b)) \
/* Definition de la recherche du maximum. */
#define Carre(x) \
((x)*(x)) \
/* Definition du carre de 'x'. */
#define d(A,B) \
sqrt(Carre(X(B)-X(A)) + Carre(Y(B)-Y(A))) \
/* Definition de la distance entre deux points 'A' et 'B'. */
#define PROBABILITE_DE_PERTURBER_UN_POINT \
0.1 \
/* Probabilite de perturber le point courant... */
#define PERTURBATION(coordonnee,minimum,maximum) \
{ \
int perturber=1; \
double coordonnee_perturbee; \
\
if (drand48() < PROBABILITE_DE_PERTURBER_UN_POINT) \
{ \
while (perturber == 1) \
{ \
coordonnee_perturbee = coordonnee + ALEA; \
/* Perturbation de la coordonnee courante... */ \
\
if ((coordonnee_perturbee < minimum) || (coordonnee_perturbee > maximum)) \
{ \
/* Les coordonnees hors-ecran sont rejetees... */ \
} \
else \
{ \
coordonnee = coordonnee_perturbee; \
perturber=0; \
/* On s'arrete sur la premiere coordonnee perturbee situee dans l'ecran... */ \
} \
} \
} \
else \
{ \
} \
}
#define DISTANCE_MINIMALE(distance_minimale) \
{ \
distance_minimale=+1e+300; \
\
for (i=0 ; i<nPOINTS ; i++) \
{ \
for (j=0 ; j<nPOINTS ; j++) \
{ \
if (i > j) \
{ \
double distance_courante=d(Lpoints[i],Lpoints[j]); \
distance_minimale=MINI(distance_minimale,distance_courante); \
/* Recherche de la distance minimale courante du nuage de points... */ \
} \
else \
{ \
} \
} \
} \
}
main()
{
int generer_les_positions_finales=0;
/* Pour controler la generation des positions finales uniquement (=1) ou des positions */
/* finales et intermediaires (=0). */
int sortir_l_image=1;
/* Pour controler la sortie (=1) ou pas (=0) de l'image... */
int x,y;
/* Definition des coordonnees. */
unsigned char *image;
/* Definition de l'image a generer... */
int i,j,n;
int iterations;
/* Index divers... */
point Lpoints[nPOINTS];
point SLpoints[nPOINTS];
/* Liste des points et sa Sauvegarde. */
double distances[nPOINTS][nPOINTS];
/* Matrice des distances. */
Get(dimX,"dimX");
Get(dimY,"dimY");
/* Recuperation des dimensions en 'X' et en 'Y' de l'image a generer. */
image=malloc(dimY*dimX);
/* Definition de l'image a generer... */
for (y=Ymin ; y<=Ymax ; y++)
{
for (x=Xmin ; x<=Xmax ; x++)
{
store(NOIR,x,y);
/* Initialisation de l'image a generer... */
}
}
for (n=0 ; n<nPOINTS ; n++)
{
X(Lpoints[n]) = drand48()*dimX;
Y(Lpoints[n]) = drand48()*dimY;
/* Initialisation arbitraire des points... */
}
for (iterations=1 ; iterations<=nITERATIONS ; iterations++)
{
double distance_minimale_avant;
double distance_minimale_apres;
for (n=0 ; n<nPOINTS ; n++)
{
X(SLpoints[n]) = X(Lpoints[n]);
Y(SLpoints[n]) = Y(Lpoints[n]);
/* Sauvegarde de l'etat courant des points... */
}
DISTANCE_MINIMALE(distance_minimale_avant);
/* Recherche de la distance minimale avant la perturbation. */
if (iterations == 1)
{
fprintf(stderr,"distance minimale initiale=%f\n",distance_minimale_avant);
}
else
{
}
for (n=0 ; n<nPOINTS ; n++)
{
double X_perturbe=X(Lpoints[n]);
double Y_perturbe=Y(Lpoints[n]);
PERTURBATION(X_perturbe,Xmin,Xmax);
PERTURBATION(Y_perturbe,Ymin,Ymax);
X(Lpoints[n]) = X_perturbe;
Y(Lpoints[n]) = Y_perturbe;
/* Perturbation aleatoire des points (sauf les deux premiers P0 et P1). */
}
DISTANCE_MINIMALE(distance_minimale_apres);
/* Recherche de la distance minimale apres la perturbation. */
if ( (distance_minimale_apres <= distance_minimale_avant)
|| (drand48() < PROBABILITE_D_ACCEPTATION_D_UNE_MAUVAISE_SOLUTION)
)
/* On cherche a maximiser la distance minimale... */
{
for (n=0 ; n<nPOINTS ; n++)
{
X(Lpoints[n]) = X(SLpoints[n]);
Y(Lpoints[n]) = Y(SLpoints[n]);
/* Restauration de l'etat anterieur lorsqu'il y a degradation des performances... */
}
}
else
{
/* On conserve un etat perturbe qui maximise la distance minimale... */
}
if (generer_les_positions_finales == 1)
{
}
else
{
for (n=0 ; n<nPOINTS ; n++)
{
store(MAXI(NOIR+1,(BLANC*iterations)/nITERATIONS),X(Lpoints[n]),Y(Lpoints[n]));
/* Marquage des points... */
}
}
if (iterations == nITERATIONS)
{
fprintf(stderr,"distance minimale finale..=%f\n",distance_minimale_avant);
/* ATTENTION : c'est la distance minimale a l'avant-derniere iteration qui est editee car, */
/* en effet, il n'est pas sur que 'distance_minimale_apres' etait maximale... */
}
else
{
}
}
if (generer_les_positions_finales == 1)
{
for (n=0 ; n<nPOINTS ; n++)
{
store(BLANC,X(Lpoints[n]),Y(Lpoints[n]));
/* Marquage des points... */
}
}
else
{
}
if (sortir_l_image == 1)
{
write(1,image,dimX*dimY);
/* Sortie de l'image... */
}
else
{
}
}