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   do
 207     {
 208       i1 = np->posi ; j1 = np->posj ;
 209       i2 = npp1->posi ; j2 = npp1->posj ;
 210
 211       nb_pixel_segment = calcul_liste_pixel_segment(i1,j1,i2,j2, liste_pixel_segment, 0) ;
 212       for (n=1; n<nb_pixel_segment-1; n++)
 213                 image[liste_pixel_segment[2*n]][liste_pixel_segment[2*n+1]] = valseg ;
 214
 215       np = npp1 ;
 216       npp1 = np->noeud_suiv ;
 217     }
 218   while (np != snake) ;
 219
 220   /* les deux noeuds */
 221   np = snake ;
 222   npp1 = snake->noeud_suiv ;
 223   do
 224     {
 225       i1 = np->posi ; j1 = np->posj ;
 226       i2 = npp1->posi ; j2 = npp1->posj ;
 227
 228       image[i1][j1] = valnoeud ;
 229       image[i2][j2] = valnoeud ;
 230
 231       np = npp1 ;
 232       npp1 = np->noeud_suiv ;
 233     }
 234   while (np != snake) ;
 235 }
 236
 237 /* ========== DEBUG ================= */
 238 /* fonction d'affichage pour le debug */
 239 /* affiche les deux premiers segments avec valseg-1 */
 240 /* et incremenent les valeurs des noeuds */
 241 void affiche_snake_couleur(int **image, struct snake_node *snake, int valseg, int valnoeud,
 242                            uint32 *liste_pixel_segment)
 243 {
 244   uint32 i1, j1, i2, j2 ;
 245   uint32 n, nb_pixel_segment ;
 246   struct snake_node *np, *npp1 ;
 247   int cpt = 0;
 248   snake = snake->noeud_prec ;
 249
 250   /* les segments */
 251   np = snake ;
 252   npp1 = np->noeud_suiv ;
 253   do
 254     {
 255       i1 = np->posi ; j1 = np->posj ;
 256       i2 = npp1->posi ; j2 = npp1->posj ;
 257
 258       nb_pixel_segment = calcul_liste_pixel_segment(i1,j1,i2,j2, liste_pixel_segment, 0) ;
 259       if (cpt < 2 )
 260         for (n=1; n<nb_pixel_segment-1; n++)
 261           image[liste_pixel_segment[2*n]][liste_pixel_segment[2*n+1]] = valseg-1 ;
 262       else
 263         for (n=1; n<nb_pixel_segment-1; n++)
 264           image[liste_pixel_segment[2*n]][liste_pixel_segment[2*n+1]] = valseg ;
 265
 266       cpt++ ;
 267       np = npp1 ;
 268       npp1 = np->noeud_suiv ;
 269     }
 270   while (np != snake) ;
 271
 272   /* les deux noeuds */
 273   cpt = 0 ;
 274   np = snake ;
 275   npp1 = snake->noeud_suiv ;
 276   do
 277     {
 278       i1 = np->posi ; j1 = np->posj ;
 279       i2 = npp1->posi ; j2 = npp1->posj ;
 280
 281       image[i1][j1] = valnoeud+cpt ;
 282       image[i2][j2] = valnoeud+cpt++ ;
 283
 284       np = npp1 ;
 285       npp1 = np->noeud_suiv ;
 286     }
 287   while (np != snake) ;
 288 }
 289
 290 /* ========= DEBUG ===================== */
 291 /* copie l'image du snake avec un numero */
 292 /* de fichier incremente a chaque appel */
 293 void debug_aff_snake(struct snake_node *snake)
 294 {
 295   const int idim=256, jdim=256 ;
 296
 297   int **image = new_matrix_int(idim, jdim) ;
 298   uint32 *liste_pixel = malloc(sizeof(int)*2*(idim+jdim)) ;
 299   static int iter=0 ;
 300   char output[256] ;
 301   int n;
 302
 303   for (n=0; n<idim*jdim; n++)
 304     image[0][n] = 128 ;
 305
 306   affiche_snake_couleur(image, snake, 255, 0, liste_pixel) ;
 307   sprintf(output, "debug_im%.4d.pgm", iter++) ;
 308   write_int2pgm(image, idim, idim, output, 0) ;
 309
 310   del_matrix_int(image, idim);
 311   free(liste_pixel);
 312 }
 313
 314
 315
 316
 317 /**
 318  * \fn int ajout_noeud_snake(struct snake_node *node, int *nb_noeud)
 319  * \brief ajout un noeud au snake
 320  * \author NB - PhyTI
 321  *
 322  * \param[in]  node adresse du noeud
 323  * \param[out] nb_noeud nombre de noeuds du snake
 324  *
 325  * \return le pointeur du nouveau noeud si ajout reussi, NULL sinon
 326  *
 327  * Ajout d'un noeud au millieu du segment.
 328  * !!! Pour algo rapide, cette fonction doit etre suivie
 329  * d'une mise a jour des contrib des noeuds qui conviennent !!!
 330  *
 331  */
 332 struct snake_node* ajout_noeud_snake(struct snake_node *node, uint32 *nb_noeud)
 333 {
 334   struct snake_node *najout ;
 335
 336   najout = malloc(sizeof(struct snake_node)) ;
 337
 338   najout->posi = node->centre_i ;
 339   najout->posj = node->centre_j ;
 340
 341   najout->noeud_prec = node ;
 342   najout->noeud_suiv = node->noeud_suiv ;
 343   node->noeud_suiv->noeud_prec = najout ;
 344   node->noeud_suiv = najout ;
 345
 346   (*nb_noeud)++ ;
 347   return najout ;
 348 }
 349
 350
 351
 352
 353 /**
 354  * \fn inline int test_croisement_segment_large(int Ai, int Aj, int Bi, int Bj,
 355  *                                 int Ui, int Uj, int Vi, int Vj)
 356  *
 357  * \brief Test qui determine si deux segments croisent
 358  * \author NB - PhyTI
 359  *
 360  * \param[in] Ai
 361  * \param[in] Aj
 362  * \param[in] Bi
 363  * \param[in] Bj
 364  * \param[in] Ui
 365  * \param[in] Uj
 366  * \param[in] Vi
 367  * \param[in] Vj
 368  *
 369  * \return  1 si croisement, 0 sinon
 370  *
 371  * Version large : autorise les triangles nulles
 372  * Test de croisement des segments :
 373  * si deux segments AB et UV croisent, alors
 374  * les triangles ABU et ABV change d'ordre de rotation
 375  * ET
 376  * les triangles UVA et UVB change aussi d'ordre de rotation
 377  *
 378  */
 379 inline int test_croisement_segment_large(uint32 Ai, uint32 Aj, uint32 Bi, uint32 Bj,
 380                                    uint32 Ui, uint32 Uj, uint32 Vi, uint32 Vj)
 381 {
 382   if (sign_diff_strict(sinus_triangle(Ai, Aj, Bi, Bj, Ui, Uj),     // Bi-Ai, Uj-Aj, Ui-Ai, Bj-Aj
 383                        sinus_triangle(Ai, Aj, Bi, Bj, Vi, Vj)))    // Bi-Ai, Vj-Aj, Vi-Ai, Bj-Aj
 384     if (sign_diff_strict(sinus_triangle(Ui, Uj, Vi, Vj, Ai, Aj),   // Vi-Ui, Aj-Uj, Ai-Ui, Vj-Uj
 385                          sinus_triangle(Ui, Uj, Vi, Vj, Bi, Bj)))  // Vi-Ui, Bj-Uj, Bi-Ui, Vj-Uj
 386        return 1 ;
 387   return 0 ;
 388 }
 389
 390
 391 /**
 392  * \fn inline int test_croisement_segment_strict(int Ai, int Aj, int Bi, int Bj,
 393  *                                 int Ui, int Uj, int Vi, int Vj)
 394  *
 395  * \brief Test qui determine si deux segments croisent
 396  * \author NB - PhyTI
 397  *
 398  * \param[in] Ai
 399  * \param[in] Aj
 400  * \param[in] Bi
 401  * \param[in] Bj
 402  * \param[in] Ui
 403  * \param[in] Uj
 404  * \param[in] Vi
 405  * \param[in] Vj
 406  *
 407  * \return  1 si croisement, 0 sinon
 408  *
 409  * Version strict : n'autorise pas les triangles nulles
 410  * Test de croisement des segments :
 411  * si deux segments AB et UV croisent, alors
 412  * les triangles ABU et ABV change d'ordre de rotation
 413  * ET
 414  * les triangles UVA et UVB change aussi d'ordre de rotation
 415  *
 416  */
 417 inline int test_croisement_segment_strict(uint32 Ai, uint32 Aj, uint32 Bi, uint32 Bj,
 418                                    uint32 Ui, uint32 Uj, uint32 Vi, uint32 Vj)
 419 {
 420   if (sign_diff_ou_egal_zero(sinus_triangle(Ai, Aj, Bi, Bj, Ui, Uj),
 421                              sinus_triangle(Ai, Aj, Bi, Bj, Vi, Vj)))
 422     if (sign_diff_ou_egal_zero(sinus_triangle(Ui, Uj, Vi, Vj, Ai, Aj),
 423                                sinus_triangle(Ui, Uj, Vi, Vj, Bi, Bj)))
 424       return 1 ;
 425   return 0 ;
 426 }
 427
 428
 429
 430
 431
 432 /**
 433  * \fn int test_croisement_add_noeud_large(struct snake_node *N, int Nxi, int Nxj, int seg)
 434  *
 435  * \brief test si il y a croisement de segments lors de l'ajout d'un noeud
 436  * \author NB - PhyTI
 437  *
 438  * \param[in] N le noeud ou l'on veut ajouter un noeud Nx au milieu de son segment
 439  * \param[in] Nxi coordonnee i du nouveau node Nx
 440  * \param[in] Nxj coordonnee j du nouveau node Nx
 441  * \param[in] seg booleen pour definir quel segment on test:
 442  *             Nx --> Nsuiv si seg==1
 443  *             N --> Nx si seg==0
 444  *
 445  * \return 1 si croisement, 0 sinon
 446  *
 447  * Version large : autorise les triangles nulles
 448  *
 449  */
 450 int test_croisement_add_noeud_large(struct snake_node *N, uint32 Nxi, uint32 Nxj, int seg)
 451 {
 452   uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
 453   uint32 posi, posj, suivi, suivj ; /* segment courant de test */
 454   struct snake_node *node, *end ;
 455
 456   if (seg==1)
 457     {
 458       Nrefi = N->noeud_suiv->posi ;
 459       Nrefj = N->noeud_suiv->posj ;
 460     }
 461   else
 462     {
 463       Nrefi = N->posi ;
 464       Nrefj = N->posj ;
 465     }
 466
 467   node = N->noeud_suiv ;
 468   suivi = node->posi ;
 469   suivj = node->posj ;
 470
 471   end = N ;
 472   while (node != end)
 473   {
 474     posi = suivi ;
 475     posj = suivj ;
 476     node = node->noeud_suiv ;
 477     suivi = node->posi ;
 478     suivj = node->posj ;
 479     if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
 480       return 1 ;
 481   }
 482   return 0 ;
 483 }
 484
 485
 486
 487 /**
 488  * \fn int test_croisement_add_noeud_strict(struct snake_node *N, int Nxi, int Nxj, int seg)
 489  *
 490  * \brief test si il y a croisement de segments lors de l'ajout d'un noeud
 491  * \author NB - PhyTI
 492  *
 493  * \param[in] N le noeud ou l'on veut ajouter un noeud Nx au milieu de son segment
 494  * \param[in] Nxi coordonnee i du nouveau node Nx
 495  * \param[in] Nxj coordonnee j du nouveau node Nx
 496  * \param[in] seg booleen pour definir quel segment on test:
 497  *             Nx --> Nsuiv si seg==1
 498  *             N --> Nx si seg==0
 499  *
 500  * \return 1 si croisement, 0 sinon
 501  *
 502  * Version strict : n'autorise pas les triangles nulles
 503  *
 504  */
 505 int test_croisement_add_noeud_strict(struct snake_node *N, uint32 Nxi, uint32 Nxj, int seg)
 506 {
 507   uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
 508   uint32 posi, posj, suivi, suivj ; /* segment courant de test */
 509   struct snake_node *node, *end ;
 510
 511   /* segment de reference */
 512   if (seg)
 513     {
 514       Nrefi = N->noeud_suiv->posi ;
 515       Nrefj = N->noeud_suiv->posj ;
 516     }
 517   else
 518     {
 519       Nrefi = N->posi ;
 520       Nrefj = N->posj ;
 521     }
 522
 523   /* segments de tests */
 524   node = N->noeud_suiv ;
 525   suivi = node->posi ;
 526   suivj = node->posj ;
 527
 528   if (seg)
 529     {
 530       /* premier segment : il touche le segment de ref */
 531       /* pour Nx --> Nsuiv(ref) */
 532       posi = suivi ;
 533       posj = suivj ;
 534       node = node->noeud_suiv ;
 535       suivi = node->posi ;
 536       suivj = node->posj ;
 537       if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj,posi,posj,suivi,suivj))
 538         return 1 ;
 539       end = N ; /* pour boucle while */
 540    }
 541   else
 542     /* pour N --> Nx */
 543     end = N->noeud_prec ; /* pour boucle while */
 544
 545   /* boucle sur les segments */
 546   while (node != end)
 547   {
 548     posi = suivi ;
 549     posj = suivj ;
 550     node = node->noeud_suiv ;
 551     suivi = node->posi ;
 552     suivj = node->posj ;
 553     if (test_croisement_segment_strict(posi,posj,suivi,suivj,Nxi,Nxj,Nrefi,Nrefj))
 554       return 1 ;
 555   }
 556
 557   /* dernier segment */
 558   /* cas N --> Nx */
 559   if (!seg)
 560     {
 561       posi = suivi ;
 562       posj = suivj ;
 563       node = node->noeud_suiv ;
 564       suivi = node->posi ;
 565       suivj = node->posj ;
 566       if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
 567         return 1 ;
 568     }
 569   return 0 ;
 570 }
 571
 572
 573
 574
 575
 576
 577 /**
 578  * \fn int test_croisement_move_seg_large(struct snake_node *Nx, int Nxi, int Nxj, int seg)
 579  *
 580  * \brief test si il y a croisement de segments lors du deplacement d'un noeud
 581  * \author NB - PhyTI
 582  *
 583  * \param[in] Nx le noeud que l'on veut deplacer
 584  * \param[in] Nxi coordonnee i du nouveau node Nx
 585  * \param[in] Nxj coordonnee j du nouveau node Nx
 586  * \param[in] seg booleen pour definir quel segment on test:
 587  *             Nx --> Nsuiv si seg==1
 588  *             Nprec --> Nx si seg==0
 589  *
 590  * \return 1 si croisement, 0 sinon
 591  *
 592  * Version large : autorise les triangles nulles
 593  * Version non optimisee car elle test systematiquement tout les segments du snake !
 594  *
 595  */
 596 int test_croisement_move_seg_large(struct snake_node *Nx, uint32 Nxi, uint32 Nxj, int seg)
 597 {
 598   uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
 599   uint32 posi, posj, suivi, suivj ; /* segment courant de test */
 600   struct snake_node *node, *end ;
 601
 602   if (seg==1)
 603     {
 604       Nrefi = Nx->noeud_suiv->posi ;
 605       Nrefj = Nx->noeud_suiv->posj ;
 606     }
 607   else
 608     {
 609       Nrefi = Nx->noeud_prec->posi ;
 610       Nrefj = Nx->noeud_prec->posj ;
 611     }
 612
 613   node = Nx->noeud_suiv ;
 614   suivi = node->posi ;
 615   suivj = node->posj ;
 616
 617   end = Nx->noeud_prec ;
 618   while (node != end)
 619   {
 620     posi = suivi ;
 621     posj = suivj ;
 622     node = node->noeud_suiv ;
 623     suivi = node->posi ;
 624     suivj = node->posj ;
 625     if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
 626       return 1 ;
 627   }
 628   return 0 ;
 629 }
 630
 631
 632
 633 /**
 634  * \fn int test_croisement_move_seg_strict(struct snake_node *Nx, int Nxi, int Nxj, int seg)
 635  *
 636  * \brief test si il y a croisement de segments lors du deplacement d'un noeud
 637  * \author NB - PhyTI
 638  *
 639  * \param[in] Nx le noeud que l'on veut deplacer
 640  * \param[in] Nxi coordonnee i du nouveau node Nx
 641  * \param[in] Nxj coordonnee j du nouveau node Nx
 642  * \param[in] seg booleen pour definir quel segment on test:
 643  *             Nx --> Nsuiv si seg==1
 644  *             Nprec --> Nx si seg==0
 645  *
 646  * \return 1 si croisement, 0 sinon
 647  *
 648  * Version strict : n'autorise pas les triangles nulles
 649  * Version non optimisee car elle test systematiquement tout les segments du snake !
 650  */
 651 int test_croisement_move_seg_strict(struct snake_node *Nx, uint32 Nxi, uint32 Nxj, int seg)
 652 {
 653   uint32 Nrefi=0, Nrefj=0 ; /* reference avec Nxi et Nxj */
 654   uint32 posi, posj, suivi, suivj ; /* segment courant de test */
 655   struct snake_node *node, *end ;
 656
 657   /* segment de reference */
 658   if (seg)
 659     {
 660       Nrefi = Nx->noeud_suiv->posi ;
 661       Nrefj = Nx->noeud_suiv->posj ;
 662     }
 663   else
 664     {
 665       Nrefi = Nx->noeud_prec->posi ;
 666       Nrefj = Nx->noeud_prec->posj ;
 667     }
 668
 669   /* segments de tests */
 670   node = Nx->noeud_suiv ;
 671   suivi = node->posi ;
 672   suivj = node->posj ;
 673
 674   if (seg)
 675     {
 676       /* premier segment : il touche le segment de ref */
 677       /* pour Nx --> Nsuiv(ref) */
 678       posi = suivi ;
 679       posj = suivj ;
 680       node = node->noeud_suiv ;
 681       suivi = node->posi ;
 682       suivj = node->posj ;
 683       if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj,posi,posj,suivi,suivj))
 684         return 1 ;
 685
 686       end = Nx->noeud_prec ; /* pour boucle while */
 687    }
 688   else
 689     /* pour Nprec --> Nx */
 690     end = Nx->noeud_prec->noeud_prec ; /* pour boucle while */
 691
 692   /* boucle sur les segments */
 693   while (node != end)
 694   {
 695     posi = suivi ;
 696     posj = suivj ;
 697     node = node->noeud_suiv ;
 698     suivi = node->posi ;
 699     suivj = node->posj ;
 700     if (test_croisement_segment_strict(posi,posj,suivi,suivj,Nxi,Nxj,Nrefi,Nrefj))
 701       return 1 ;
 702   }
 703
 704   /* dernier segment */
 705   /* cas Nprec --> Nx */
 706   if (!seg)
 707     {
 708       posi = suivi ;
 709       posj = suivj ;
 710       node = node->noeud_suiv ;
 711       suivi = node->posi ;
 712       suivj = node->posj ;
 713       if (test_croisement_segment_large(Nxi,Nxj,Nrefi,Nrefj, posi,posj,suivi,suivj))
 714         return 1 ;
 715     }
 716   return 0 ;
 717 }
 718