/**
 * \file lib_snake_common.c
 * \brief routines de bases pour la gestion du snake
 * \author NB - PhyTI 
 * \version x.x
 * \date 25 decembre 2009
 *
 */

#include <malloc.h>

#include "lib_snake_common.h"
#include "lib_contour.h" 
#include "lib_math.h"


/* debug */
#include <stdio.h>
#include "lib_images.h"
#include "lib_alloc.h"


/**
 * \fn struct snake_node* genere_snake_rectangle_bords(int *nb_noeud, int distance_bords,
 *                         int i_dim, int j_dim)
 *
 * \brief Initialise un snake rectangulaire par rapport au bords de l'image
 * \author NB - PhyTI
 *
 * \param[out] nb_noeud renvoie le nombre de node du snake 
 * \param[in]  distance_bords distance du rectangle par rapport au bords 
 * \param[in]  i_dim dimension verticale de l'image
 * \param[in]  j_dim dimension horizontale de l'image
 *
 * \return le pointeur du premier noeud du snake
 *
 * note : les calculs sse necessite l'alignement memoire des snake_node
 */
struct snake_node* genere_snake_rectangle_bords(uint32 *nb_noeud, uint32 distance_bords, 
						uint32 i_dim, uint32 j_dim)
{
  struct snake_node *n1, *n2, *n3 ; /* noeuds courant */
  struct snake_node *n0 = malloc(sizeof(struct snake_node)) ;

  /* n0 */
  *nb_noeud = 1 ;
  n0->posi = distance_bords ;
  n0->posj = distance_bords ;
  n0->noeud_suiv = malloc(sizeof(struct snake_node)) ;
  (*nb_noeud)++ ;
  /* n1 */
  n1 = n0->noeud_suiv ;
  n1->posi = i_dim - distance_bords ;
  n1->posj = distance_bords ; 
  n1->noeud_prec = n0 ; 
  n1->noeud_suiv = malloc(sizeof(struct snake_node)) ;
  (*nb_noeud)++ ;
  /* n2 */
  n2 = n1->noeud_suiv ;
  n2->posi = i_dim - distance_bords ;
  n2->posj = j_dim - distance_bords ; 
  n2->noeud_prec = n1 ; 
  n2->noeud_suiv = malloc(sizeof(struct snake_node)) ;
  (*nb_noeud)++ ;
  /* n3 */
  n3 = n2->noeud_suiv ;
  n3->posi = distance_bords ;
  n3->posj = j_dim - distance_bords ; 
  n3->noeud_prec = n2 ; 
  n3->noeud_suiv = n0 ;  /* on ferme le snake */
  /* n0, on ferme le snake */
  n0->noeud_prec = n3 ; 
  
  return n0 ;
}

/**
 * \fn struct snake_node* genere_snake_rectangle(int *nb_noeud,int i1,int j1,int i2,int j2, 
 *                         int i_dim, int j_dim)
 *
 * \brief Initialise un snake rectangulaire definie par deux noeuds
 * \author NB - PhyTI
 *
 * \param[out] nb_noeud renvoie le nombre de node du snake 
 * \param[in]  i1 coordonnee du coin haut-gauche
 * \param[in]  j1 coordonnee du coin haut-gauche
 * \param[in]  i2 coordonnee du coin bas-droit
 * \param[in]  j2 coordonnee du coin bas-droit 
 * \param[in]  i_dim dimension verticale de l'image
 * \param[in]  j_dim dimension horizontale de l'image
 *
 * \return le pointeur du premier noeud du snake
 *
 * note : les calculs sse necessite l'alignement memoire des snake_node
 */
