/*
    bsptree-cor.c - Edouard Thiel - 02/06/2001
 			
    Compilation :
      cc bsptree-cor.c -o bsptree-cor `~/helium/helium-cfg --cflags --libs` -lm

    Exécution :    bsptree-cor
    
    But du TP : 
        - Programmer une autopartition en BSP-tree 2D sur des segments.
        - L'interface du programme est entièrement fournie.
        - Les fonctions à compléter sont toutes dans la partie "Algorithmes".
*/

#include <helium.h>
#include <math.h>


He_node *princ, *canvas, *panel1, *panel2, *mess1;

char bla_dessin[] = "Sommets : ajoute (tirer souris), déplace, supprime (tirer dehors)";

#define SMAX 10000
double Px[SMAX], Py[SMAX];
int Pn = 0, Pm = 0;

typedef struct {
    int pa, pb, ia, ib;
} Segment;
#define SEGMAX 2000
Segment TS[SEGMAX];
int TSn = 0;

#define MIN_DIST 3


/*--------------------------- A F F I C H A G E ------------------------------*/

int c_gris, c_rouge, c_vert, c_bleu, c_jaune, c_cyan, c_magenta;

void init_couleurs ()
{
    c_gris    = HeAllocRgb (150, 150, 150, he_white);
    c_rouge   = HeAllocRgb (255, 0, 0, he_black);
    c_vert    = HeAllocRgb (0, 255, 0, he_black);
    c_bleu    = HeAllocRgb (0, 0, 255, he_black);
    c_jaune   = HeAllocRgb (255, 255, 0, he_black);
    c_cyan    = HeAllocRgb (0, 255, 255, he_black);
    c_magenta = HeAllocRgb (255, 0, 255, he_black);
}


/*
 * Dessins de base
*/

void couleur (int coul)
{
    XSetForeground (he_display, he_gc, coul);
}

void dessin_ligne (Window win, int x1, int y1, int x2, int y2)
{
    XDrawLine (he_display, win, he_gc, x1, y1, x2, y2);
}

void dessin_sommet (Window win, int x, int y)
{
    int l = MIN_DIST;
    XDrawRectangle (he_display, win, he_gc, x-l, y-l, l*2, l*2);
}

void dessin_intersec (Window win, int x, int y)
{
    int l = MIN_DIST;
    XDrawArc (he_display, win, he_gc, x-l, y-l, l*2, l*2, 0, 360*64);
}

void dessin_numero (Window win, int x, int y, int n, int pos)
{
    char bla[64];
    sprintf (bla, "%d", n);
    HeDrawStringPos (win, he_gc, he_normal_font,
	x, y, pos, bla);
}


/*-------------------------- A L G O R I T H M E S ---------------------------*/

/*
 * Calcule le points d'intersection IA et IB d'une droite A,B avec un rectangle.
 *
 * Le rectangle a pour sommets 0,0 et larg-1,haut-1
 * La droite est définie par les points xa,ya et xb,yb
 * Les points d'intersection avec la boite sont xia,yia et xib,yib
 *
 * Remarques : le point IA doit être du côté du point A, IB du côté du point B.
 *
 *           |-----------x----------x-------|
 *           IA          A          B       IB
 *
 * L'équation de la droite passant par A,B est :
 *
 *     y*dx - x*dy + c = 0
 *   
 * avec dx = xb-xa, dy = yb-ya, c = xa*dy - ya*dx
*/

void intersection_boite (int larg, int haut, 
                         double xa, double ya, double xb, double yb,
                         double *xia, double *yia, double *xib, double *yib)
{
    double dx = xb - xa, dy = yb - ya;
    
    /* Cas particuliers */
    if (dy == 0) {
	*xia = 0; *xib = larg-1; *yia = *yib = ya;
    } else if (dx == 0) {
	*yia = 0; *yib = haut-1; *xia = *xib = xa;
    } else {
    
        /* Intersections avec bords horizontaux */
        *xia = xa + (   0  -ya)*dx/dy; *yia = 0;
        *xib = xa + (haut-1-ya)*dx/dy; *yib = haut-1;

        /* Intersection avec bords verticaux */
        if (*xia < 0) {
            *xia = 0;      *yia = ya + (   0  -xa)*dy/dx; 
        } else if (*xia >= larg) {
            *xia = larg-1; *yia = ya + (larg-1-xa)*dy/dx; 
        }
        if (*xib < 0) {
            *xib = 0;      *yib = ya + (   0  -xa)*dy/dx; 
        } else if (*xib >= larg) {
            *xib = larg-1; *yib = ya + (larg-1-xa)*dy/dx; 
        }
    }
    
    /* Echange éventuel des points pour qu'ils soient du bon côté du segment */
    if (dy < 0 || (dy == 0 && dx < 0)) { 
        double tmp;
        tmp = *xia; *xia = *xib; *xib = tmp;
        tmp = *yia; *yia = *yib; *yib = tmp;
    }
}


