src/lib_contour.c

   1 /**
   2  * \file lib_contour.c
   3  * \brief routines pour la gestion des contours polygonaux
   4  * \author NB - PhyTI
   5  * \version x.x
   6  * \date 24 decembre 2009
   7  *
   8  */
   9
  10 #include "lib_contour.h"
  11
  12
  13
  14 /**
  15  * \fn int calcul_liste_pixel_segment(int y1,int x1,int y2,int x2,
  16  *                            int *liste_pixel_segment, int ind_offset=0)
  17  *
  18  * \brief calcul la liste des pixels du segment entre 2 noeuds
  19  * \author FG - PhyTI (mars 2007), modifiee NB - PhyTI
  20  *
  21  * \param[in] y1 coordonnee du point P1 (equiv i1)
  22  * \param[in] x1 coordonnee du point P1 (equiv j1)
  23  * \param[in] y2 coordonnee du point P2 (equiv i2)
  24  * \param[in] x2 coordonnee du point P2 (equiv j2)
  25  * \param[out] liste_pixel_segment coordonnees des pixels [i j i j i j ...]
  26  * \param[in] ind_offset decalage de la position origine dans la liste
  27  *
  28  * \return nb_pixel_segment, la dimension de la liste en nombre de coord (i,j)
  29  *
  30  * donne la liste des pixels d'un segment [P1 -> P2]
  31  * Utilise l'algo de Bresenham en version int (recupere sur Wikipedia)
  32  *
  33  */
  34 uint32 calcul_liste_pixel_segment(uint32 y1,uint32 x1,uint32 y2,uint32 x2, uint32 *liste_pixel_segment, int ind_offset)
  35 {
  36   int dx, dy ;
  37   int e ;
  38   uint32 *liste ;
  39
  40   liste = liste_pixel_segment + ind_offset ;
  41
  42   if ( (dx=x2-x1) != 0)
  43     {
  44       if ( dx > 0 )
  45         {
  46           if ( (dy=y2-y1) != 0 )
  47             {
  48               if ( dy > 0 )
  49                 {
  50                   // vecteur oblique dans le 1er quadran
  51                   if ( dx >= dy )
  52                     {
  53                       // vecteur diagonal ou oblique proche de l'horizontale, dans le 1er octant
  54                       dx = (e=dx) * 2 ; dy = dy * 2 ;  // e est positif
  55                       while( x1!=x2 ) //boucler sans fin: deplacements horizontaux
  56                         {
  57                           *liste++=y1;
  58                           *liste++=x1;
  59
  60                           x1++;
  61                           if ( (e-=dy) < 0 )
  62                             {
  63                               y1++ ;  // deplacement diagonal
  64                               e += dx ;
  65                             }
  66                         }
  67                     }
  68                   else
  69                     {
  70                       // vecteur oblique proche de la verticale, dans le 2nd octant
  71                       dy = (e=dy) * 2 ; dx = dx * 2 ;  // e est positif
  72                       while ( y1 != y2 ) //boucler sans fin: deplacements verticaux
  73                         {
  74                           *liste++=y1;
  75                           *liste++=x1;
  76                           y1 += 1 ;
  77                           if ( (e -= dx) < 0 )
  78                             {
  79                               x1++ ;  // deplacement diagonal
  80                               e += dy ;
  81                             }
  82                         }
  83                     }
  84                 }
  85               else // dy < 0 (et dx > 0)
  86                 {
  87                   // vecteur oblique dans le 4e cadran
  88                   if ( dx >= -dy )
  89                     {
  90                       // vecteur diagonal ou oblique proche de l'horizontale, dans le 8e octant
  91                       dx = (e=dx) * 2 ; dy = dy * 2 ;  // e est positif
  92                       while ( x1 != x2 ) //boucler sans fin  // deplacements horizontaux
  93                         {
  94                           *liste++=y1;
  95                           *liste++=x1;
  96                           x1 ++;
  97                           if ( (e += dy) < 0 )
  98                             {
  99                               y1--;  // deplacement diagonal
 100                               e += dx ;
 101                             }
 102                         }
 103                     }
 104                   else // vecteur oblique proche de la verticale, dans le 7e octant
 105                     {
 106                       dy = (e=dy) * 2 ; dx = dx * 2 ;  // e est negatif
 107                       while ( y1 != y2 ) // boucler sans fin: deplacements verticaux
 108                         {
 109                           *liste++=y1;
 110                           *liste++=x1;
 111                           y1--;
 112                           if ( (e += dx) > 0 )
 113                             {
 114                               x1 ++;  // deplacement diagonal
 115                               e += dy ;
 116                             }
 117                         }
 118                     }
 119                 }
 120             }
 121           else // dy = 0 (et dx > 0)
 122             {
 123               // vecteur horizontal vers la droite
 124               while ( x1 != x2 )
 125                 {
 126                   *liste++=y1;
 127                   *liste++=x1;
 128                   x1++ ;
 129                 }
 130             }
 131         }
 132       else
 133         {
 134           // dx < 0
 135           if ( (dy=y2-y1) != 0 )
 136             {
 137               if ( dy > 0 )
 138                 {
 139                   // vecteur oblique dans le 2nd quadran
 140                   if ( -dx >= dy )
 141                     {
 142                       // vecteur diagonal ou oblique proche de l'horizontale, dans le 4e octant
 143                       dx = (e=dx) * 2 ; dy = dy * 2 ;  // e est negatif
 144                       while ( x1 != x2 ) //boucler sans fin  // deplacements horizontaux
 145                         {
 146                           *liste++=y1;
 147                           *liste++=x1;
 148                           x1 -- ;
 149                           if ( (e += dy) >= 0 )
 150                             {
 151                               y1++ ;  // deplacement diagonal
 152                               e += dx ;
 153                             }
 154                         }
 155                     }
 156                   else
 157                     {
 158                       // vecteur oblique proche de la verticale, dans le 3e octant
 159                       dy = (e=dy) * 2 ; dx = dx * 2 ;  // e est positif
 160                       while ( y1 != y2 ) //boucler sans fin  // deplacements verticaux
 161                         {
 162                           *liste++=y1;
 163                           *liste++=x1;
 164                           y1++ ;
 165                           if ( (e += dx) <= 0 )
 166                             {
 167                               x1--;  // depacement diagonal
 168                               e += dy ;
 169                             }
 170                         }
 171                     }
 172                 }
 173
 174               else  // dy < 0 (et dx < 0)
 175                 {
 176                   // vecteur oblique dans le 3e cadran
 177                   if ( dx <= dy )
 178                     {
 179                       // vecteur diagonal ou oblique proche de l'horizontale, dans le 5e octant
 180                       dx = (e=dx) * 2 ; dy = dy * 2 ;  // e est negatif
 181                       while ( x1 != x2 ) //boucler sans fin  // deplacements horizontaux
 182                         {
 183                           *liste++=y1;
 184                           *liste++=x1;
 185                           x1 -- ;
 186                           if ( (e -= dy) >= 0 )
 187                             {
 188                               y1-- ;  // deplacement diagonal
 189                               e += dx ;
 190                             }
 191                         }
 192                     }
 193                   else
 194                     {
 195                       // vecteur oblique proche de la verticale, dans le 6e octant
 196                       dy = (e=dy) * 2 ; dx = dx * 2 ;  // e est negatif
 197                       while ( y1 != y2 ) //boucler sans fin  // deplacements verticaux
 198                         {
 199                           *liste++=y1;
 200                           *liste++=x1;
 201                           y1-- ;
 202                           if ( (e-=dx) >= 0 )
 203                             {
 204                               x1 --;  // deplacement diagonal
 205                               e += dy ;
 206                             }
 207                         }
 208                     }
 209                 }
 210             }
 211           else // dy = 0 (et dx < 0)
 212             {
 213               // vecteur horizontal vers la gauche
 214               while ( x1 != x2 )
 215                 {
 216                   *liste++=y1;
 217                   *liste++=x1;
 218                   x1 -- ;
 219                 }
 220             }
 221         }
 222     }
 223   else // dx = 0
 224     {
 225       if ( (dy=y2-y1) != 0 )
 226         {
 227           if ( dy > 0 )
 228             {
 229               // vecteur vertical croissant
 230               while ( y1 != y2 )
 231                 {
 232                   *liste++=y1;
 233                   *liste++=x1;
 234                   y1 ++ ;
 235                 }
 236             }
 237           else // dy < 0 (et dx = 0)
 238             {
 239               // vecteur vertical décroissant
 240               while ( y1 != y2 )
 241                 {
 242                   *liste++=y1;
 243                   *liste++=x1;
 244                   y1 -- ;
 245               }
 246             }
 247         }
 248     }
 249
 250   *liste++=y2;
 251   *liste++=x2;
 252
 253   return (uint32)(liste-liste_pixel_segment)/2;
 254 }