struct snake_node* genere_snake_rectangle(int *nb_noeud, uint32 i1, uint32 j1, uint32 i2, uint32 j2, 
					  uint32 i_dim, uint32 j_dim)
{
  struct snake_node *n1, *n2, *n3 ; /* noeuds courant */
  struct snake_node *n0 = malloc(sizeof(struct snake_node)) ;

  /* n0 */
  *nb_noeud = 1 ;
  n0->posi = i1 ;
  n0->posj = j1 ;
  n0->noeud_suiv = malloc(sizeof(struct snake_node)) ;
  (*nb_noeud)++ ;
  /* n1 */
  n1 = n0->noeud_suiv ;
  n1->posi = i2 ;
  n1->posj = j1 ; 
  n1->noeud_prec = n0 ; 
  n1->noeud_suiv = malloc(sizeof(struct snake_node)) ;
  (*nb_noeud)++ ;
  /* n2 */
  n2 = n1->noeud_suiv ;
  n2->posi = i2 ;
  n2->posj = j2 ; 
  n2->noeud_prec = n1 ; 
  n2->noeud_suiv = malloc(sizeof(struct snake_node)) ;
  (*nb_noeud)++ ;
  /* n3 */
  n3 = n2->noeud_suiv ;
  n3->posi = i1 ;
  n3->posj = j2 ; 
  n3->noeud_prec = n2 ; 
  n3->noeud_suiv = n0 ;  /* on ferme le snake */
  /* n0, on ferme le snake */
  n0->noeud_prec = n3 ; 

  return n0 ;
}






/**
 * \fn int affiche_snake(int **image, struct snake_node *snake, 
 *                       int valseg, int valnoeud, int *liste_pixel_segment)
 *
 * \brief Affiche le snake sur une image N&B 
 * \author NB - PhyTI
 *
 * \param[out] image image ou le snake doit etre affiche 
 * \param[in]  snake premier noeud du snake 
 * \param[in]  valseg valeur de niveau de gris des segments
 * \param[in]  valnoeud valeur de niveau de gris des noeuds
 * \param[out] liste_pixel_segment pour caluls temporaire
 *
 * \return nb_noeud le nombre de noeuds du snake
 *
 */
void affiche_snake(int **image, struct snake_node *snake, int valseg, int valnoeud,
		  uint32 *liste_pixel_segment)
{
  uint32 i1, j1, i2, j2 ;
  uint32 n, nb_pixel_segment ;
  struct snake_node *np, *npp1 ;
  
  /* les segments */
  np = snake ;
  npp1 = snake->noeud_suiv ;
  do
    {
      i1 = np->posi ; j1 = np->posj ;
      i2 = npp1->posi ; j2 = npp1->posj ;
      
      nb_pixel_segment = calcul_liste_pixel_segment(i1,j1,i2,j2, liste_pixel_segment, 0) ;
      for (n=1; n<nb_pixel_segment-1; n++)
	image[liste_pixel_segment[2*n]][liste_pixel_segment[2*n+1]] = valseg ;
      
      np = npp1 ;
      npp1 = np->noeud_suiv ;
    }
  while (np != snake) ;
  
  /* les deux noeuds */
  np = snake ;
  npp1 = snake->noeud_suiv ;
  do
    {
      i1 = np->posi ; j1 = np->posj ;
      i2 = npp1->posi ; j2 = npp1->posj ;
      
      image[i1][j1] = valnoeud ;
      image[i2][j2] = valnoeud ;
      
      np = npp1 ;
      npp1 = np->noeud_suiv ;
    }
  while (np != snake) ;
}

void affiche_snake_ushort(unsigned short **image, struct snake_node *snake, int valseg, unsigned short valnoeud,
						  uint32 *liste_pixel_segment)
{
  uint32 i1, j1, i2, j2 ;
  uint32 n, nb_pixel_segment ;
  struct snake_node *np, *npp1 ;
  
  /* les segments */
  np = snake ;
  npp1 = snake->noeud_suiv ;
  do
    {
      i1 = np->posi ; j1 = np->posj ;
      i2 = npp1->posi ; j2 = npp1->posj ;
      
      nb_pixel_segment = calcul_liste_pixel_segment(i1,j1,i2,j2, liste_pixel_segment, 0) ;
      for (n=1; n<nb_pixel_segment-1; n++)
		image[liste_pixel_segment[2*n]][liste_pixel_segment[2*n+1]] = valseg ;
      
      np = npp1 ;
      npp1 = np->noeud_suiv ;
    }
  while (np != snake) ;
  
  /* les deux noeuds */
  np = snake ;
  npp1 = snake->noeud_suiv ;
  do
    {
      i1 = np->posi ; j1 = np->posj ;
      i2 = npp1->posi ; j2 = npp1->posj ;
      
      image[i1][j1] = valnoeud ;
      image[i2][j2] = valnoeud ;
      
      np = npp1 ;
      npp1 = np->noeud_suiv ;
    }
  while (np != snake) ;
}