/*
 * Calcule l'intersection de tous les segments avec le bord du canvas,
 * et mémorise les quadruplets A,B,IA,IB dans TS[].
*/

void calcul_intersections_bords (int larg, int haut)
{
    int i;
    
    Pm = Pn;
    TSn = 0;
      
    for (i = 0; i < Pn; i += 2, Pm += 2) {
        
        intersection_boite (larg, haut, Px[i], Py[i], Px[i+1], Py[i+1],
        	&Px[Pm], &Py[Pm], &Px[Pm+1], &Py[Pm+1]);
        
	TS[TSn].pa = i;   TS[TSn].ia = Pm;
        TS[TSn].pb = i+1; TS[TSn].ib = Pm+1;
        TSn++;
    }
}


/*
 * Calcule le point d'intersection entre 2 droite et renvoie TRUE,
 * ou renvoie FALSE si les droites ne s'intersectent pas.
*/

int intersec_droites (double xa1, double ya1, double xb1, double yb1, 
                      double xa2, double ya2, double xb2, double yb2, 
                      double *xp, double *yp)
{
    double dx1 = xb1 - xa1, dy1 = yb1 - ya1, c1 = xa1*dy1 - ya1*dx1,
        dx2 = xb2 - xa2, dy2 = yb2 - ya2, c2 = xa2*dy2 - ya2*dx2,
        delta = dx1*dy2 - dx2*dy1;
    if (delta == 0) return FALSE;
    *xp = (dx1*c2 - dx2*c1) / delta;
    *yp = (dy1*c2 - dy2*c1) / delta;
    return TRUE;
}


/*
 * Renvoie -1, 0, 1 suivant que le point x,y est à gauche, sur ou à droite
 * de la droite.
*/

int signe_droite (double xa, double ya, double xb, double yb, 
                  double x, double y)
{
    double dx = xb - xa, dy = yb - ya, c = xa*dy - ya*dx,
        f = y*dx - x*dy +c;
    return f == 0 ? 0 : f < 0 ? -1 : 1;
}


/*
 * Calcul récursif du bsp-tree sur une liste de segments
*/

