/* jeu-tangram.c : un jeu de tangram aleatoire
 *
 * Edouard.Thiel@lif.univ-mrs.fr - 05/10/2011 - version 1.2
 *
 * Compilation sous Unix :
 *     gcc -Wall jeu-tangram.c ez-draw.c -o jeu-tangram -lX11 -lXext -lm -L/usr/X11R6/lib
 * Compilation sous Windows :
 *     gcc -Wall jeu-tangram.c ez-draw.c -o jeu-tangram.exe -lgdi32 -lm
 *
 * This program is free software under the terms of the
 * GNU Lesser General Public License (LGPL) version 2.1.
*/

#include "ez-draw.h"
#include <math.h>

#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif


/*------------------------- D E F I N I T I O N S ---------------------------*/

#define SOMMET_MAX     20
#define PIECE_MAX      50
#define BSPLINE_MAX     8
#define ANGLE_MAX     540
#define DELAI1       1500
#define DELAI2         20
#define DELAI3        500
#define ANIM2_NB      200
#define NIVEAU_INIT     5


typedef struct {
    double x, y;                        /* Coordonnees cartesiennes */
} Sommet;

typedef struct {
    Sommet sommet[SOMMET_MAX];          /* Liste des sommets */
    int nb_som;                         /* Nb de sommets du polygone */
} Polyg;

#define DIM 3
typedef double Matr[DIM][DIM];          /* [ligne][colonne] */
typedef double Vec[DIM];

typedef struct {
    double tx, ty;                      /* Translation */
    double rx, ry;                      /* Centre de rotation */
    double ra;                          /* Angle en degres */
    Matr matr;                          /* Matrice de transfo. resultante */
} Transfo;

typedef struct {
    Polyg pol_orig;                     /* Polygone d'origine */
    Sommet cg_orig;                     /* Centre de gravite de pol_orig */
    Transfo transfo;                    /* Transformation sur pol_orig */
    Polyg pol_trans;                    /* Polygone transforme' */
    Sommet cg_trans;                    /* Centre de gravite de pol_trans */
    Ez_uint32 coul_inter;               /* Couleur de l'interieur */
    Ez_uint32 coul_bord;                /* Couleur du bord */
} Piece;

typedef struct {
    Piece piece[PIECE_MAX];             /* Liste des pieces */
    int ordre_z[PIECE_MAX];             /* Ordre d'empilement des pieces */
    int nb_piece;                       /* Nombre de pieces */
} Tangram;

typedef struct {
    double px[BSPLINE_MAX];             /* Coordonnees des points de controle */
    double py[BSPLINE_MAX];             /* d'une courbe b-spline cubique */
    double pa[BSPLINE_MAX];             /* Idem pour l'angle */
} Trajec;

typedef struct {
    Trajec trajec[PIECE_MAX];           /* Trajectoires des pieces */
    int etape;
    int nb_etapes;
} Anim;

typedef struct {
    Tangram tangram;                    /* Tangram */
    int clic;                           /* Numero de la piece courante, ou -1 */
    Transfo transfo_clic;               /* Transfo de la piece lors du clic */
    double clic_x, clic_y;              /* Coordonnees du clic */
    int niveau;                         /* Nb de pieces du tangram */
    Anim anim;                          /* Parametres pour l'animation */
    int melange_auto;                   /* Flag */
    int kb_shift;                        /* Une touche control enfoncee */
    enum { E_DEBUT, E_JEU, E_ANIM2, E_MAGNET, E_GAGNE } etat;
} App;


#define TANG_X1  150
#define TANG_Y1  150
#define TANG_X2  450
#define TANG_Y2  450
#define TANG_EST_CARRE (TANG_X2-TANG_X1 == TANG_Y2-TANG_Y1)

#define WIN1_H 600
#define WIN1_L 600

typedef struct {
    App *app;
    Ez_window win1;
} Gui;


/*---------------------------- P O L Y G O N E S ----------------------------*/


void polyg_init (Polyg *polyg)
{
    polyg->nb_som = 0;
}


/*
 * Insere le sommet dans polyg en position pos.
 * Renvoie l'indice du sommet, sinon -1.
*/

int polyg_inserer_sommet_pos (Polyg *polyg, Sommet sommet, int pos)
{
    int i;

    if (polyg->nb_som >= SOMMET_MAX) {
        fprintf (stderr, "ERREUR: polyg_inserer_sommet_pos: tableau plein\n");
        return -1;
    }

    if (pos < 0 || pos > polyg->nb_som) {
        fprintf (stderr, "ERREUR: polyg_inserer_sommet_pos: mauvaise pos\n");
        return -1;
    }

    for (i = polyg->nb_som-1; i >= pos; i--)
        polyg->sommet[i+1] = polyg->sommet[i];
    polyg->sommet[pos] = sommet;
    polyg->nb_som ++;

    return pos;
}


int polyg_inserer_sommet_fin (Polyg *polyg, Sommet sommet)
{
    return polyg_inserer_sommet_pos (polyg, sommet, polyg->nb_som);
}


int polyg_inserer_point_pos (Polyg *polyg, double x, double y, int pos)
{
    Sommet sommet;

    sommet.x = x; sommet.y = y;
    return polyg_inserer_sommet_pos (polyg, sommet, pos);
}


int polyg_inserer_point_fin (Polyg *polyg, double x, double y)
{
    return polyg_inserer_point_pos (polyg, x, y, polyg->nb_som);
}


/*
 * Supprime les sommets [a..b] de polyg.
*/

void polyg_supprimer_intervalle (Polyg *polyg, int a, int b)
{
    int i;

    if (a < 0 || b >= polyg->nb_som) {
        fprintf (stderr, "ERREUR: polyg_supprimer_intervalle: mauvais ind sommets\n");
        return;
    }
    if (a > b) return;

    for (i = b+1; i < polyg->nb_som; i++)
        polyg->sommet[i+a-b-1] = polyg->sommet[i];
    polyg->nb_som -= b-a+1;
}