/* ========== DEBUG ================= */
/* fonction d'affichage pour le debug */
/* affiche les deux premiers segments avec valseg-1 */
/* et incremenent les valeurs des noeuds */
void affiche_snake_couleur(int **image, struct snake_node *snake, int valseg, int valnoeud,
			   uint32 *liste_pixel_segment)
{
  uint32 i1, j1, i2, j2 ;
  uint32 n, nb_pixel_segment ;
  struct snake_node *np, *npp1 ;
  int cpt = 0;
  snake = snake->noeud_prec ;  

  /* les segments */
  np = snake ;
  npp1 = np->noeud_suiv ;
  do
    {
      i1 = np->posi ; j1 = np->posj ;
      i2 = npp1->posi ; j2 = npp1->posj ;
      
      nb_pixel_segment = calcul_liste_pixel_segment(i1,j1,i2,j2, liste_pixel_segment, 0) ;
      if (cpt < 2 )
	for (n=1; n<nb_pixel_segment-1; n++)
	  image[liste_pixel_segment[2*n]][liste_pixel_segment[2*n+1]] = valseg-1 ;
      else
	for (n=1; n<nb_pixel_segment-1; n++)
	  image[liste_pixel_segment[2*n]][liste_pixel_segment[2*n+1]] = valseg ;
	
      cpt++ ;
      np = npp1 ;
      npp1 = np->noeud_suiv ;
    }
  while (np != snake) ;
  
  /* les deux noeuds */
  cpt = 0 ;
  np = snake ;
  npp1 = snake->noeud_suiv ;
  do
    {
      i1 = np->posi ; j1 = np->posj ;
      i2 = npp1->posi ; j2 = npp1->posj ;
      
      image[i1][j1] = valnoeud+cpt ;
      image[i2][j2] = valnoeud+cpt++ ;
      
      np = npp1 ;
      npp1 = np->noeud_suiv ;
    }
  while (np != snake) ;
}

/* ========= DEBUG ===================== */
/* copie l'image du snake avec un numero */
/* de fichier incremente a chaque appel */
void debug_aff_snake(struct snake_node *snake)
{
  const int idim=256, jdim=256 ;

  int **image = new_matrix_int(idim, jdim) ;
  uint32 *liste_pixel = malloc(sizeof(int)*2*(idim+jdim)) ;
  static int iter=0 ;
  char output[256] ;
  int n;

  for (n=0; n<idim*jdim; n++)
    image[0][n] = 128 ;

  affiche_snake_couleur(image, snake, 255, 0, liste_pixel) ;
  sprintf(output, "debug_im%.4d.pgm", iter++) ;
  write_int2pgm(image, idim, idim, output, 0) ;

  del_matrix_int(image, idim); 
  free(liste_pixel);
}




/**
 * \fn int ajout_noeud_snake(struct snake_node *node, int *nb_noeud)
 * \brief ajout un noeud au snake 
 * \author NB - PhyTI
 *
 * \param[in]  node adresse du noeud 
 * \param[out] nb_noeud nombre de noeuds du snake
 *
 * \return le pointeur du nouveau noeud si ajout reussi, NULL sinon
 *
 * Ajout d'un noeud au millieu du segment.
 * !!! Pour algo rapide, cette fonction doit etre suivie
 * d'une mise a jour des contrib des noeuds qui conviennent !!!
 *
 */
struct snake_node* ajout_noeud_snake(struct snake_node *node, uint32 *nb_noeud)
{
  struct snake_node *najout ;

  najout = malloc(sizeof(struct snake_node)) ;
  
  najout->posi = node->centre_i ;
  najout->posj = node->centre_j ; 
  
