src/lib_snake_common.c

   1 /**
   2  * \file lib_snake_common.c
   3  * \brief routines de bases pour la gestion du snake
   4  * \author NB - PhyTI
   5  * \version x.x
   6  * \date 25 decembre 2009
   7  *
   8  */
   9
  10 #include <malloc.h>
  11
  12 #include "lib_snake_common.h"
  13 #include "lib_contour.h"
  14 #include "lib_math.h"
  15
  16
  17 /* debug */
  18 #include <stdio.h>
  19 #include "lib_images.h"
  20 #include "lib_alloc.h"
  21
  22
  23 /**
  24  * \fn struct snake_node* genere_snake_rectangle_bords(int *nb_noeud, int distance_bords,
  25  *                         int i_dim, int j_dim)
  26  *
  27  * \brief Initialise un snake rectangulaire par rapport au bords de l'image
  28  * \author NB - PhyTI
  29  *
  30  * \param[out] nb_noeud renvoie le nombre de node du snake
  31  * \param[in]  distance_bords distance du rectangle par rapport au bords
  32  * \param[in]  i_dim dimension verticale de l'image
  33  * \param[in]  j_dim dimension horizontale de l'image
  34  *
  35  * \return le pointeur du premier noeud du snake
  36  *
  37  * note : les calculs sse necessite l'alignement memoire des snake_node
  38  */
  39 struct snake_node* genere_snake_rectangle_bords(uint32 *nb_noeud, uint32 distance_bords,
  40                                                 uint32 i_dim, uint32 j_dim)
  41 {
  42   struct snake_node *n1, *n2, *n3 ; /* noeuds courant */
  43   struct snake_node *n0 = malloc(sizeof(struct snake_node)) ;
  44
  45   /* n0 */
  46   *nb_noeud = 1 ;
  47   n0->posi = distance_bords ;
  48   n0->posj = distance_bords ;
  49   n0->noeud_suiv = malloc(sizeof(struct snake_node)) ;
  50   (*nb_noeud)++ ;
  51   /* n1 */
  52   n1 = n0->noeud_suiv ;
  53   n1->posi = i_dim - distance_bords ;
  54   n1->posj = distance_bords ;
  55   n1->noeud_prec = n0 ;
  56   n1->noeud_suiv = malloc(sizeof(struct snake_node)) ;
  57   (*nb_noeud)++ ;
  58   /* n2 */
  59   n2 = n1->noeud_suiv ;
  60   n2->posi = i_dim - distance_bords ;
  61   n2->posj = j_dim - distance_bords ;
  62   n2->noeud_prec = n1 ;
  63   n2->noeud_suiv = malloc(sizeof(struct snake_node)) ;
  64   (*nb_noeud)++ ;
  65   /* n3 */
  66   n3 = n2->noeud_suiv ;
  67   n3->posi = distance_bords ;
  68   n3->posj = j_dim - distance_bords ;
  69   n3->noeud_prec = n2 ;
  70   n3->noeud_suiv = n0 ;  /* on ferme le snake */
  71   /* n0, on ferme le snake */
  72   n0->noeud_prec = n3 ;
  73
  74   return n0 ;
  75 }
  76
  77 /**
  78  * \fn struct snake_node* genere_snake_rectangle(int *nb_noeud,int i1,int j1,int i2,int j2,
  79  *                         int i_dim, int j_dim)
  80  *
  81  * \brief Initialise un snake rectangulaire definie par deux noeuds
  82  * \author NB - PhyTI
  83  *
  84  * \param[out] nb_noeud renvoie le nombre de node du snake
  85  * \param[in]  i1 coordonnee du coin haut-gauche
  86  * \param[in]  j1 coordonnee du coin haut-gauche
  87  * \param[in]  i2 coordonnee du coin bas-droit
  88  * \param[in]  j2 coordonnee du coin bas-droit
  89  * \param[in]  i_dim dimension verticale de l'image
  90  * \param[in]  j_dim dimension horizontale de l'image
  91  *
  92  * \return le pointeur du premier noeud du snake
  93  *
  94  * note : les calculs sse necessite l'alignement memoire des snake_node
  95  */
  96 struct snake_node* genere_snake_rectangle(int *nb_noeud, uint32 i1, uint32 j1, uint32 i2, uint32 j2,
  97                                           uint32 i_dim, uint32 j_dim)
  98 {
  99   struct snake_node *n1, *n2, *n3 ; /* noeuds courant */
 100   struct snake_node *n0 = malloc(sizeof(struct snake_node)) ;
 101
 102   /* n0 */
 103   *nb_noeud = 1 ;
 104   n0->posi = i1 ;
 105   n0->posj = j1 ;
 106   n0->noeud_suiv = malloc(sizeof(struct snake_node)) ;
 107   (*nb_noeud)++ ;
 108   /* n1 */
 109   n1 = n0->noeud_suiv ;
 110   n1->posi = i2 ;
 111   n1->posj = j1 ;
 112   n1->noeud_prec = n0 ;
 113   n1->noeud_suiv = malloc(sizeof(struct snake_node)) ;
 114   (*nb_noeud)++ ;
 115   /* n2 */
 116   n2 = n1->noeud_suiv ;
 117   n2->posi = i2 ;
 118   n2->posj = j2 ;
 119   n2->noeud_prec = n1 ;
 120   n2->noeud_suiv = malloc(sizeof(struct snake_node)) ;
 121   (*nb_noeud)++ ;
 122   /* n3 */
 123   n3 = n2->noeud_suiv ;
 124   n3->posi = i1 ;
 125   n3->posj = j2 ;
 126   n3->noeud_prec = n2 ;
 127   n3->noeud_suiv = n0 ;  /* on ferme le snake */
 128   /* n0, on ferme le snake */
 129   n0->noeud_prec = n3 ;
 130
 131   return n0 ;
 132 }
 133
 134
 135
 136
 137
 138
 139 /**
 140  * \fn int affiche_snake(int **image, struct snake_node *snake,
 141  *                       int valseg, int valnoeud, int *liste_pixel_segment)
 142  *
 143  * \brief Affiche le snake sur une image N&B
 144  * \author NB - PhyTI
 145  *
 146  * \param[out] image image ou le snake doit etre affiche
 147  * \param[in]  snake premier noeud du snake
 148  * \param[in]  valseg valeur de niveau de gris des segments
 149  * \param[in]  valnoeud valeur de niveau de gris des noeuds
 150  * \param[out] liste_pixel_segment pour caluls temporaire
 151  *
 152  * \return nb_noeud le nombre de noeuds du snake
 153  *
 154  */
 155 void affiche_snake(int **image, struct snake_node *snake, int valseg, int valnoeud,
 156                   uint32 *liste_pixel_segment)
 157 {
 158   uint32 i1, j1, i2, j2 ;
 159   uint32 n, nb_pixel_segment ;
 160   struct snake_node *np, *npp1 ;
 161
 162   /* les segments */
 163   np = snake ;
 164   npp1 = snake->noeud_suiv ;
 165   do
 166     {
 167       i1 = np->posi ; j1 = np->posj ;
 168       i2 = npp1->posi ; j2 = npp1->posj ;
 169
 170       nb_pixel_segment = calcul_liste_pixel_segment(i1,j1,i2,j2, liste_pixel_segment, 0) ;
 171       for (n=1; n<nb_pixel_segment-1; n++)
 172         image[liste_pixel_segment[2*n]][liste_pixel_segment[2*n+1]] = valseg ;
 173
 174       np = npp1 ;
 175       npp1 = np->noeud_suiv ;
 176     }
 177   while (np != snake) ;
 178
 179   /* les deux noeuds */
 180   np = snake ;
 181   npp1 = snake->noeud_suiv ;
 182   do
 183     {
 184       i1 = np->posi ; j1 = np->posj ;
 185       i2 = npp1->posi ; j2 = npp1->posj ;
 186
 187       image[i1][j1] = valnoeud ;
 188       image[i2][j2] = valnoeud ;
 189
 190       np = npp1 ;
 191       npp1 = np->noeud_suiv ;
 192     }
 193   while (np != snake) ;
 194 }
 195
 196 void affiche_snake_ushort(unsigned short **image, struct snake_node *snake, int valseg, unsigned short valnoeud,
 197                                                   uint32 *liste_pixel_segment)
 198 {
 199   uint32 i1, j1, i2, j2 ;
 200   uint32 n, nb_pixel_segment ;
 201   struct snake_node *np, *npp1 ;
 202
 203   /* les segments */
 204   np = snake ;
 205   npp1 = snake->noeud_suiv ;
 206
 207   do
 208     {
 209       i1 = np->posi ; j1 = np->posj ;
 210       i2 = npp1->posi ; j2 = npp1->posj ;
 211
 212       nb_pixel_segment = calcul_liste_pixel_segment(i1,j1,i2,j2, liste_pixel_segment, 0) ;
 213
 214       for (n=1; n<nb_pixel_segment-1; n++)
 215                 image[liste_pixel_segment[2*n]][liste_pixel_segment[2*n+1]] = valseg ;
 216
 217       np = npp1 ;
 218       npp1 = np->noeud_suiv ;
 219
 220     }
 221   while (np != snake) ;
 222
 223   /* les deux noeuds */
 224   np = snake ;
 225   npp1 = snake->noeud_suiv ;
 226   /*
 227   do
 228     {
 229       i1 = np->posi ; j1 = np->posj ;
 230       i2 = npp1->posi ; j2 = npp1->posj ;
 231
 232       image[i1][j1] = valnoeud ;
 233       image[i2][j2] = valnoeud ;
 234
 235       np = npp1 ;
 236       npp1 = np->noeud_suiv ;
 237     }
 238         while (np != snake) ;
 239   */
 240 }
 241
 242 /* ========== DEBUG ================= */
 243 /* fonction d'affichage pour le debug */
 244 /* affiche les deux premiers segments avec valseg-1 */
 245 /* et incremenent les valeurs des noeuds */
 246 void affiche_snake_couleur(int **image, struct snake_node *snake, int valseg, int valnoeud,
 247                            uint32 *liste_pixel_segment)
 248 {
 249   uint32 i1, j1, i2, j2 ;
 250   uint32 n, nb_pixel_segment ;
 251   struct snake_node *np, *npp1 ;
 252   int cpt = 0;
 253   snake = snake->noeud_prec ;
 254
 255   /* les segments */
 256   np = snake ;
 257   npp1 = np->noeud_suiv ;
 258   do
 259     {
 260       i1 = np->posi ; j1 = np->posj ;
 261       i2 = npp1->posi ; j2 = npp1->posj ;
 262
 263       nb_pixel_segment = calcul_liste_pixel_segment(i1,j1,i2,j2, liste_pixel_segment, 0) ;
 264       if (cpt < 2 )
 265         for (n=1; n<nb_pixel_segment-1; n++)
 266           image[liste_pixel_segment[2*n]][liste_pixel_segment[2*n+1]] = valseg-1 ;
 267       else
 268         for (n=1; n<nb_pixel_segment-1; n++)
 269           image[liste_pixel_segment[2*n]][liste_pixel_segment[2*n+1]] = valseg ;
 270
 271       cpt++ ;
 272       np = npp1 ;
 273       npp1 = np->noeud_suiv ;
 274     }
 275   while (np != snake) ;
 276
 277   /* les deux noeuds */
 278   cpt = 0 ;
 279   np = snake ;
 280   npp1 = snake->noeud_suiv ;
 281   do
 282     {
 283       i1 = np->posi ; j1 = np->posj ;
 284       i2 = npp1->posi ; j2 = npp1->posj ;
 285
 286       image[i1][j1] = valnoeud+cpt ;
 287       image[i2][j2] = valnoeud+cpt++ ;
 288
 289       np = npp1 ;
 290       npp1 = np->noeud_suiv ;
 291     }
 292   while (np != snake) ;
 293 }
 294
 295 /* ========= DEBUG ===================== */
 296 /* copie l'image du snake avec un numero */
 297 /* de fichier incremente a chaque appel */
 298 void debug_aff_snake(struct snake_node *snake)
 299 {
 300   const int idim=256, jdim=256 ;
 301
 302   int **image = new_matrix_int(idim, jdim) ;
 303   uint32 *liste_pixel = malloc(sizeof(int)*2*(idim+jdim)) ;
 304   static int iter=0 ;
 305   char output[256] ;
 306   int n;
 307
 308   for (n=0; n<idim*jdim; n++)
 309     image[0][n] = 128 ;
 310
 311   affiche_snake_couleur(image, snake, 255, 0, liste_pixel) ;
 312   sprintf(output, "debug_im%.4d.pgm", iter++) ;
 313   write_int2pgm(image, idim, idim, output, 0) ;
 314
 315   del_matrix_int(image, idim);
 316   free(liste_pixel);
 317 }
 318
 319
 320
 321
 322 /**
 323  * \fn int ajout_noeud_snake(struct snake_node *node, int *nb_noeud)
 324  * \brief ajout un noeud au snake
 325  * \author NB - PhyTI
 326  *
 327  * \param[in]  node adresse du noeud
 328  * \param[out] nb_noeud nombre de noeuds du snake
 329  *
 330  * \return le pointeur du nouveau noeud si ajout reussi, NULL sinon
 331  *
 332  * Ajout d'un noeud au millieu du segment.
 333  * !!! Pour algo rapide, cette fonction doit etre suivie
 334  * d'une mise a jour des contrib des noeuds qui conviennent !!!
 335  *
 336  */
 337 struct snake_node* ajout_noeud_snake(struct snake_node *node, uint32 *nb_noeud)
 338 {
 339   struct snake_node *najout ;
 340
 341   najout = malloc(sizeof(struct snake_node)) ;
 342
 343   najout->posi = node->centre_i ;
 344   najout->posj = node->centre_j ;
 345
 346   najout->noeud_prec = node ;
 347   najout->noeud_suiv = node->noeud_suiv ;
 348   node->noeud_suiv->noeud_prec = najout ;
 349   node->noeud_suiv = najout ;
 350
 351   (*nb_noeud)++ ;
 352   return najout ;
 353 }
 354
 355
 356
 357
 358 /**
 359  * \fn inline int test_croisement_segment_large(int Ai, int Aj, int Bi, int Bj,
 360  *                                 int Ui, int Uj, int Vi, int Vj)
 361  *
 362  * \brief Test qui determine si deux segments croisent
 363  * \author NB - PhyTI
 364  *
 365  * \param[in] Ai
 366  * \param[in] Aj
 367  * \param[in] Bi
 368  * \param[in] Bj
 369  * \param[in] Ui
 370  * \param[in] Uj
 371  * \param[in] Vi
 372  * \param[in] Vj
 373  *
 374  * \return  1 si croisement, 0 sinon
 375  *
 376  * Version large : autorise les triangles nulles
 377  * Test de croisement des segments :
 378  * si deux segments AB et UV croisent, alors
 379  * les triangles ABU et ABV change d'ordre de rotation
 380  * ET
 381  * les triangles UVA et UVB change aussi d'ordre de rotation
 382  *
 383  */
 384 inline int test_croisement_segment_large(uint32 Ai, uint32 Aj, uint32 Bi, uint32 Bj,
 385                                    uint32 Ui, uint32 Uj, uint32 Vi, uint32 Vj)
 386 {
 387   if (sign_diff_strict(sinus_triangle(Ai, Aj, Bi, Bj, Ui, Uj),     // Bi-Ai, Uj-Aj, Ui-Ai, Bj-Aj
 388                        sinus_triangle(Ai, Aj, Bi, Bj, Vi, Vj)))    // Bi-Ai, Vj-Aj, Vi-Ai, Bj-Aj
 389     if (sign_diff_strict(sinus_triangle(Ui, Uj, Vi, Vj, Ai, Aj),   // Vi-Ui, Aj-Uj, Ai-Ui, Vj-Uj
 390                          sinus_triangle(Ui, Uj, Vi, Vj, Bi, Bj)))  // Vi-Ui, Bj-Uj, Bi-Ui, Vj-Uj
 391        return 1 ;
 392   return 0 ;
 393 }
 394
 395
 396 /**
 397  * \fn inline int test_croisement_segment_strict(int Ai, int Aj, int Bi, int Bj,
 398  *                                 int Ui, int Uj, int Vi, int Vj)
 399  *
 400  * \brief Test qui determine si deux segments croisent
 401  * \author NB - PhyTI
 402  *
 403  * \param[in] Ai
 404  * \param[in] Aj
 405  * \param[in] Bi
 406  * \param[in] Bj
 407  * \param[in] Ui
 408  * \param[in] Uj
 409  * \param[in] Vi
 410  * \param[in] Vj
 411  *
 412  * \return  1 si croisement, 0 sinon
 413  *
 414  * Version strict : n'autorise pas les triangles nulles
 415  * Test de croisement des segments :
 416  * si deux segments AB et UV croisent, alors
 417  * les triangles ABU et ABV change d'ordre de rotation
 418  * ET
 419  * les triangles UVA et UVB change aussi d'ordre de rotation
 420  *
 421  */
 422 inline int test_croisement_segment_strict(uint32 Ai, uint32 Aj, uint32 Bi, uint32 Bj,
 423                                    uint32 Ui, uint32 Uj, uint32 Vi, uint32 Vj)
 424 {
 425   if (sign_diff_ou_egal_zero(sinus_triangle(Ai, Aj, Bi, Bj, Ui, Uj),
 426                              sinus_triangle(Ai, Aj, Bi, Bj, Vi, Vj)))
 427     if (sign_diff_ou_egal_zero(sinus_triangle(Ui, Uj, Vi, Vj, Ai, Aj),
 428                                sinus_triangle(Ui, Uj, Vi, Vj, Bi, Bj)))
 429       return 1 ;
 430   return 0 ;
 431 }
 432
 433
 434
 435
 436
 437 /**
 438  * \fn int test_croisement_add_noeud_large(struct snake_node *N, int Nxi, int Nxj, int seg)
 439  *
 440  * \brief test si il y a croisement de segments lors de l'ajout d'un noeud
 441  * \author NB - PhyTI
 442  *
 443  * \param[in] N le noeud ou l'on veut ajouter un noeud Nx au milieu de son segment
 444  * \param[in] Nxi coordonnee i du nouveau node Nx
 445  * \param[in] Nxj coordonnee j du nouveau node Nx
 446  * \param[in] seg booleen pour definir quel segment on test:
 447  *             Nx --> Nsuiv si seg==1
 448  *             N --> Nx si seg==0
 449  *
 450  * \return 1 si croisement, 0 sinon
 451  *
 452  * Version large : autorise les triangles nulles
 453  *
 454  */
 455 int test_croisement_add_noeud_large(struct snake_node *N, uint32 Nxi, uint32 Nxj, int seg)
 456 {
 457   uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
 458   uint32 posi, posj, suivi, suivj ; /* segment courant de test */
 459   struct snake_node *node, *end ;
 460
 461   if (seg==1)
 462     {
 463       Nrefi = N->noeud_suiv->posi ;
 464       Nrefj = N->noeud_suiv->posj ;
 465     }
 466   else
 467     {
 468       Nrefi = N->posi ;
 469       Nrefj = N->posj ;
 470     }
 471
 472   node = N->noeud_suiv ;
 473   suivi = node->posi ;
 474   suivj = node->posj ;
 475
 476   end = N ;
 477   while (node != end)
 478   {
 479     posi = suivi ;
 480     posj = suivj ;
 481     node = node->noeud_suiv ;
 482     suivi = node->posi ;
 483     suivj = node->posj ;
 484     if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
 485       return 1 ;
 486   }
 487   return 0 ;
 488 }
 489
 490
 491
 492 /**
 493  * \fn int test_croisement_add_noeud_strict(struct snake_node *N, int Nxi, int Nxj, int seg)
 494  *
 495  * \brief test si il y a croisement de segments lors de l'ajout d'un noeud
 496  * \author NB - PhyTI
 497  *
 498  * \param[in] N le noeud ou l'on veut ajouter un noeud Nx au milieu de son segment
 499  * \param[in] Nxi coordonnee i du nouveau node Nx
 500  * \param[in] Nxj coordonnee j du nouveau node Nx
 501  * \param[in] seg booleen pour definir quel segment on test:
 502  *             Nx --> Nsuiv si seg==1
 503  *             N --> Nx si seg==0
 504  *
 505  * \return 1 si croisement, 0 sinon
 506  *
 507  * Version strict : n'autorise pas les triangles nulles
 508  *
 509  */
 510 int test_croisement_add_noeud_strict(struct snake_node *N, uint32 Nxi, uint32 Nxj, int seg)
 511 {
 512   uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
 513   uint32 posi, posj, suivi, suivj ; /* segment courant de test */
 514   struct snake_node *node, *end ;
 515
 516   /* segment de reference */
 517   if (seg)
 518     {
 519       Nrefi = N->noeud_suiv->posi ;
 520       Nrefj = N->noeud_suiv->posj ;
 521     }
 522   else
 523     {
 524       Nrefi = N->posi ;
 525       Nrefj = N->posj ;
 526     }
 527
 528   /* segments de tests */
 529   node = N->noeud_suiv ;
 530   suivi = node->posi ;
 531   suivj = node->posj ;
 532
 533   if (seg)
 534     {
 535       /* premier segment : il touche le segment de ref */
 536       /* pour Nx --> Nsuiv(ref) */
 537       posi = suivi ;
 538       posj = suivj ;
 539       node = node->noeud_suiv ;
 540       suivi = node->posi ;
 541       suivj = node->posj ;
 542       if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj,posi,posj,suivi,suivj))
 543         return 1 ;
 544       end = N ; /* pour boucle while */
 545    }
 546   else
 547     /* pour N --> Nx */
 548     end = N->noeud_prec ; /* pour boucle while */
 549
 550   /* boucle sur les segments */
 551   while (node != end)
 552   {
 553     posi = suivi ;
 554     posj = suivj ;
 555     node = node->noeud_suiv ;
 556     suivi = node->posi ;
 557     suivj = node->posj ;
 558     if (test_croisement_segment_strict(posi,posj,suivi,suivj,Nxi,Nxj,Nrefi,Nrefj))
 559       return 1 ;
 560   }
 561
 562   /* dernier segment */
 563   /* cas N --> Nx */
 564   if (!seg)
 565     {
 566       posi = suivi ;
 567       posj = suivj ;
 568       node = node->noeud_suiv ;
 569       suivi = node->posi ;
 570       suivj = node->posj ;
 571       if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
 572         return 1 ;
 573     }
 574   return 0 ;
 575 }
 576
 577
 578
 579
 580
 581
 582 /**
 583  * \fn int test_croisement_move_seg_large(struct snake_node *Nx, int Nxi, int Nxj, int seg)
 584  *
 585  * \brief test si il y a croisement de segments lors du deplacement d'un noeud
 586  * \author NB - PhyTI
 587  *
 588  * \param[in] Nx le noeud que l'on veut deplacer
 589  * \param[in] Nxi coordonnee i du nouveau node Nx
 590  * \param[in] Nxj coordonnee j du nouveau node Nx
 591  * \param[in] seg booleen pour definir quel segment on test:
 592  *             Nx --> Nsuiv si seg==1
 593  *             Nprec --> Nx si seg==0
 594  *
 595  * \return 1 si croisement, 0 sinon
 596  *
 597  * Version large : autorise les triangles nulles
 598  * Version non optimisee car elle test systematiquement tout les segments du snake !
 599  *
 600  */
 601 int test_croisement_move_seg_large(struct snake_node *Nx, uint32 Nxi, uint32 Nxj, int seg)
 602 {
 603   uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
 604   uint32 posi, posj, suivi, suivj ; /* segment courant de test */
 605   struct snake_node *node, *end ;
 606
 607   if (seg==1)
 608     {
 609       Nrefi = Nx->noeud_suiv->posi ;
 610       Nrefj = Nx->noeud_suiv->posj ;
 611     }
 612   else
 613     {
 614       Nrefi = Nx->noeud_prec->posi ;
 615       Nrefj = Nx->noeud_prec->posj ;
 616     }
 617
 618   node = Nx->noeud_suiv ;
 619   suivi = node->posi ;
 620   suivj = node->posj ;
 621
 622   end = Nx->noeud_prec ;
 623   while (node != end)
 624   {
 625     posi = suivi ;
 626     posj = suivj ;
 627     node = node->noeud_suiv ;
 628     suivi = node->posi ;
 629     suivj = node->posj ;
 630     if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
 631       return 1 ;
 632   }
 633   return 0 ;
 634 }
 635
 636
 637
 638 /**
 639  * \fn int test_croisement_move_seg_strict(struct snake_node *Nx, int Nxi, int Nxj, int seg)
 640  *
 641  * \brief test si il y a croisement de segments lors du deplacement d'un noeud
 642  * \author NB - PhyTI
 643  *
 644  * \param[in] Nx le noeud que l'on veut deplacer
 645  * \param[in] Nxi coordonnee i du nouveau node Nx
 646  * \param[in] Nxj coordonnee j du nouveau node Nx
 647  * \param[in] seg booleen pour definir quel segment on test:
 648  *             Nx --> Nsuiv si seg==1
 649  *             Nprec --> Nx si seg==0
 650  *
 651  * \return 1 si croisement, 0 sinon
 652  *
 653  * Version strict : n'autorise pas les triangles nulles
 654  * Version non optimisee car elle test systematiquement tout les segments du snake !
 655  */
 656 int test_croisement_move_seg_strict(struct snake_node *Nx, uint32 Nxi, uint32 Nxj, int seg)
 657 {
 658   uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
 659   uint32 posi, posj, suivi, suivj ; /* segment courant de test */
 660   struct snake_node *node, *end ;
 661
 662   /* segment de reference */
 663   if (seg)
 664     {
 665       Nrefi = Nx->noeud_suiv->posi ;
 666       Nrefj = Nx->noeud_suiv->posj ;
 667     }
 668   else
 669     {
 670       Nrefi = Nx->noeud_prec->posi ;
 671       Nrefj = Nx->noeud_prec->posj ;
 672     }
 673
 674   /* segments de tests */
 675   node = Nx->noeud_suiv ;
 676   suivi = node->posi ;
 677   suivj = node->posj ;
 678
 679   if (seg)
 680     {
 681       /* premier segment : il touche le segment de ref */
 682       /* pour Nx --> Nsuiv(ref) */
 683       posi = suivi ;
 684       posj = suivj ;
 685       node = node->noeud_suiv ;
 686       suivi = node->posi ;
 687       suivj = node->posj ;
 688       if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj,posi,posj,suivi,suivj))
 689         return 1 ;
 690
 691       end = Nx->noeud_prec ; /* pour boucle while */
 692    }
 693   else
 694     /* pour Nprec --> Nx */
 695     end = Nx->noeud_prec->noeud_prec ; /* pour boucle while */
 696
 697   /* boucle sur les segments */
 698   while (node != end)
 699   {
 700     posi = suivi ;
 701     posj = suivj ;
 702     node = node->noeud_suiv ;
 703     suivi = node->posi ;
 704     suivj = node->posj ;
 705     if (test_croisement_segment_strict(posi,posj,suivi,suivj,Nxi,Nxj,Nrefi,Nrefj))
 706       return 1 ;
 707   }
 708
 709   /* dernier segment */
 710   /* cas Nprec --> Nx */
 711   if (!seg)
 712     {
 713       posi = suivi ;
 714       posj = suivj ;
 715       node = node->noeud_suiv ;
 716       suivi = node->posi ;
 717       suivj = node->posj ;
 718       if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
 719         return 1 ;
 720     }
 721   return 0 ;
 722 }
 723