/*
 * Decoupe le polygone pol1 en deux polygones pol1 et pol2 sur l'arete a,b.
 * a et b sont des indices de sommet dans le polygone pol1.
*/

void polyg_decouper_par_arete (Polyg *pol1, Polyg *pol2, int a, int b)
{
    int k;

    if (a < 0 || a >= pol1->nb_som || b < 0 || b >= pol1->nb_som || a == b) {
        fprintf (stderr, "ERREUR: polyg_decouper_par_arete: mauvais ind sommets\n");
        return;
    }
    if (a > b) { int tmp = a; a = b; b = tmp; }

    polyg_init (pol2);
    for (k = a; k <= b; k++)
        polyg_inserer_sommet_fin (pol2, pol1->sommet[k]);

    polyg_supprimer_intervalle (pol1, a+1, b-1);
}


/*
 * Cree un polygone carre' de coordonnees x1..x2, y1..y2.
*/

void polyg_creer_carre (Polyg *pol, double x1, double y1, double x2, double y2)
{
    polyg_init (pol);
    polyg_inserer_point_fin (pol, x1, y1);
    polyg_inserer_point_fin (pol, x2, y1);
    polyg_inserer_point_fin (pol, x2, y2);
    polyg_inserer_point_fin (pol, x1, y2);
}


void polyg_calculer_centre_gravite (Polyg *pol, double *xg, double *yg)
{
    int i;

    *xg = *yg = 0;
    if (pol->nb_som == 0) return;

    for (i = 0; i < pol->nb_som; i++) {
        *xg += pol->sommet[i].x;
        *yg += pol->sommet[i].y;
    }
    *xg /= pol->nb_som;
    *yg /= pol->nb_som;    
}


double calculer_aire_triangle (double x1, double y1, double x2, double y2,
    double x3, double y3)
{
    double xa = x2-x1, ya = y2-y1, xb = x3-x1, yb = y3-y1;
    return fabs (xa*yb - ya*xb) / 2;
}


double polyg_calculer_aire (Polyg *polyg)
{
    int i;
    double aire = 0;

    for (i = 0; i < polyg->nb_som-2; i++)
        aire += calculer_aire_triangle (
            polyg->sommet[0].x, polyg->sommet[0].y,
            polyg->sommet[i+1].x, polyg->sommet[i+1].y,
            polyg->sommet[i+2].x, polyg->sommet[i+2].y);
    return aire;
}


/*--------------------- T R A N S F O R M A T I O N S   2 D -----------------*/


void matr_afficher (Matr m)
{
    int i, j;
    
    for (i = 0; i < DIM; i++) {
        for (j = 0; j < DIM; j++) printf ("%2.3f ", m[i][j]);
        printf ("\n");
    }
}


void matr_init_unite (Matr m)
{
    int i, j;

    for (i = 0; i < DIM; i++)
    for (j = 0; j < DIM; j++)
        m[i][j] = 0;

    for (i = 0; i < DIM; i++)
        m[i][i] = 1;
}


void matr_copier (Matr m, Matr res)
{
    int i, j;

    for (i = 0; i < DIM; i++)
    for (j = 0; j < DIM; j++)
        res[i][j] = m[i][j];
}


void matr_multiplier_par_matr (Matr m1, Matr m2, Matr res)
{
    int i, j, k;
    double d;

    for (i = 0; i < DIM; i++)
    for (j = 0; j < DIM; j++)
    {
        d = 0;
        for (k = 0; k < DIM; k++)
            d += m1[i][k] * m2[k][j];
        res[i][j] = d;
    }
}


void matr_multiplier_par_vec (Matr m1, Vec v2, Vec res)
{
    int i, k;
    double d;

    for (i = 0; i < DIM; i++)
    {
        d = 0;
        for (k = 0; k < DIM; k++)
            d += m1[i][k] * v2[k];
        res[i] = d;
    }
}


void matr_multiplier_rotation (Matr m, double ra)
{
    Matr res, tmp;
    double a, c, s;

    a = ra * M_PI / 180; c = cos(a); s = sin(a);

    tmp[0][0] =  c; tmp[0][1] =  s; tmp[0][2] =  0;
    tmp[1][0] = -s; tmp[1][1] =  c; tmp[1][2] =  0;
    tmp[2][0] =  0; tmp[2][1] =  0; tmp[2][2] =  1;
  
    matr_multiplier_par_matr (m, tmp, res);
    matr_copier (res, m);
}


void matr_multiplier_translation (Matr m, double tx, double ty)
{
    Matr res, tmp;

    tmp[0][0] =  1; tmp[0][1] =  0; tmp[0][2] = tx;
    tmp[1][0] =  0; tmp[1][1] =  1; tmp[1][2] = ty;
    tmp[2][0] =  0; tmp[2][1] =  0; tmp[2][2] =  1;
  
    matr_multiplier_par_matr (m, tmp, res);
    matr_copier (res, m);
}


void transfo_init (Transfo *t)
{
    t->tx = t->ty = 0;
    t->rx = t->ry = 0;
    t->ra = 0;
    matr_init_unite (t->matr);
}


void transfo_memoriser_translation (Transfo *t, double tx, double ty)
{
    t->tx = tx; t->ty = ty;
}


void transfo_memoriser_rotation (Transfo *t, double rx, double ry, double ra)
{
    t->rx = rx; t->ry = ry; t->ra = ra;
}


void transfo_calculer_matr (Transfo *t)
{
    matr_init_unite (t->matr);
    matr_multiplier_translation (t->matr, t->tx, t->ty);
    matr_multiplier_translation (t->matr, t->rx, t->ry);
    matr_multiplier_rotation    (t->matr, t->ra);
    matr_multiplier_translation (t->matr, -t->rx, -t->ry);
}