  najout->noeud_prec = node ;
  najout->noeud_suiv = node->noeud_suiv ;
  node->noeud_suiv->noeud_prec = najout ;
  node->noeud_suiv = najout ; 

  (*nb_noeud)++ ;
  return najout ;
}




/**
 * \fn inline int test_croisement_segment_large(int Ai, int Aj, int Bi, int Bj,
 *				   int Ui, int Uj, int Vi, int Vj)
 *
 * \brief Test qui determine si deux segments croisent 
 * \author NB - PhyTI
 *
 * \param[in] Ai 
 * \param[in] Aj
 * \param[in] Bi
 * \param[in] Bj
 * \param[in] Ui 
 * \param[in] Uj
 * \param[in] Vi
 * \param[in] Vj
 *
 * \return  1 si croisement, 0 sinon
 *
 * Version large : autorise les triangles nulles
 * Test de croisement des segments :  
 * si deux segments AB et UV croisent, alors 
 * les triangles ABU et ABV change d'ordre de rotation 
 * ET 
 * les triangles UVA et UVB change aussi d'ordre de rotation
 *
 */
inline int test_croisement_segment_large(uint32 Ai, uint32 Aj, uint32 Bi, uint32 Bj,
				   uint32 Ui, uint32 Uj, uint32 Vi, uint32 Vj)
{
  if (sign_diff_strict(sinus_triangle(Ai, Aj, Bi, Bj, Ui, Uj),     // Bi-Ai, Uj-Aj, Ui-Ai, Bj-Aj
		       sinus_triangle(Ai, Aj, Bi, Bj, Vi, Vj)))    // Bi-Ai, Vj-Aj, Vi-Ai, Bj-Aj
    if (sign_diff_strict(sinus_triangle(Ui, Uj, Vi, Vj, Ai, Aj),   // Vi-Ui, Aj-Uj, Ai-Ui, Vj-Uj
			 sinus_triangle(Ui, Uj, Vi, Vj, Bi, Bj)))  // Vi-Ui, Bj-Uj, Bi-Ui, Vj-Uj
       return 1 ;
  return 0 ;
}


/**
 * \fn inline int test_croisement_segment_strict(int Ai, int Aj, int Bi, int Bj,
 *				   int Ui, int Uj, int Vi, int Vj)
 *
 * \brief Test qui determine si deux segments croisent 
 * \author NB - PhyTI
 *
 * \param[in] Ai 
 * \param[in] Aj
 * \param[in] Bi
 * \param[in] Bj
 * \param[in] Ui 
 * \param[in] Uj
 * \param[in] Vi
 * \param[in] Vj
 *
 * \return  1 si croisement, 0 sinon
 *
 * Version strict : n'autorise pas les triangles nulles
 * Test de croisement des segments :  
 * si deux segments AB et UV croisent, alors 
 * les triangles ABU et ABV change d'ordre de rotation 
 * ET 
 * les triangles UVA et UVB change aussi d'ordre de rotation
 *
 */
inline int test_croisement_segment_strict(uint32 Ai, uint32 Aj, uint32 Bi, uint32 Bj,
				   uint32 Ui, uint32 Uj, uint32 Vi, uint32 Vj)
{
  if (sign_diff_ou_egal_zero(sinus_triangle(Ai, Aj, Bi, Bj, Ui, Uj),
			     sinus_triangle(Ai, Aj, Bi, Bj, Vi, Vj)))  
    if (sign_diff_ou_egal_zero(sinus_triangle(Ui, Uj, Vi, Vj, Ai, Aj),
			       sinus_triangle(Ui, Uj, Vi, Vj, Bi, Bj)))
      return 1 ;
  return 0 ;
}





/**
 * \fn int test_croisement_add_noeud_large(struct snake_node *N, int Nxi, int Nxj, int seg)
 *
 * \brief test si il y a croisement de segments lors de l'ajout d'un noeud 
 * \author NB - PhyTI
 *
 * \param[in] N le noeud ou l'on veut ajouter un noeud Nx au milieu de son segment
 * \param[in] Nxi coordonnee i du nouveau node Nx
 * \param[in] Nxj coordonnee j du nouveau node Nx
 * \param[in] seg booleen pour definir quel segment on test:
 *             Nx --> Nsuiv si seg==1
 *             N --> Nx si seg==0 
 *
 * \return 1 si croisement, 0 sinon
 *
 * Version large : autorise les triangles nulles
 *
 */