void rec_bsptree (int *L, int Ln)
{
    int i, j, k, LP[SEGMAX], LM[SEGMAX], LPn = 0, LMn = 0;
    
    if (Ln <= 1) return;
    
    j = L[0];
    /* printf ("intersections avec seg %d\n", j); */
    
    for (i = 1; i < Ln; i++) {
	int s_ia, s_pa, s_pb, s_ib, cas = -1;
        double xp, yp;
        
	k = L[i];

        /*
         * Calcul des signes pour les 4 points
        */
        s_ia = signe_droite (Px[TS[j].pa], Py[TS[j].pa], Px[TS[j].pb], Py[TS[j].pb],
                    Px[TS[k].ia], Py[TS[k].ia]);
        s_pa = signe_droite (Px[TS[j].pa], Py[TS[j].pa], Px[TS[j].pb], Py[TS[j].pb],
                    Px[TS[k].pa], Py[TS[k].pa]);
        s_pb = signe_droite (Px[TS[j].pa], Py[TS[j].pa], Px[TS[j].pb], Py[TS[j].pb],
                    Px[TS[k].pb], Py[TS[k].pb]);
        s_ib = signe_droite (Px[TS[j].pa], Py[TS[j].pa], Px[TS[j].pb], Py[TS[j].pb],
                    Px[TS[k].ib], Py[TS[k].ib]);

        /*
         * Recherche du type d'intersection
        */
        if (Px[TS[j].pa] == Px[TS[j].pb] && Py[TS[j].pa] == Py[TS[j].pb])
            cas = -2;
        else if (s_pa == 0 && s_pb == 0)  /* segment k inclus dans la droite j */
            cas = 0;
        else if (s_pa*s_pb < 0)      /* segment k coupé entre ]pa,pb[ */
            cas = 1;
        else if (s_ia*s_pa <= 0)     /* segment k coupé entre [ia,pa] */
            cas = 2;
        else if (s_ib*s_pb <= 0)     /* segment k coupé entre [pb,ib] */
            cas = 3;

        /* printf ("Seg %d  cas %d\n", k, cas); */
        
        /*
         * Calcul du point d'intersection
        */
        if (cas > 0)
	    if (intersec_droites (
                   Px[TS[j].pa], Py[TS[j].pa], Px[TS[j].pb], Py[TS[j].pb],
                   Px[TS[k].pa], Py[TS[k].pa], Px[TS[k].pb], Py[TS[k].pb],
                   &xp, &yp) == FALSE)
            cas = -2;
            
        /*
         * MAJ intersections
        */
        switch (cas) {
          case 0 : /* Le segment est inclus dans la droite */
                   Px[TS[k].ia] = Px[TS[k].pa]; Py[TS[k].ia] = Py[TS[k].pa];
                   Px[TS[k].ib] = Px[TS[k].pb]; Py[TS[k].ib] = Py[TS[k].pb];
                   break;
          case 1 : /* On introduit un nouveau sommet */
                   TS[TSn].ib = TS[k].ib; TS[TSn].pb = TS[k].pb;
                   TS[TSn].ia = TS[TSn].pa = TS[k].ib = TS[k].pb = Pm;
                   Px[Pm] = xp; Py[Pm] = yp;
                   /* printf ("  nouveau segment %d\n", TSn); */
                   Pm++ ; TSn++;
                   break;
          case 2 : /* On raccourcit ia */
                   Px[TS[k].ia] = xp; Py[TS[k].ia] = yp;
                   break;
          case 3 : /* On raccourcit ib */
                   Px[TS[k].ib] = xp; Py[TS[k].ib] = yp;
                   break;
        }
        
        /*
         * Insertion des segments dans les listes LP et LM
        */
        switch (cas) {
          case 1 : if (s_pa < 0) 
                        { LM[LMn++] = k;     LP[LPn++] = TSn-1; }
                   else { LM[LMn++] = TSn-1; LP[LPn++] = k;     }
                   break;
          case -1 :
          case 2 :
          case 3 : if (s_pa < 0 || s_pb < 0) 
                        LM[LMn++] = k;
                   else LP[LPn++] = k;
                   break;
        }
    }
    
    /*
     * Appels récursifs
    */
    rec_bsptree (LP, LPn);
    rec_bsptree (LM, LMn);
}


/*
 * Calcul du bsp-tree sur tous les segments de l'image.
 * appelle rec_bsptree().
*/

void calcul_bsptree ()
{
    int i, L[SEGMAX], Ln;
    
    Ln = TSn;
    for (i = 0; i < TSn; i++)
	L[i] = i;
    rec_bsptree (L, Ln);
}


/*
 * Calcul principal
*/

void calcul_principal (int larg, int haut)
{
    calcul_intersections_bords (larg, haut);
    calcul_bsptree ();    
}


/*--------------------------- C A L L B A C K S ------------------------------*/


void princ_resize (He_node *hn, int width, int height)
{
    HeSetWidth (panel1, width);
    HeSetWidth (panel2, width);
    HeJustify (panel2, NULL, HE_BOTTOM);
    HeExpand (canvas, panel2, HE_BOTTOM);
    HeExpand (canvas, NULL, HE_RIGHT);    
}

void canvas_repaint (He_node *hn, Window win)
{
    int i;
    int larg = HeGetWidth (canvas),
        haut = HeGetHeight (canvas);
        
    calcul_principal (larg, haut);
    
    HeDrawBg (canvas, he_white);
    
    couleur (c_rouge);
    for (i = 0; i < Pn; i += 2)
	dessin_ligne (win, Px[i], Py[i], Px[i+1], Py[i+1]);

    couleur (c_gris);
    for (i = 0; i < TSn; i++) {
        dessin_ligne (win, Px[TS[i].pa], Py[TS[i].pa], Px[TS[i].ia], Py[TS[i].ia]);
        dessin_ligne (win, Px[TS[i].pb], Py[TS[i].pb], Px[TS[i].ib], Py[TS[i].ib]);
    }
    
    couleur (c_bleu);
    for (i = 0; i < Pn; i++)
        dessin_sommet (win, Px[i], Py[i]);
        
    couleur (he_black);
    for (i = 0; i < TSn; i++)
        if (TS[i].pa >= Pn)
        dessin_intersec (win, Px[TS[i].pa], Py[TS[i].pa]);
        
    for (i = 0; i < TSn; i++) {
        int xm = (Px[TS[i].pa]+Px[TS[i].pb])/2,
            ym = (Py[TS[i].pa]+Py[TS[i].pb])/2;
        dessin_numero (win, xm, ym, i, HE_TOP_MIDDLE);
    }
}