void transfo_appliquer_sur_point (Transfo *t, 
    double x1, double y1, double *x2, double *y2)
{
    Vec v1, v2;
    
    v1[0] = x1; v1[1] = y1; v1[2] = 1;
    matr_multiplier_par_vec (t->matr, v1, v2);

    /* Point a l'infini */
    if (v2[2] == 0) { *x2 = *y2 = -1; return; }

    *x2 = v2[0]/v2[2]; *y2 = v2[1]/v2[2]; 
}


void transfo_appliquer_sur_sommet (Transfo *t, Sommet *s1, Sommet *s2)
{
    transfo_appliquer_sur_point (t, s1->x, s1->y, &s2->x, &s2->y);
}


void transfo_appliquer_sur_polyg (Transfo *t, Polyg *p1, Polyg *p2)
{
    int i;
    double x, y;

    polyg_init (p2);

    for (i = 0; i < p1->nb_som; i++) {
        transfo_appliquer_sur_point (t, p1->sommet[i].x, p1->sommet[i].y, &x, &y);
        polyg_inserer_point_fin (p2, x, y);
    }
}


/*--------------------------------- P I E C E -------------------------------*/


void piece_init (Piece *piece)
{
    polyg_init (&piece->pol_orig);
    polyg_init (&piece->pol_trans);
    transfo_init (&piece->transfo);
    piece->coul_inter = ez_grey;
    piece->coul_bord = ez_black;
}


void piece_calculer_centre_gravite (Piece *piece)
{
    polyg_calculer_centre_gravite (&piece->pol_orig,
        &piece->cg_orig.x, &piece->cg_orig.y);
}


void piece_memoriser_translation (Piece *piece, double tx, double ty)
{
    transfo_memoriser_translation (&piece->transfo, tx, ty);
}


void piece_memoriser_rotation (Piece *piece, double ra)
{
    transfo_memoriser_rotation (&piece->transfo,
        piece->cg_orig.x, piece->cg_orig.y, ra);
}


void piece_calculer_matr (Piece *piece)
{
    transfo_calculer_matr (&piece->transfo);
}


void piece_appliquer_transformation (Piece *piece)
{
    transfo_appliquer_sur_polyg (&piece->transfo,
        &piece->pol_orig, &piece->pol_trans);
    transfo_appliquer_sur_sommet (&piece->transfo,
        &piece->cg_orig, &piece->cg_trans);
}


/*------------------------------- T A N G R A M -----------------------------*/


void tangram_init (Tangram *tangram)
{
    tangram->nb_piece = 0;
}


/*
 * Ajoute et initialise une piece dans le tangram.
 * Renvoie l'indice de la piece, sinon -1.
*/

int tangram_ajouter_piece (Tangram *tangram)
{
    if (tangram->nb_piece >= PIECE_MAX) {
        fprintf (stderr, "ERREUR: tangram_ajouter_piece: tableau plein\n");
        return -1;
    }

    piece_init (&tangram->piece[tangram->nb_piece]);
    tangram->ordre_z[tangram->nb_piece] = tangram->nb_piece;
    return tangram->nb_piece ++;
}


void tangram_placer_piece_dessus (Tangram *tangram, int i)
{
    int j;

    if (i < 0 || i >= tangram->nb_piece) {
        fprintf (stderr, "ERREUR: tangram_placer_piece_dessus: mauvais indice\n");
        return;
    }

    for (j = tangram->nb_piece-1; j >= 0; j--)
        if (tangram->ordre_z[j] == i) break;
    for (j-- ; j >= 0; j--)
        tangram->ordre_z[j+1] = tangram->ordre_z[j];
    tangram->ordre_z[0] = i;
}


void tangram_memoriser_translation (Tangram *tangram, int i, double tx, double ty)
{
    if (i < 0 || i >= tangram->nb_piece) {
        fprintf (stderr, "ERREUR: tangram_memoriser_translation: mauvais indice\n");
        return;
    }
    piece_memoriser_translation (&tangram->piece[i], tx, ty);
}


void tangram_memoriser_rotation (Tangram *tangram, int i, double ra)
{
    if (i < 0 || i >= tangram->nb_piece) {
        fprintf (stderr, "ERREUR: tangram_memoriser_rotation: mauvais indice\n");
        return;
    }
    piece_memoriser_rotation (&tangram->piece[i], ra);
}


void tangram_calculer_matr (Tangram *tangram, int i)
{
    if (i < 0 || i >= tangram->nb_piece) {
        fprintf (stderr, "ERREUR: tangram_calculer_matr: mauvais indice\n");
        return;
    }
    piece_calculer_matr (&tangram->piece[i]);
}


/*
 * Renvoie l'angle entre l'horizontale Cx et CP
 * in [0..360[
*/

double calculer_angle_horizontal (double xc, double yc, double xp, double yp)
{
    double dx = xp-xc, dy = yp-yc, a;

    if (fabs(dx) < 1E-5 && fabs(dy) < 1E-5) return 0;
    a = atan2 (dy, dx) * 180/M_PI;
    return (a < 0) ? a+360 : a;
}


double calculer_difference_angle (double xc, double yc, 
    double xp, double yp, double xq, double yq)
{
    return calculer_angle_horizontal (xc, yc, xq, yq) -
           calculer_angle_horizontal (xc, yc, xp, yp);
}


double tangram_calculer_angle_cg_trans (Tangram *tangram, int i,
    double xp, double yp, double xq, double yq)
{
    if (i < 0 || i >= tangram->nb_piece) {
        fprintf (stderr, "ERREUR: tangram_calculer_angle_cg_trans: mauvais indice\n");
        return 0;
    }

    return calculer_difference_angle (
        tangram->piece[i].cg_trans.x, tangram->piece[i].cg_trans.y,
        xp, yp, xq, yq);
}