int test_croisement_add_noeud_large(struct snake_node *N, uint32 Nxi, uint32 Nxj, int seg)
{
  uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
  uint32 posi, posj, suivi, suivj ; /* segment courant de test */
  struct snake_node *node, *end ;

  if (seg==1)
    {
      Nrefi = N->noeud_suiv->posi ;
      Nrefj = N->noeud_suiv->posj ;
    }
  else
    {
      Nrefi = N->posi ;
      Nrefj = N->posj ;
    }

  node = N->noeud_suiv ;
  suivi = node->posi ;
  suivj = node->posj ;

  end = N ;
  while (node != end) 
  {
    posi = suivi ;
    posj = suivj ;
    node = node->noeud_suiv ;
    suivi = node->posi ;
    suivj = node->posj ;
    if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
      return 1 ;
  }
  return 0 ;
}



/**
 * \fn int test_croisement_add_noeud_strict(struct snake_node *N, int Nxi, int Nxj, int seg)
 *
 * \brief test si il y a croisement de segments lors de l'ajout d'un noeud 
 * \author NB - PhyTI
 *
 * \param[in] N le noeud ou l'on veut ajouter un noeud Nx au milieu de son segment
 * \param[in] Nxi coordonnee i du nouveau node Nx
 * \param[in] Nxj coordonnee j du nouveau node Nx
 * \param[in] seg booleen pour definir quel segment on test:
 *             Nx --> Nsuiv si seg==1
 *             N --> Nx si seg==0 
 *
 * \return 1 si croisement, 0 sinon
 *
 * Version strict : n'autorise pas les triangles nulles
 *
 */
int test_croisement_add_noeud_strict(struct snake_node *N, uint32 Nxi, uint32 Nxj, int seg)
{
  uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
  uint32 posi, posj, suivi, suivj ; /* segment courant de test */
  struct snake_node *node, *end ;

  /* segment de reference */
  if (seg)
    {
      Nrefi = N->noeud_suiv->posi ;
      Nrefj = N->noeud_suiv->posj ;
    }
  else
    {
      Nrefi = N->posi ;
      Nrefj = N->posj ;
    }

  /* segments de tests */
  node = N->noeud_suiv ;
  suivi = node->posi ;
  suivj = node->posj ;
 
  if (seg) 
    {
      /* premier segment : il touche le segment de ref */
      /* pour Nx --> Nsuiv(ref) */
      posi = suivi ;
      posj = suivj ;
      node = node->noeud_suiv ;
      suivi = node->posi ;
      suivj = node->posj ;
      if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj,posi,posj,suivi,suivj))
	return 1 ;     
      end = N ; /* pour boucle while */
   }
  else     
    /* pour N --> Nx */ 
    end = N->noeud_prec ; /* pour boucle while */

  /* boucle sur les segments */
  while (node != end) 
  {
    posi = suivi ;
    posj = suivj ;
    node = node->noeud_suiv ;
    suivi = node->posi ;
    suivj = node->posj ;
    if (test_croisement_segment_strict(posi,posj,suivi,suivj,Nxi,Nxj,Nrefi,Nrefj))
      return 1 ;
  }

  /* dernier segment */
  /* cas N --> Nx */
  if (!seg)
    {
      posi = suivi ;
      posj = suivj ;
      node = node->noeud_suiv ;
      suivi = node->posi ;
      suivj = node->posj ;  
      if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
  	return 1 ;
    }
  return 0 ;
}






