#include "tools.h" /////////////////////////////////////////////////////////////////////////// // // Variables et fonctions internes (static) qui ne doivent pas être // visibles à l'extérieur de ce fichier. À ne pas mettre dans le .h. // /////////////////////////////////////////////////////////////////////////// // pour l'affichage de l'aide static char HELP[] = "\n\ ┌──\n\ │ Commandes pour l'interface graphique\n\ │\n\ │ [h] ... affiche l'aide\n\ │ [q] ... passe running à false\n\ │ [p] ... pause de 0\"5, maintenir pour pause plus longue\n\ │ [souris] ... déplacement d'un ou de tous les points, zoom\n\ │\n\ │ Spécifique pour TSP:\n\ │\n\ │ [s] ... change la taille des points\n\ │ [o] ... indique l'orientation de la tournée\n\ │ [r] ... indique le point de départ (racine du MST) de la tournée\n\ │ [t] ... dessine ou pas la tournée et/ou l'arbre MST\n\ │ [g] ... dessine ou pas une grille pour le positionnement des points\n\ │ [u] ... recentrage (modification) du nuage de points dans la fenêtre\n\ │ [w] ... écrit les coordonnées des points dans un fichier\n\ │\n\ │ Spécifique pour A*:\n\ │\n\ │ [c] ... maintient ou supprime les sommets visités à la fin de A*\n\ │ [+] ou [a] ... accélère drawGrid() en diminuant delay pour A*\n\ │ [-] ou [z] ... ralentis drawGrid() en augmentant delay pour A*\n\ └──\n\ "; // nombres d'appels au dessin de la grille attendus par seconde static unsigned long call_speed = 1 << 7; static bool mouse_ldown = false; // bouton souris gauche, vrai si enfoncé static bool mouse_rdown = false; // boutons souris droit, vrai si enfoncé static bool oriented = false; // pour afficher l'orientation de la tournée static bool root = false; // pour afficher le point de départ de la tournée static int selectedVertex = -1; // indice du point sélectionné avec la souris static point *POINT = NULL; // tableau de points (interne) static int nPOINT = 0; // nombre de points (de POINTS) static int mst = 3; // pour drawGraph(): // bit-0: dessin de l'arbre (1=oui/0=non) // bit-1: dessin de la tournée (1=oui/0=non) static int quadrillage = 0; // quadrillage pour drawX(): 0 (=off), 1, 2, 3, 0 static SDL_Window *window; static SDL_GLContext glcontext; static GLvoid *gridImage; // image de pixels calculée à partir d'une 'grid' G static GLuint textureName; static void drawLine(point p, point q) { glBegin(GL_LINES); glVertex2f(p.x, p.y); glVertex2f(q.x, q.y); glEnd(); } static void drawEdge(point p, point q) { double linewidth = 1; glGetDoublev(GL_LINE_WIDTH, &linewidth); glBegin(GL_LINES); glVertex2f(p.x, p.y); glVertex2f(.2*p.x+.8*q.x, .2*p.y+.8*q.y); glEnd(); glLineWidth(linewidth*5); glBegin(GL_LINES); glVertex2f(.2*p.x+.8*q.x, .2*p.y+.8*q.y); glVertex2f(q.x, q.y); glEnd(); glLineWidth(linewidth); } static void drawPoint(point p) { glPointSize(sizePt); glBegin(GL_POINTS); glVertex2f(p.x, p.y); glEnd(); } // Convertit les coordonnées pixels en coordonnées dans le dessin // https://www.khronos.org/registry/OpenGL-Refpages/gl2.1/xhtml/gluUnProject.xml static void pixelToCoord(int pixel_x, int pixel_y, double *x, double *y) { GLint viewport[4]; GLdouble proj[16]; GLdouble modelview[16]; // we query OpenGL for the necessary matrices etc. glGetIntegerv(GL_VIEWPORT, viewport); glGetDoublev(GL_PROJECTION_MATRIX, proj); glGetDoublev(GL_MODELVIEW_MATRIX, modelview); GLdouble _X = pixel_x; GLdouble _Y = viewport[3] - pixel_y; GLdouble z; // using 1.0 for winZ give us a ray gluUnProject(_X, _Y, 1.0f, modelview, proj, viewport, x, y, &z); } // Récupère les coordonnées du centre de la fenêtre static void getCenterCoord(double *x, double *y) { GLint viewport[4]; glGetIntegerv(GL_VIEWPORT, viewport); pixelToCoord((viewport[0] + viewport[2]) / 2, (viewport[1] + viewport[3]) / 2, x, y); } static int getClosestVertex(double x, double y) { // renvoie l'indice i du point le plus proche de (x,y) int res = 0; double dmin = (x - POINT[0].x) * (x - POINT[0].x) + (y - POINT[0].y) * (y - POINT[0].y); for (int i = 1; i < nPOINT; i++) { double d = (x - POINT[i].x) * (x - POINT[i].x) + (y - POINT[i].y) * (y - POINT[i].y); if (d < dmin) { dmin = d; res = i; } } return res; } static char *getTitle(void){ static char buffer[100]; sprintf(buffer,"Techniques Algorithmiques et Programmation - %d x %d (%.2lf)", width,height,scale); return buffer; } // Zoom d'un facteur s centré en (x,y) static void zoomAt(double s, double x, double y) { glTranslatef(x, y, 0); glScalef(s, s, 1.0); glTranslatef(-x, -y, 0); } // Zoom d'un facteur s centré sur la position de la souris, modifie // la variable globale scale du même facteur static void zoomMouse(double s){ int mx, my; double x, y; SDL_GetMouseState(&mx, &my); pixelToCoord(mx, my, &x, &y); zoomAt(s, x, y); scale *= s; } // set drawGrid call speed static void speedUp() { if (!call_speed) call_speed = 1; if ((call_speed << 1) != 0) call_speed <<= 1; } static void speedDown() { call_speed >>= 1; if (!call_speed) call_speed = 1; } void speedSet(unsigned long speed) { call_speed = speed; if (!call_speed) call_speed = 1; } static unsigned long speedMax() { return ULONG_MAX; } // Vrai ssi (i,j) est sur le bord de la grille G. static inline int onBorder(grid *G, int i, int j) { return (i == 0) || (j == 0) || (i == G->X - 1) || (j == G->Y - 1); } // Distance L2 entre s et t. static inline double distL2(position s, position t) { return hypot(t.x - s.x, t.y - s.y); } typedef struct { // l'ordre de la déclaration est important GLubyte R; GLubyte G; GLubyte B; } RGB; static RGB color[] = { // l'ordre de la déclaration est important {0xE0, 0xE0, 0xE0}, // TX_FREE {0x10, 0x10, 0x30}, // TX_WALL {0xF0, 0xD8, 0xA8}, // TX_SAND {0x00, 0x6D, 0xBA}, // TX_WATER {0x7C, 0x70, 0x56}, // TX_MUD {0x00, 0xA0, 0x60}, // TX_GRASS {0x70, 0xE0, 0xD0}, // TX_TUNNEL {0x80, 0x80, 0x80}, // MK_NULL {0x12, 0x66, 0x66}, // MK_USED {0x08, 0xF0, 0xF0}, // MK_FRONT {0x90, 0x68, 0xF8}, // MK_PATH {0xFF, 0x00, 0x00}, // C_START {0xFF, 0x88, 0x28}, // C_END {0x99, 0xAA, 0xCC}, // C_FINAL {0xFF, 0xFF, 0x80}, // C_END_WALL {0x66, 0x12, 0x66}, // MK_USED2 {0xC0, 0x4F, 0x16}, // C_FINAL2 {0xFF, 0xFF, 0x00}, // C_PATH2 }; // Nombre de couleurs dans color[]. static int const NCOLOR = (int)(sizeof(color)/sizeof(*color)); // Vrai ssi p est une position de la grille. Attention ! cela ne veut // pas dire que p est un sommet du graphe, car la case peut contenir // TX_WALL. static inline int inGrid(grid *G, position p) { return (0 <= p.x) && (p.x < G->X) && (0 <= p.y) && (p.y < G->Y); } // // Construit l'image de pixels (variable globale gridImage) à partir // de la grille G. Le point (0,0) de G correspond au coin en haut à // gauche. // // +--x // | // y // static void makeImage(grid *G) { // Attention! modifie update si fin=true static int cpt; // compteur d'étape lorsqu'on reconstruit le chemin RGB *I = gridImage, c; int k = 0, v, m, f; // fin = true ssi le chemin a fini d'être construit, .start et .end // ont été marqués MK_PATH tous les deux bool const fin = (G->mark[G->start.x][G->start.y] == MK_PATH) && (G->mark[G->end.x][G->end.y] == MK_PATH); // debut = vrai ssi le chemin commence à être construit bool debut = false; for (int j = 0; j < G->Y && !debut; j++) for (int i = 0; i < G->X && !debut; i++) if(G->mark[i][j]==MK_PATH) debut = true; if (fin) update = false; if (!debut) cpt = 0; if (debut) cpt++; if (debut && cpt == 1) speedSet(sqrt(call_speed/4)); double t1,t2,dmax = distL2(G->start, G->end); if (dmax == 0) dmax = 1E-10; // pour éviter la division par 0 for (int j = 0; j < G->Y; j++) for (int i = 0; i < G->X; i++) { m = G->mark[i][j]; if ((m < 0) || (m >= NCOLOR)) m = MK_NULL; v = G->texture[i][j]; if ((v < 0) || (v >= NCOLOR)) v = TX_FREE; do { // do...while(0) pour permettre des break if (m == MK_PATH) { c = color[m]; if ( fin && !erase ) c = color[C_PATH2]; break; } if (fin && erase) { c = color[v]; break; } // affiche la grille d'origine à la fin if (m == MK_NULL) { c = color[v]; break; } // si pas de marquage if (m == MK_USED || m == MK_USED2) { // interpolation de couleur entre les couleurs MK_USED(2) et // C_FINAL(2) ou bien MK_USED(2) et v si on est en train de // reconstruire le chemin position p = {.x = i, .y = j}; t1 = (m == MK_USED) ? distL2(G->start, p) / dmax : distL2(G->end, p) / dmax; t1 = fmax(t1, 0.0), t1 = fmin(t1, 1.0); t2 = (debut && erase)? 0.5 * cpt / dmax : 0; t2 = fmin(t2, 1.0); f = (m == MK_USED) ? C_FINAL : C_FINAL2; c.R = t2*color[v].R + (1-t2) * (t1 * color[f].R + (1-t1)*color[m].R); c.G = t2*color[v].G + (1-t2) * (t1 * color[f].G + (1-t1)*color[m].G); c.B = t2*color[v].B + (1-t2) * (t1 * color[f].B + (1-t1)*color[m].B); break; } c = (m == MK_NULL) ? color[v] : color[m]; break; } while (0); I[k++] = c; } if (inGrid(G, G->start)) { k = G->start.y * G->X + G->start.x; I[k] = color[C_START]; } if (inGrid(G, G->end)) { v = (G->texture[G->end.x][G->end.y] == TX_WALL) ? C_END_WALL : C_END; k = G->end.y * G->X + G->end.x; I[k] = color[v]; } } // // Alloue une grille aux dimensions x,y ainsi que son image. On force // x,y>=3 pour avoir au moins un point qui n'est pas sur le bord. // static grid allocGrid(int x, int y) { grid G; position p = {-1, -1}; G.start = G.end = p; if (x < 3) x = 3; if (y < 3) y = 3; G.X = x; G.Y = y; G.texture = malloc(x * sizeof(*(G.texture))); G.mark = malloc(x * sizeof(*(G.mark))); for (int i = 0; i < x; i++) { G.texture[i] = malloc(y * sizeof(*(G.texture[i]))); G.mark[i] = malloc(y * sizeof(*(G.mark[i]))); for (int j = 0; j < y; j++) G.mark[i][j] = MK_NULL; // initialise } gridImage = malloc(3 * x * y * sizeof(GLubyte)); return G; } /////////////////////////////////////////////////////////////////////////// // // Variables et fonctions utilisées depuis l'extérieur (non static). // À mettre dans le .h. // /////////////////////////////////////////////////////////////////////////// // valeurs par défaut int width = 640; int height = 480; bool update = true; bool running = true; bool hover = true; bool erase = true; double scale = 1; GLfloat sizePt = 5.0f; bool NextPermutation(int *P, int n) { /* Génère la prochaine permutation P de taille n dans l'ordre lexicographique. On renvoie true si la prochaine permutation a pu être déterminée et false si P était la dernière permutation (et alors P n'est pas modifiée). Il n'est pas nécessaire que les valeurs de P soit dans [0,n[. On se base sur l'algorithme classique qui est: 1. Trouver le plus grand index i tel que P[i] < P[i+1]. S'il n'existe pas, la dernière permutation est atteinte. 2. Trouver le plus grand indice j tel que P[i] < P[j]. 3. Echanger P[i] avec P[j]. 4. Renverser la suite de P[i+1] jusqu'au dernier élément. */ int i=-1, j, m=n-1, t; /* étape 1: cherche i le plus grand tq P[i]
24h (précision: 1')
1h00'00" si le temps est > 60' (précision: 1s)
1'00"0 si le temps est > 1' (précision: 1/10s)
1"00 si le temps est > 1" (précision: 1/100s)
0"000 si le temps est < 1" (précision: 1/1000s)
Pour initialiser et mettre à jour tous les chronomètres (dont le
nombre vaut CHRONOMAX), il suffit d'appeler une fois la fonction,
par exemple avec TopChrono(0). Si i<0, alors les pointeurs alloués
par l'initialisation sont désalloués. La durée maximale est
limitée à 100 jours. Si une erreur se produit (durée supérieure ou
erreur avec gettimeofday()), alors on renvoie la chaîne
"--error--".
*/
if (i >= CHRONOMAX) return "--error--";
/* variables globales, locale à la fonction */
static int first = 1; /* =1 ssi c'est la 1ère fois qu'on exécute la fonction */
static char *str[CHRONOMAX];
static struct timeval last[CHRONOMAX], tv;
int j;
if (i < 0) { /* libère les pointeurs */
if (!first) /* on a déjà alloué les chronomètres */
for (j = 0; j < CHRONOMAX; j++) free(str[j]);
first = 1;
return NULL;
}
/* tv=temps courant */
int err = gettimeofday(&tv, NULL);
if (first) { /* première fois, on alloue puis on renvoie TopChrono(i) */
first = 0;
for (j = 0; j < CHRONOMAX; j++) {
str[j] = malloc(
10); // assez grand pour "--error--", "99d99h99'" ou "23h59'59""
last[j] = tv;
}
}
/* t=temps en 1/1000" écoulé depuis le dernier appel à TopChrono(i) */
long t = (tv.tv_sec - last[i].tv_sec) * 1000L +
(tv.tv_usec - last[i].tv_usec) / 1000L;
last[i] = tv; /* met à jour le chrono interne i */
if ((t < 0L) || (err))
t = LONG_MAX; /* temps erroné */
/* écrit le résultat dans str[i] */
for (;;) { /* pour faire un break */
/* ici t est en millième de seconde */
if (t < 1000L) { /* t<1" */
sprintf(str[i], "0\"%03li", t);
break;
}
t /= 10L; /* t en centième de seconde */
if (t < 6000L) { /* t<60" */
sprintf(str[i], "%li\"%02li", t / 100L, t % 100L);
break;
}
t /= 10L; /* t en dixième de seconde */
if (t < 36000L) { /* t<1h */
sprintf(str[i], "%li'%02li\"%li", t / 360L, (t / 10L) % 60L, t % 10L);
break;
}
t /= 10L; /* t en seconde */
if (t < 86400L) { /* t<24h */
sprintf(str[i], "%lih%02li'%02li\"", t / 3600L, (t / 60L) % 60L, t % 60L);
break;
}
t /= 60L; /* t en minute */
if (t < 144000) { /* t<100 jours */
sprintf(str[i], "%lid%02lih%02li'", t / 1440L, (t / 60L) % 24L, t % 60L);
break;
}
/* error ... */
sprintf(str[i], "--error--");
}
return str[i];
#undef CHRONOMAX
}
//
// Renvoie une position aléatoire de la grille qui est uniforme parmi
// toutes les cases de la grille du type t (hors les bords de la
// grille). Si aucune case de type t n'est trouvée, la position
// {-1,-1} est renvoyée.
//
position randomPosition(grid G, int t) {
int i, j, c;
int n; // n=nombre de cases de type t hors le bord
int r = -1; // r=numéro aléatoire dans [0,n[
position p = {-1, -1}; // position par défaut
int const stop = G.X * G.Y; // pour sortir des boucles
int const x1 = G.X - 1;
int const y1 = G.Y - 1;
// On fait deux parcours: un 1er pour compter le nombre n de cases
// de type t, et un 2e pour tirer au hasard la position parmi les
// n. A la fin du premier parcours on connaît le nombre n de cases
// de type t. On tire alors au hasard un numéro r dans [0,n[. Puis
// on recommence le comptage (n=0) de cases de type t et on s'arrête
// dès qu'on arrive à la case numéro r.
c = 0;
do {
n = 0;
for (i = 1; i < x1; i++)
for (j = 1; j < y1; j++)
if (G.texture[i][j] == t) {
if (n == r){
p = (position){ i, j };
i = j = stop; // toujours faux au 1er parcours
}
n++;
}
c = 1 - c;
if (c) r = random() % n;
} while (c); // vrai la 1ère fois, faux la 2e
return p;
}
//
// Libère les pointeurs alloués par allocGrid().
//
void freeGrid(grid G) {
for (int i = 0; i < G.X; i++) {
free(G.texture[i]);
free(G.mark[i]);
}
free(G.texture);
free(G.mark);
free(gridImage);
}
//
// Renvoie une grille de dimensions x,y rempli de points aléatoires de
// type et de densité donnés. Le départ et la destination sont
// initialisées aléatroirement dans une case TX_FREE.
//
grid initGridPoints(int x, int y, int type, double density) {
grid G = allocGrid(x, y); // alloue la grille et son image
// vérifie que le type est correct, MK_NULL par défaut
if ((type < 0) || (type >= NCOLOR)) type = MK_NULL;
// met les bords et remplit l'intérieur
for (int i = 0; i < x; i++)
for (int j = 0; j < y; j++)
G.texture[i][j] =
onBorder(&G, i, j) ? TX_WALL : ((RAND01 <= density) ? type : TX_FREE);
// position start/end aléatoires
G.start = randomPosition(G, TX_FREE);
G.end = randomPosition(G, TX_FREE);
return G;
}
//
// Renvoie une grille aléatoire de dimensions x,y (au moins 3)
// correspondant à partir un labyrinthe qui est un arbre couvrant
// aléatoire uniforme. On fixe le point start = en bas à droit et end
// = en haut à gauche. La largeur des couloirs est donnée par w>0.
//
// Il s'agit de l'algorithme de Wilson par "marches aléatoires avec
// effacement de boucle" (cf. https://bl.ocks.org/mbostock/11357811)
//
grid initGridLaby(int x, int y, int w) {
// vérifie les paramètres
if (x < 3) x = 3;
if (y < 3) y = 3;
if (w <= 0) w = 1;
// alloue la grille et son image
int *texture = malloc(x * y * sizeof(*texture));
// alloue la grille et son image
grid Gw = allocGrid(x * (w + 1) + 1, y * (w + 1) + 1);
// position par défaut
Gw.start = (position){ .x = Gw.X - 2, .y = Gw.Y - 2 };
Gw.end = (position){ .x = 1, .y = 1 };
// au début des murs seulement sur les bords
for (int i = 0; i < Gw.X; i++) {
for (int j = 0; j < Gw.Y; j++) {
Gw.texture[i][j] =
((i % (w + 1) == 0) || (j % (w + 1) == 0)) ? TX_WALL : TX_FREE;
}
}
for (int i = 0; i < x; i++)
for (int j = 0; j < y; j++)
texture[i * y + j] = -1;
int count = 1;
texture[0] = 0;
while (count < x * y) {
int i0 = 0;
while (i0 < x * y && texture[i0] != -1) i0++;
texture[i0] = i0 + 1;
while (i0 < x * y) {
int x0 = i0 / y;
int y0 = i0 % y;
while (true) {
int dir = random()&3; // pareil que random()%4
switch (dir) {
case 0:
if (x0 <= 0) continue;
x0--;
break;
case 1:
if (y0 <= 0) continue;
y0--;
break;
case 2:
if (x0 >= x - 1) continue;
x0++;
break;
case 3:
if (y0 >= y - 1) continue;
y0++;
break;
}
break;
}
if (texture[x0 * y + y0] == -1) {
texture[x0 * y + y0] = i0 + 1;
i0 = x0 * y + y0;
} else {
if (texture[x0 * y + y0] > 0) {
while (i0 != x0 * y + y0 && i0 > 0) {
int i1 = texture[i0] - 1;
texture[i0] = -1;
i0 = i1;
}
} else {
int i1 = i0;
i0 = x0 * y + y0;
do {
int x0 = i0 / y;
int y0 = i0 % y;
int x1 = i1 / y;
int y1 = i1 % y;
if (x0 < x1)
for (int i = 0; i < w; ++i)
Gw.texture[x1 * (w + 1)][y0 * (w + 1) + i + 1] = TX_FREE;
if (x0 > x1)
for (int i = 0; i < w; ++i)
Gw.texture[x0 * (w + 1)][y0 * (w + 1) + i + 1] = TX_FREE;
if (y0 < y1)
for (int i = 0; i < w; ++i)
Gw.texture[x1 * (w + 1) + i + 1][y1 * (w + 1)] = TX_FREE;
if (y0 > y1)
for (int i = 0; i < w; ++i)
Gw.texture[x1 * (w + 1) + i + 1][y0 * (w + 1)] = TX_FREE;
i0 = i1;
i1 = texture[i0] - 1;
texture[i0] = 0;
count++;
} while (texture[i1] != 0);
break;
}
}
}
}
free(texture);
return Gw;
}
grid initGridFile(char *file) {
FILE *f = fopen(file, "r");
if (f == NULL) {
printf("Cannot open file \"%s\"\n", file);
exit(1);
}
char *L = NULL; // L=buffer pour la ligne de texte à lire
size_t b = 0; // b=taille du buffer L utilisé (nulle au départ)
ssize_t n; // n=nombre de caractères lus dans L, sans le '\0'
// Etape 1: on évalue la taille de la grille. On s'arrête si c'est
// la fin du fichier ou si le 1ère caractère n'est pas un '#'
int x = 0; // x=nombre de caractères sur une ligne
int y = 0; // y=nombre de lignes
while ((n = getline(&L, &b, f)) > 0) {
if (L[0] != '#') break;
if (L[n - 1] == '\n')
n--; // se termine par '\n' sauf si fin de fichier
if (n > x) x = n;
y++;
}
rewind(f);
if (x < 3) x = 3;
if (y < 3) y = 3;
grid G = allocGrid(x, y);
// met des bords et remplit l'intérieur
for (int i = 0; i < x; i++)
for (int j = 0; j < y; j++)
G.texture[i][j] = onBorder(&G, i, j) ? TX_WALL : TX_FREE;
// Etape 2: on relie le fichier et on remplit la grille
int v;
for (int j = 0; j < y; j++) {
n = getline(&L, &b, f);
if (L[n - 1] == '\n') n--; // enlève le '\n' éventuelle
for (int i = 0; i < n; i++) { // ici n<=x
switch (L[i]) {
case ' ':
v = TX_FREE;
break;
case '#':
v = TX_WALL;
break;
case ';':
v = TX_SAND;
break;
case '~':
v = TX_WATER;
break;
case ',':
v = TX_MUD;
break;
case '.':
v = TX_GRASS;
break;
case '+':
v = TX_TUNNEL;
break;
case 's':
v = TX_FREE;
G.start = (position){ .x=i, .y=j };
break;
case 't':
v = TX_FREE;
G.end = (position){ .x=i, .y=j };
break;
default:
v = TX_FREE;
}
G.texture[i][j] = v;
}
}
free(L);
fclose(f);
return G;
}
void addRandomBlob(grid G, int type, int n) {
// ne touche pas au bord de la grille: 0, G.X-1 et G.Y-1
// ni à .start et .end
int V[8][2] = {{ 0, -1}, { 1, 0}, {0, 1}, {-1, 0},
{-1, -1}, {-1, 1}, {1, -1}, { 1, 1}};
for (int i = 0; i < n; i++) // met n graines
G.texture[1 + random() % (G.X - 2)][1 + random() % (G.Y - 2)] = type;
int m = (G.X+G.Y)/2;
for (int t = 0; t < m; t++) // répète m fois
for (int i = 1; i < G.X - 1; i++)
for (int j = 1; j < G.Y - 1; j++) {
int c = 0; // c = nombre de voisins de (i,j) de texture "type"
for (int k = 0; k < 8; k++)
if (G.texture[i + V[k][0]][j + V[k][1]] == type) c++;
if (c && (random() % ((8 - c) * 20 + 1) == 0)) G.texture[i][j] = type;
}
}
static inline double angle(double const x, double const y)
/*
Renvoie l'angle de [0,2𝜋[ en radian du point de coordonnées
cartésiennes (x,y) par rapport à l'axe des abscisses (1,0). NB:
atan(y/x) donne un angle [-𝜋/2,+𝜋/2] ce qui n'est pas ce que l'on
veut. On renvoie 0 si (x,y)=(0,0).
Pour avoir ces constantes, faire sous xmaple par exemple:
> evalf(3𝜋/2,39)
*/
{
#define M_2PI 6.28318530717958647692528676655900576839 /* = 2𝜋 */
#define M_3PI_2 4.71238898038468985769396507491925432630 /* = 3𝜋/2 */
if(x==0){
if(y>0) return M_PI_2; // = 𝜋/2
if(y<0) return M_3PI_2; // = 3𝜋/2
return 0;
}
// atan(y/x) renvoie un angle entre -𝜋/2 et +𝜋/2
// l'angle est correct si x>0 et y>0
// si x,y de signe contraire alors atan(y/x)=-atan(y/x)
double const a=atan(y/x);
if(x>0) return (y>0)? a : a+M_2PI; // = a ou a+2𝜋
return a+M_PI; // = a+𝜋
}
void addRandomArc(grid G, int type, int n) {
// pour ajouter n segments (arcs) de textures t entre .star et .end
// ne touche pas au bord de la grille: 0, G.X-1 et G.Y-1
// ni à .start et .end sauf s'ils sont <0, dans ce
// cas les met à random dans TX_FREE
//
// Algo: n fois on crée un arc de cercle entre +𝜋/4 et -𝜋/4 (en fait
// 𝜋/(2c) où c=0.5 environ) autour de l'axe s-t (on tire au hasard si
// l'arc est depuis s ou depuis t). L'arc est continue selon de
// 4-voisinage.
if( !inGrid(&G,G.start) || !inGrid(&G,G.end) ){
G.start=randomPosition(G, TX_FREE);
G.end=randomPosition(G, TX_FREE);
}
// ici .star et .end sont dans la grille
if(G.start.x==G.end.x && G.start.y==G.end.y) return; // rien à faire
double d,a1,a2,t,a,da;
position p,q,u,v;
double const c=0.6;
for(int i=0;i0.5 pour une
// concentration des valeurs vers le centre et p<0.5 pour un
// écartement du centre. Les valeurs <0 de p donne des écartements au
// delà du rayon du disque. Met à jour les variables globales POINT[]
// et nPOINT.
point *generatePower(int n, double p){
POINT = malloc(n * sizeof(point));
point c = { width / 2.0, height / 2.0 }; // centre
double const r0 = 0.49*fmin(width,height);
for (int i = 0; i < n; i++) { // on place les n points
double a = 2.0 * M_PI * RAND01; // angle aléatoire
double r = r0 * pow(RAND01,p); // loi puissance
POINT[i].x = c.x + r * cos(a);
POINT[i].y = c.y + r * sin(a);
}
nPOINT = n;
return POINT;
}
// Génère n points en position convexe dans le rectangle [0,width] ×
// [0,height]. Le principe de l'algorithme, de complexité O(nlog(n)),
// est le suivant:
//
// On part de points aléatoires dans [0,1[², puis on calcule (pour les
// points finaux) la différence entre deux points consécutifs. La
// somme des n différences est nulle. On trie alors les points obtenus
// selon l'angle, puis on dessine de proche en proche les points de
// l'enveloppe convexe (avec chaque fois d'un angle croissant donc).
//
// Le dessin est ensuite recalibré pour tenir dans la fenêtre. Met à
// jour les variables globales POINT[] et nPOINT.
point *generateConvex(int n){
POINT = malloc(n * sizeof(point));
for(int i=0; i