void tangram_calculer_centre_gravite (Tangram *tangram, int i)
{
    if (i < 0 || i >= tangram->nb_piece) {
        fprintf (stderr, "ERREUR: tangram_calculer_centre_gravite: mauvais indice\n");
        return;
    }
    piece_calculer_centre_gravite (&tangram->piece[i]);
}


void tangram_calculer_centres_gravite (Tangram *tangram)
{
    int i;

    for (i = 0; i < tangram->nb_piece; i++)
        piece_calculer_centre_gravite (&tangram->piece[i]);
}


void tangram_transformer_piece (Tangram *tangram, int i)
{
    if (i < 0 || i >= tangram->nb_piece) {
        fprintf (stderr, "ERREUR: tangram_transformer_piece: mauvais indice\n");
        return;
    }
    piece_appliquer_transformation (&tangram->piece[i]);
}


void tangram_transformer_pieces (Tangram *tangram)
{
    int i;

    for (i = 0; i < tangram->nb_piece; i++)
        piece_appliquer_transformation (&tangram->piece[i]);
}


void reborner_dans_rectangle (int xmin, int ymin, int xmax, int ymax, 
    int *x, int *y)
{
    if (*x < xmin) *x = xmin;
    if (*y < ymin) *y = ymin;
    if (*x > xmax-1) *x = xmax-1;
    if (*y > ymax-1) *y = ymax-1;
}


void tangram_reborner_translation (Tangram *tangram, int i, Transfo *trans,
    int *dx, int *dy)
{
    int gx, gy, bx, by;

    if (i < 0 || i >= tangram->nb_piece) {
        fprintf (stderr, "ERREUR: tangram_reborner_translation: mauvais indice\n");
        return;
    }

    gx = tangram->piece[i].cg_orig.x;
    gy = tangram->piece[i].cg_orig.y;
    bx = trans->tx + gx;
    by = trans->ty + gy;

    reborner_dans_rectangle (-bx, -by, WIN1_L-bx, WIN1_H-by, dx, dy);
}


/*
 * Renvoie 1 si P est a droite (ou sur) la droite AB, sinon 0.
*/

int point_est_a_droite (double xp, double yp, double xa, double ya,
    double xb, double yb)
{
    double d = (xb-xa)*(yp-ya) - (yb-ya)*(xp-xa);
    return d >= 0 ? 1 : 0;
}


/*
 * Renvoie 1 si P est a l'interieur (ou sur la frontiere) du polygone, sinon 0.
 * On suppose que le polygone est convexe.
*/

int point_est_interieur (double xp, double yp, Polyg *pol)
{
    int i, j;

    for (i = 0; i < pol->nb_som; i++) {
        j = (i+1) % pol->nb_som;
        if (! point_est_a_droite (xp, yp, 
                pol->sommet[i].x, pol->sommet[i].y, 
                pol->sommet[j].x, pol->sommet[j].y) )
            return 0; 
    }
    return 1;
}


/*
 * Renvoie le numero de la piece contenant P (le premier dans l'ordre)
 * sinon -1.
*/

int tangram_rechercher_piece_cliquee (Tangram *tangram, double xp, double yp)
{
    int i, j;

    for (j = 0; j < tangram->nb_piece; j++) {
        i = tangram->ordre_z[j];
        if (point_est_interieur (xp, yp, &tangram->piece[i].pol_trans))
            return i;
    }
    return -1;
}


/*
 * Renvoie a % b in [0..b[. On suppose b > 0 
*/

double modulo_reel (double a, double b)
{
    if (a < 0) a += ((int) (1-a/b))*b;
    return a - ((int) (a/b))*b;
}


/*
 * Renvoie l'ecart d'angle minimum in [0..360[ 
*/

double ecart_angle (double a, double b)
{
    double c = modulo_reel (fabs(a-b), 360),
           d = 360 - c;
    return c < d ? c : d;
}


/*
 * Attire les pieces sur les emplacements d'origine (en tenant compte des
 * rotations a 90 degres).
 * Renvoie 1 si toutes les pieces sont a leur place.
*/

int tangram_appliquer_grille_magnetique (Tangram *tangram)
{
    Transfo t;
    int rot_a = TANG_EST_CARRE ? 90 : 180;

    t.tx = t.ty = 0;
    t.rx = (TANG_X1 + TANG_X2)/2; t.ry = (TANG_Y1 + TANG_Y2)/2;

    /* Rotations a 90 degres de la solution d'origine */
    for (t.ra = 0; t.ra < 360; t.ra += rot_a) {
        int i;
        int ok = 1;

        transfo_calculer_matr (&t);

        for (i = 0; i < tangram->nb_piece ; i++) {
            Piece *piece = &tangram->piece[i];
            Sommet c;
            double dx, dy, da;

            transfo_appliquer_sur_sommet (&t, &piece->cg_orig, &c);

            dx = fabs (c.x - piece->cg_trans.x);
            dy = fabs (c.y - piece->cg_trans.y);
            da =  ecart_angle (t.ra, piece->transfo.ra);

            /* La piece est en place */
            if (dx < 1E-5 && dy < 1E-5 && da < 1E-5) continue;

            /* La piece est presque en place */
            if (dx < 5 && dy < 5 && da < 3) 
            {
                piece->transfo.tx = c.x - piece->cg_orig.x;
                piece->transfo.ty = c.y - piece->cg_orig.y;
                piece->transfo.ra = t.ra;
                transfo_calculer_matr (&piece->transfo);
                piece_appliquer_transformation (piece);
            } else {
                ok = 0;  /* pas en place */
            }
        }

        /* Est-ce que toutes les pieces sont en place pour rot_a ? */
        if (ok) return 1;
    }
    return 0;
}


/*------------------------------ C O U L E U R S ----------------------------*/