/**
 * \fn int test_croisement_move_seg_large(struct snake_node *Nx, int Nxi, int Nxj, int seg)
 *
 * \brief test si il y a croisement de segments lors du deplacement d'un noeud 
 * \author NB - PhyTI
 *
 * \param[in] Nx le noeud que l'on veut deplacer
 * \param[in] Nxi coordonnee i du nouveau node Nx
 * \param[in] Nxj coordonnee j du nouveau node Nx
 * \param[in] seg booleen pour definir quel segment on test:
 *             Nx --> Nsuiv si seg==1
 *             Nprec --> Nx si seg==0 
 *
 * \return 1 si croisement, 0 sinon
 *
 * Version large : autorise les triangles nulles
 * Version non optimisee car elle test systematiquement tout les segments du snake !
 *
 */
int test_croisement_move_seg_large(struct snake_node *Nx, uint32 Nxi, uint32 Nxj, int seg)
{
  uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
  uint32 posi, posj, suivi, suivj ; /* segment courant de test */
  struct snake_node *node, *end ;

  if (seg==1)
    {
      Nrefi = Nx->noeud_suiv->posi ;
      Nrefj = Nx->noeud_suiv->posj ;
    }
  else
    {
      Nrefi = Nx->noeud_prec->posi ;
      Nrefj = Nx->noeud_prec->posj ;
    }

  node = Nx->noeud_suiv ;
  suivi = node->posi ;
  suivj = node->posj ;

  end = Nx->noeud_prec ;
  while (node != end) 
  {
    posi = suivi ;
    posj = suivj ;
    node = node->noeud_suiv ;
    suivi = node->posi ;
    suivj = node->posj ;
    if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
      return 1 ;
  }
  return 0 ;
}



/**
 * \fn int test_croisement_move_seg_strict(struct snake_node *Nx, int Nxi, int Nxj, int seg)
 *
 * \brief test si il y a croisement de segments lors du deplacement d'un noeud 
 * \author NB - PhyTI
 *
 * \param[in] Nx le noeud que l'on veut deplacer
 * \param[in] Nxi coordonnee i du nouveau node Nx
 * \param[in] Nxj coordonnee j du nouveau node Nx
 * \param[in] seg booleen pour definir quel segment on test:
 *             Nx --> Nsuiv si seg==1
 *             Nprec --> Nx si seg==0 
 *
 * \return 1 si croisement, 0 sinon
 *
 * Version strict : n'autorise pas les triangles nulles
 * Version non optimisee car elle test systematiquement tout les segments du snake !
 */
int test_croisement_move_seg_strict(struct snake_node *Nx, uint32 Nxi, uint32 Nxj, int seg)
{
  uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
  uint32 posi, posj, suivi, suivj ; /* segment courant de test */
  struct snake_node *node, *end ;

  /* segment de reference */
  if (seg)
    {
      Nrefi = Nx->noeud_suiv->posi ;
      Nrefj = Nx->noeud_suiv->posj ;
    }
  else
    {
      Nrefi = Nx->noeud_prec->posi ;
      Nrefj = Nx->noeud_prec->posj ;
    }

  /* segments de tests */
  node = Nx->noeud_suiv ;
  suivi = node->posi ;
  suivj = node->posj ;
 
  if (seg) 
    {
      /* premier segment : il touche le segment de ref */
      /* pour Nx --> Nsuiv(ref) */
      posi = suivi ;
      posj = suivj ;
      node = node->noeud_suiv ;
      suivi = node->posi ;
      suivj = node->posj ;
      if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj,posi,posj,suivi,suivj))
	return 1 ;
      
      end = Nx->noeud_prec ; /* pour boucle while */
   }
  else     
    /* pour Nprec --> Nx */ 
    end = Nx->noeud_prec->noeud_prec ; /* pour boucle while */

  /* boucle sur les segments */
  while (node != end) 
  {
    posi = suivi ;
    posj = suivj ;
    node = node->noeud_suiv ;
    suivi = node->posi ;
    suivj = node->posj ;
    if (test_croisement_segment_strict(posi,posj,suivi,suivj,Nxi,Nxj,Nrefi,Nrefj))
      return 1 ;
  }

  /* dernier segment */
  /* cas Nprec --> Nx */
  if (!seg)
    {
      posi = suivi ;
      posj = suivj ;
      node = node->noeud_suiv ;
      suivi = node->posi ;
      suivj = node->posj ;  
      if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
  	return 1 ;
    }
  return 0 ;
}