int test_dist (int x0, int y0, int x1, int y1)
{
    return (abs(x1 - x0) <= MIN_DIST && abs(y1 - y0) <= MIN_DIST);
}

int cherche_clic (int x0, int y0)
{
    int i;

    for (i = 0; i < Pn; i++)
	if (test_dist (x0, y0, Px[i], Py[i]))
	    return i;

    return -1;
}

void canvas_event (He_node *hn, He_event *hev)
{
    int larg = HeGetWidth (canvas),
        haut = HeGetHeight (canvas),
        re = FALSE;
    static int clic = -1, fixe = -1;
    
    switch (hev->type) {
	
        case ButtonPress : {
            clic = cherche_clic (hev->sx, hev->sy);
            if (clic >= 0)
                fixe = clic + 1 - 2*(clic % 2);
            else {
                fixe = Pn;   Px[fixe] = hev->sx; Py[fixe] = hev->sy;
                clic = Pn+1; Px[clic] = hev->sx; Py[clic] = hev->sy;
                Pn += 2;
            }
        } break;
        
        case MotionNotify : {
            if (hev->sb > 0) {
	        Px[clic] = hev->sx; Py[clic] = hev->sy;
                re = TRUE;
            }
        } break;
        
        case ButtonRelease : {
          
            /* Sommets trop proches, ou point intérieurs */
            if ( test_dist (hev->sx, hev->sy, Px[fixe], Py[fixe]) || 
                 hev->sx < 0 || hev->sy < 0 || 
                 hev->sx >= larg || hev->sy >= haut )
            {
                /* Suppression du segment */
                Px[fixe] = Px[Pn-2]; Py[fixe] = Py[Pn-2]; 
                Px[clic] = Px[Pn-1]; Py[clic] = Py[Pn-1]; 
                Pn -= 2; re = TRUE; 
            }
        } break;
    }
 
    if (re) HePostRepaint (canvas);
}

void vider_proc (He_node *hn)
{
    Pn = Pm = TSn = 0;
    HePostRepaint (canvas);
}

void permut_proc (He_node *hn)
{
    int i, a, b, t;
    double n = Pn/2;
    
    for (i = 0; i < Pn; i+=2)
    {
        a = i;
        b = 2*(int)(n*rand()/(RAND_MAX+1.0));
        t = Px[a]; Px[a] = Px[b]; Px[b] = t;
        t = Py[a]; Py[a] = Py[b]; Py[b] = t;
        a++; b++;
        t = Px[a]; Px[a] = Px[b]; Px[b] = t;
        t = Py[a]; Py[a] = Py[b]; Py[b] = t;
    }
    
    HePostRepaint (canvas);
}

void quit_proc (He_node *hn)
{
    HeQuit(0);
}

/*--------------------------------- M A I N ----------------------------------*/

int main (int argc, char **argv)
{
   
    HeInit (&argc, &argv);
    
    init_couleurs ();
    
    princ = HeCreateFrame ();
    HeSetFrameLabel (princ, "BSP-tree 2D (cor)");
    HeSetFrameResizeProc (princ, princ_resize);
    
    panel1 = HeCreatePanel (princ);
    HeCreateButtonP (panel1, "Vider", vider_proc, NULL);
    HeCreateButtonP (panel1, "Permuter", permut_proc, NULL);
    HeCreateButtonP (panel1, "Quit", quit_proc, NULL);
    HeFit (panel1);
    
    canvas = HeCreateCanvas (princ);
    HeSetCanvasRepaintProc (canvas, canvas_repaint);
    HeSetCanvasEventProc (canvas, canvas_event);
    HeSetWidth (canvas, 400);
    HeSetHeight (canvas, 400);

    panel2 = HeCreatePanel (princ);
    mess1 = HeCreateMessageP (panel2, bla_dessin, FALSE);
    HeFit(panel2);

    HeJustify (canvas, panel1, HE_TOP);
    HeJustify (panel2, canvas, HE_TOP);
    HeFit (princ);

    return HeMainLoop (princ);
}