void tangram_choisir_couleurs (Tangram *tangram)
{
    double h, g = 0.1 * ez_random (3600), s = 0.23;
    int i;

    for (i = 0; i < tangram->nb_piece; i++) {
        h = g + i * 360.0 / tangram->nb_piece;
        h = h - ((int) h / 360)*360;
        tangram->piece[i].coul_inter = ez_get_HSV (h, s, 0.99);
        tangram->piece[i].coul_bord  = ez_get_HSV (h, s, 0.8);
    }
}


/*--------------------------- G E N E R A T I O N ---------------------------*/


/*
 * Renvoie l'indice d'une piece d'aire maximale
*/

int choisir_piece_aire_max (Tangram *tangram)
{
    int i, j, k, aire_ind;
    double aire, aire_max;

    aire_max = 0; 
    aire_ind = 0;
    i = ez_random (tangram->nb_piece);

    for (j = 0; j < tangram->nb_piece; j++) {
        k = (i+j) % tangram->nb_piece;
        aire = polyg_calculer_aire (&tangram->piece[k].pol_orig);
        if (aire > aire_max) { aire_max = aire; aire_ind = k; }
    }
    return aire_ind;
}


/*
 * Renvoie l'aire de la plus petite piece
*/

double tangram_calculer_aire_plus_petite_piece (Tangram *tangram)
{
    int i;
    double aire, aire_min;

    aire_min = -1; 

    for (i = 0; i < tangram->nb_piece; i++) {
        aire = polyg_calculer_aire (&tangram->piece[i].pol_orig);
        if (aire_min < 0 || aire < aire_min) aire_min = aire;
    }
    return aire_min;
}


/*
 * Renvoie l'indice k d'une plus longue arete k,k+1 du polyg
*/

int choisir_arete_long_max (Polyg *polyg)
{
    int i, j, k, l, lg_ind;
    double dx, dy, lg, lg_max;

    lg_max = 0;
    lg_ind = 0;
    i = ez_random (polyg->nb_som);

    for (j = 0; j < polyg->nb_som; j++) {
        k = (i+j) % polyg->nb_som;
        l = (k+1) % polyg->nb_som;
        dx = polyg->sommet[l].x - polyg->sommet[k].x;
        dy = polyg->sommet[l].y - polyg->sommet[k].y;
        lg = sqrt (dx*dx + dy*dy);
        if (lg > lg_max) { lg_max = lg; lg_ind = k; }
    }
    return lg_ind;
}


/*
 * Genere un tangram de nb_pieces.
*/

void tangram_generer_decoupage (Tangram *tangram, int nb_pieces)
{
    int i;

    tangram_init (tangram);

    i = tangram_ajouter_piece (tangram);
    if (i < 0) return;
    polyg_creer_carre (&tangram->piece[i].pol_orig, 
        TANG_X1, TANG_Y1, TANG_X2, TANG_Y2);
    
    for (i = 1; i < nb_pieces; i++) {
        int p, q, a, b, c, n;
        double t;
        Polyg *polyg;

        p = choisir_piece_aire_max (tangram);
        polyg = &tangram->piece[p].pol_orig;

        a = choisir_arete_long_max (polyg);
        n = polyg->nb_som;
        b = (a+1) % n;
        t = (300 + ez_random (400)) / 1000.0;

        polyg_inserer_point_pos (polyg, 
            polyg->sommet[a].x * t + polyg->sommet[b].x * (1-t),
            polyg->sommet[a].y * t + polyg->sommet[b].y * (1-t),
            b);

        c = (b + 2 + ez_random (n-2)) % (n+1);
        q = tangram_ajouter_piece (tangram);
        if (q < 0) return;
        polyg_decouper_par_arete (polyg, &tangram->piece[q].pol_orig, b, c);
    }

    tangram_calculer_centres_gravite (tangram);
    tangram_transformer_pieces (tangram);
    tangram_choisir_couleurs (tangram);
}


/*
 * Genere plusieurs tangrams, et recopie le "meilleur" dans *tangram.
 * Le but est d'eviter les petits triangles tres plats.
 * L'heuristique est de choisir le tangram dont l'aire de la plus petite
 * piece est maximale.
*/

void tangram_generer_probleme (Tangram *tangram, int nb_pieces)
{
    Tangram essai[3];
    int i, j = 0;
    double aire, aire_max = 0;
    
    for (i = 0; i < 3; i++) {
        tangram_generer_decoupage (&essai[i], nb_pieces);
        aire = tangram_calculer_aire_plus_petite_piece (&essai[i]);
        if (aire > aire_max) { aire_max = aire; j = i; }
    }
    *tangram = essai[j];
}


void tangram_placer_pieces_en_cercle (Tangram *tangram)
{
    int i;
    double a = ez_random (360);

    for (i = 0; i < tangram->nb_piece; i++) {
        double b = (a + i * 360 / tangram->nb_piece) * M_PI / 180;

        tangram_memoriser_translation (tangram, i, 
            WIN1_L * (0.5 + 0.3*cos(b)) - tangram->piece[i].cg_orig.x, 
            WIN1_H * (0.5 + 0.3*sin(b)) - tangram->piece[i].cg_orig.y); 
        tangram_memoriser_rotation (tangram, i, ez_random (360)); 

        tangram_calculer_matr (tangram, i);
        tangram_transformer_piece (tangram, i);
    }
}


/*---------------------------- A N I M A T I O N ----------------------------*/


/*
 * Renvoie le polynome cubique de Bezier en t
 * b[0..3], t in [0..1]
*/

double calculer_bezier_cubique (double *b, double t)
{
    double s = 1.0 - t;
    return s*s*(s*b[0] + 3*t*b[1]) + t*t*(3*s*b[2] + t*b[3]);
}


/*
 * Renvoie le polynome bspline cubique en r
 * p[0..n-1], r in [0..n-3]
*/

double calculer_bspline_cubique (double *p, int n, double r)
{
    int i = r;
    double t = r-i;
    double b[4];

    if (i >= n-3) { i = n-4; t = 1.0; }

    b[0] = (p[i] + 4*p[i+1] + p[i+2])/6;
    b[1] = (2*p[i+1] + p[i+2])/3;
    b[2] = (p[i+1] + 2*p[i+2])/3;
    b[3] = (p[i+1] + 4*p[i+2] + p[i+3])/6;

    return calculer_bezier_cubique (b, t);
}


/*
 * Choisit des coordonnees de points de controle tels que :
 *  - la trajectoire commence en a et finit en b ;
 *  - les valeurs sont dans [val_min .. val_max]
*/

void app_preparer_courbe (double *p, int n, double a, double b, 
    double val_min, double val_max)
{
    int j;

    /* Des entiers suffisent */
    for (j = 2; j < n-2; j++)
        p[j] = val_min + ez_random (val_max - val_min);  

    p[1] = a; p[0] = 2*p[1] - p[2];
    p[n-2] = b; p[n-1] = 2*p[n-2] - p[n-3];
}


void app_preparer_trajectoires_melange (App *app)
{
    int i;
    double a = ez_random (360);

    for (i = 0; i < app->tangram.nb_piece; i++) {
        Piece *piece = &app->tangram.piece[i];
        double b = (a + i * 360 / app->tangram.nb_piece) * M_PI / 180;

        app_preparer_courbe (app->anim.trajec[i].px, BSPLINE_MAX,
            piece->cg_orig.x + piece->transfo.tx, 
            WIN1_L * (0.5 + 0.3*cos(b)),
            0, WIN1_L);
        app_preparer_courbe (app->anim.trajec[i].py, BSPLINE_MAX,
            piece->cg_orig.y + piece->transfo.ty,
            WIN1_H * (0.5 + 0.3*sin(b)),            
            0, WIN1_H);
        app_preparer_courbe (app->anim.trajec[i].pa, BSPLINE_MAX,
            piece->transfo.ra, 
            ez_random (360),
            -ANGLE_MAX, ANGLE_MAX);
    }
}


void app_preparer_trajectoires_solution (App *app)
{
    int i;

    for (i = 0; i < app->tangram.nb_piece; i++) {
        Piece *piece = &app->tangram.piece[i];

        app_preparer_courbe (app->anim.trajec[i].px, BSPLINE_MAX,
            piece->cg_orig.x + piece->transfo.tx, 
            piece->cg_orig.x,
            0, WIN1_L);
        app_preparer_courbe (app->anim.trajec[i].py, BSPLINE_MAX,
            piece->cg_orig.y + piece->transfo.ty,
            piece->cg_orig.y,            
            0, WIN1_H);
        app_preparer_courbe (app->anim.trajec[i].pa, BSPLINE_MAX,
            piece->transfo.ra, 
            0,
            -ANGLE_MAX, ANGLE_MAX);
    }
}


/*
 * Calcule les transformations de maniere a placer le centre des gravite
 * des pieces sur la trajectoire.
 * etape in [0..netapes-1]
*/

void app_animer_etape (App *app, int etape, int netapes)
{
    int i;
    double tx, ty, ta;
    double r = (double) etape * (BSPLINE_MAX-3) / (netapes-1);

    for (i = 0; i < app->tangram.nb_piece; i++) {
        tx = calculer_bspline_cubique (app->anim.trajec[i].px, BSPLINE_MAX, r);
        ty = calculer_bspline_cubique (app->anim.trajec[i].py, BSPLINE_MAX, r);
        ta = calculer_bspline_cubique (app->anim.trajec[i].pa, BSPLINE_MAX, r);

        tangram_memoriser_translation (&app->tangram, i, 
            tx - app->tangram.piece[i].cg_orig.x, 
            ty - app->tangram.piece[i].cg_orig.y); 
        tangram_memoriser_rotation (&app->tangram, i, ta); 

        tangram_calculer_matr (&app->tangram, i);
        tangram_transformer_piece (&app->tangram, i);
    }
}


/*------------------------------ D E S S I N S ------------------------------*/


void sommet_afficher (Ez_window win, Sommet *s)
{
    ez_draw_rectangle (win, s->x-3, s->y-3, s->x+3, s->y+3);
}


void centre_g_afficher (Ez_window win, Sommet *s)
{
    ez_draw_circle (win, s->x-3, s->y-3, s->x+3, s->y+3);
}


void polyg_afficher (Ez_window win, Polyg *polyg, 
    Ez_uint32 c_sommets, Ez_uint32 c_aretes)
{
    int i, j;

    ez_set_color (c_sommets);
    for (i = 0; i < polyg->nb_som; i++)
        sommet_afficher (win, &polyg->sommet[i]);

    ez_set_color (c_aretes);
    for (i = 0; i < polyg->nb_som; i++) {
        j = (i == 0) ? polyg->nb_som-1 : i-1;
        ez_draw_line (win, polyg->sommet[j].x, polyg->sommet[j].y,
                           polyg->sommet[i].x, polyg->sommet[i].y);
    }
}

void polyg_remplir (Ez_window win, Polyg *polyg, 
    Ez_uint32 c_inter, Ez_uint32 c_bord)
{
    int i, j;

    ez_set_color (c_inter);
    for (i = 0; i < polyg->nb_som-2; i++)
        ez_fill_triangle (win,
            polyg->sommet[0  ].x + 0.5, polyg->sommet[0  ].y + 0.5,
            polyg->sommet[i+1].x + 0.5, polyg->sommet[i+1].y + 0.5,
            polyg->sommet[i+2].x + 0.5, polyg->sommet[i+2].y + 0.5);

    ez_set_color (c_bord);
    for (i = 0; i < polyg->nb_som; i++) {
        j = (i == 0) ? polyg->nb_som-1 : i-1;
        ez_draw_line (win,
            polyg->sommet[j].x + 0.5, polyg->sommet[j].y + 0.5,
            polyg->sommet[i].x + 0.5, polyg->sommet[i].y + 0.5);
    }
}


void tangram_afficher (Ez_window win, Tangram *tangram, int clic)
{
    int j;

    /* Algorithme du peintre */
    for (j = tangram->nb_piece-1; j >= 0; j--) {
        int i = tangram->ordre_z[j];
        Piece *piece = &tangram->piece[i];
        Ez_uint32 c_bord = i == clic ? ez_red : piece->coul_bord;

        polyg_remplir (win, &piece->pol_trans, piece->coul_inter, c_bord);

        if (i == clic) {
            ez_set_color (c_bord);
            centre_g_afficher (win, &piece->cg_trans);
        }
    }
}


/*-------------------- E V E N E M E N T S   W I N   1 ----------------------*/


void win1_onExpose (Ez_event *ev)
{
    Gui *gui = ez_get_data (ev->win);
    App *app = gui->app;
    int w, h, d = 5;

    ez_set_color (ez_grey);
    ez_fill_rectangle (ev->win,
        TANG_X1-d, TANG_Y1-d, TANG_X2+d, TANG_Y2+d);
    ez_set_color (ez_white);
    ez_fill_rectangle (ev->win,
        TANG_X1, TANG_Y1, TANG_X2, TANG_Y2);

    tangram_afficher (ev->win, &app->tangram, app->clic);

    ez_set_nfont (2);
    if (app->etat == E_GAGNE) {
        ez_set_color (ez_red);
        ez_draw_text (ev->win, EZ_TC, WIN1_L/2, 10, 
            "Bravo !! Tangram avec %d pieces resolu", app->tangram.nb_piece);
    } else {
        ez_set_color (ez_magenta); 
        ez_draw_text (ev->win, EZ_TC, WIN1_L/2, 10, 
            "Placez les %d pieces dans le %s !", app->tangram.nb_piece,
            TANG_EST_CARRE ? "carre" : "rectangle");
    }

    ez_window_get_size (ev->win, &w, &h);
    ez_set_color (ez_black); ez_set_nfont (0);
    switch (app->etat) {
        case E_DEBUT : 
            ez_draw_text (ev->win, EZ_BC, WIN1_L/2, h-10,
                "Le programme jeu-tangram.c fait partie de EZ-Draw :\n"
                "http://pageperso.lif.univ-mrs.fr/~edouard.thiel/ez-draw"); 
            break;
        case E_JEU :
        case E_MAGNET :
            ez_draw_text (ev->win, EZ_BC, WIN1_L/2, h-10,
                "n : nouveau tangram   haut,bas : nombre pieces   "
                "m : melanger   r : resoudre   q : quitter\n"
                "bouton1 : tirer pour deplacer une piece    c : couleurs   "
                "a : melange auto %s\n"
                "Pour tourner une piece, tirer bouton3 ou shift+bouton1, "
                "ou utiliser la molette",
                app->melange_auto ? "ON " : "OFF");
                break;
        case E_ANIM2 : 
        case E_GAGNE :
            ez_draw_text (ev->win, EZ_BC, WIN1_L/2, h-10,
                "Animation en cours ..."); 
            break;
        default : break;
    }
}


void win1_onButtonPress (Ez_event *ev)
{
    Gui *gui = ez_get_data (ev->win);
    App *app = gui->app;
    int da = 1;

    if (app->etat == E_MAGNET) app->etat = E_JEU;
    if (app->etat != E_JEU) return;

    if (app->clic < 0 || ev->mb <= 3)
        app->clic = tangram_rechercher_piece_cliquee (&app->tangram,
            ev->mx, ev->my);

    if (app->clic < 0) { ez_send_expose (ev->win); return; }

    app->transfo_clic = app->tangram.piece[app->clic].transfo;
    app->clic_x = ev->mx;
    app->clic_y = ev->my;
    tangram_placer_piece_dessus (&app->tangram, app->clic);

    switch (ev->mb) {
        case 4 :
            da = -1;
        case 5 :
            tangram_memoriser_rotation (&app->tangram, app->clic,
                (int)(app->transfo_clic.ra - da));
            tangram_calculer_matr (&app->tangram, app->clic);
            tangram_transformer_piece (&app->tangram, app->clic);
            break;
    }
    ez_send_expose (ev->win);
}


void win1_onMotionNotify (Ez_event *ev)
{
    Gui *gui = ez_get_data (ev->win);
    App *app = gui->app;
    enum { A_AUCUNE, A_TRANSLATION, A_ROTATION} action = A_AUCUNE;

    if (app->etat != E_JEU) return;
    if (app->clic < 0) return;

    switch (ev->mb) {
        case 1 :
            action = A_TRANSLATION;
            if (app->kb_shift == 1) action = A_ROTATION;
            break;
        case 2 :
        case 3 :
            action = A_ROTATION;
            break;
    }

    switch (action) {
        case A_TRANSLATION : {
            int dx = ev->mx - app->clic_x, 
                dy = ev->my - app->clic_y;
            tangram_reborner_translation (&app->tangram, app->clic,
                &app->transfo_clic, &dx, &dy);
            tangram_memoriser_translation (&app->tangram, app->clic, 
                app->transfo_clic.tx + dx, 
                app->transfo_clic.ty + dy);
            tangram_calculer_matr (&app->tangram, app->clic);
            tangram_transformer_piece (&app->tangram, app->clic);
            ez_send_expose (ev->win);
          } break;
        case A_ROTATION : {
            double a = tangram_calculer_angle_cg_trans (&app->tangram,
                app->clic, app->clic_x, app->clic_y, ev->mx, ev->my);
            tangram_memoriser_rotation (&app->tangram, app->clic,
                (int)(app->transfo_clic.ra - a));
            tangram_calculer_matr (&app->tangram, app->clic);
            tangram_transformer_piece (&app->tangram, app->clic);
            ez_send_expose (ev->win);
          } break;
        default : break;
    }
}


void win1_onButtonRelease (Ez_event *ev)
{
    Gui *gui = ez_get_data (ev->win);
    App *app = gui->app;

    if (app->etat == E_JEU) {
        app->etat = E_MAGNET;
        ez_start_timer (ev->win, DELAI3);
    }
}


void win1_onKeyPress (Ez_event *ev)
{
    Gui *gui = ez_get_data (ev->win);
    App *app = gui->app;

    /* Comportement independant de l'etat */
    switch (ev->key_sym) {
        case XK_q : 
            ez_quit (); 
            break;

        case XK_c : {
            tangram_choisir_couleurs (&app->tangram);
            ez_send_expose (ev->win);
          } break;

        case XK_a :
            app->melange_auto = ! app->melange_auto;
            ez_send_expose (ev->win);
            break;

        case XK_Shift_L :
        case XK_Shift_R :
            app->kb_shift = 1;
            if (app->clic >= 0) {
                app->clic = -1;
                ez_send_expose (ev->win);
            }
            break;
    }

    if (app->etat == E_DEBUT || app->etat == E_MAGNET) app->etat = E_JEU;
    if (app->etat != E_JEU) return;

    switch (ev->key_sym) {
        case XK_n :
            tangram_generer_probleme (&app->tangram, app->niveau);
            if (app->melange_auto)
                tangram_placer_pieces_en_cercle (&app->tangram);
            app->clic = -1;
            ez_send_expose (ev->win);
            break;

        case XK_Up :
        case XK_KP_Up :
            app->niveau ++;
            if (app->niveau >= PIECE_MAX) app->niveau = PIECE_MAX-1;
            tangram_generer_probleme (&app->tangram, app->niveau);
            if (app->melange_auto)
                tangram_placer_pieces_en_cercle (&app->tangram);
            app->clic = -1;
            ez_send_expose (ev->win);
            break;

        case XK_Down :
        case XK_KP_Down :
            app->niveau --;
            if (app->niveau < 2) app->niveau = 2;
            tangram_generer_probleme (&app->tangram, app->niveau);
            if (app->melange_auto)
                tangram_placer_pieces_en_cercle (&app->tangram);
            app->clic = -1;
            ez_send_expose (ev->win);
            break;

        case XK_m : 
        case XK_r : {
              if (app->etat == E_DEBUT || app->etat == E_JEU) {
                  app->etat = E_ANIM2;
                  app->clic = -1;
                  if (ev->key_sym == XK_m)
                       app_preparer_trajectoires_melange (app);
                  else app_preparer_trajectoires_solution (app);
                  app->anim.etape = 0;
                  app->anim.nb_etapes = ANIM2_NB;
                  ez_start_timer (ev->win, DELAI2);
                  ez_send_expose (ev->win);
              }
          } break;
    }
}


void win1_onKeyRelease (Ez_event *ev)
{
    Gui *gui = ez_get_data (ev->win);
    App *app = gui->app;

    /* Comportement independant de l'etat */
    switch (ev->key_sym) {
        case XK_Shift_L :
        case XK_Shift_R :
            app->kb_shift = 0;
            if (app->clic >= 0) {
                app->clic = -1;
                ez_send_expose (ev->win);
            }
            break;
    }
}


void win1_onTimerNotify (Ez_event *ev)
{
    Gui *gui = ez_get_data (ev->win);
    App *app = gui->app;

    if (app->etat == E_DEBUT) {

        app->etat = E_ANIM2;
        app_preparer_trajectoires_melange (app);
        app->anim.etape = 0;
        app->anim.nb_etapes = ANIM2_NB;
    }

    if (app->etat == E_ANIM2 || app->etat == E_GAGNE) {

        app->clic = -1;
        app->anim.etape ++;
        app_animer_etape (app, app->anim.etape, app->anim.nb_etapes);
        ez_send_expose (ev->win);

        if (app->anim.etape < app->anim.nb_etapes-1)
            ez_start_timer (ev->win, DELAI2);
        else app->etat = E_JEU;

    } else if (app->etat == E_MAGNET) {

        if (tangram_appliquer_grille_magnetique (&app->tangram)) {
            app->etat = E_GAGNE;
            app_preparer_trajectoires_solution (app);
            app->anim.etape = 0;
            app->anim.nb_etapes = ANIM2_NB;
            ez_start_timer (ev->win, DELAI2);
        } else app->etat = E_JEU;
        ez_send_expose (ev->win);
    }
}


void win1_event (Ez_event *ev)       /* Appele'e a chaque evenement sur win1 */
{
    switch (ev->type) {
        case Expose        : win1_onExpose (ev); break;
        case MotionNotify  : win1_onMotionNotify (ev); break;
        case ButtonPress   : win1_onButtonPress (ev); break;
        case ButtonRelease : win1_onButtonRelease (ev); break;
        case KeyPress      : win1_onKeyPress (ev); break;
        case KeyRelease    : win1_onKeyRelease (ev); break;
        case TimerNotify   : win1_onTimerNotify (ev); break;
    }
}


/*------------------------ I N I T   G E N E R A L E ------------------------*/


void app_init (App *app)
{
    app->niveau = NIVEAU_INIT;
    tangram_generer_probleme (&app->tangram, app->niveau);
    app->clic = -1;
    app->etat = E_DEBUT;
    app->melange_auto = 1;
    app->kb_shift = 0;
}


void gui_init (Gui *gui, App *app)
{
    gui->app = app;

    gui->win1 = ez_window_create (WIN1_L, WIN1_H, "Jeu de Tangram", win1_event);
    ez_window_dbuf (gui->win1, 1);
    ez_set_data (gui->win1, gui);
    ez_start_timer (gui->win1, DELAI1);
}


/*------------------ P R O G R A M M E   P R I N C I P A L ------------------*/


int main ()
{
    App app;
    Gui gui;

    if (ez_init() < 0) exit(1);

    app_init (&app);
    gui_init (&gui, &app);

    ez_main_loop ();
    exit(0);
}