home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 3 / 3406 / pix.c < prev    next >
C/C++ Source or Header  |  1991-05-23  |  6KB  |  256 lines
  1.  
  2. /* This module keeps track of which pixels are calculated and which are
  3.  * not. It then returns the next pixel to start from, which is
  4.  * guaranteed to be in upper edge of an area.
  5.  * The algorithm used here depends on that the chain of pixels relayed
  6.  * to it 1) goes clockwise and 2) follows the boundary of the area 
  7.  * (That is, no peaks to the inside) (That would be stupid anyways)
  8.  */
  9.  
  10. /* In case you are interested, the changes in the "calculated-or-not"
  11.  * status (off-to-on and on-to-off) are stored in a column by column
  12.  * basis in a dynamically allocated structure.
  13.  */
  14.  
  15. /* NOTE: This module is used both by the sender and the receiver, since
  16.  * pixel position information are omitted; the receiver should
  17.  * reconstruct it using this package.
  18.  * (unless FAST-flag is used)
  19.  
  20.  * void initialize(int nx, int ny);
  21.  * void deinit(void);
  22.  * int first_point(int *nx, int *ny);
  23.  * void next_point(int dir);
  24.  
  25.  */
  26.  
  27. #include <stdio.h>
  28. #include "mb.h"
  29.  
  30. #undef DEBUG
  31.  
  32. #define DEFSIZE 8
  33. typedef struct {
  34.   int *ch;
  35.   int size;
  36.   } pixline;
  37. static pixline *pix;
  38. static int px, py;
  39. static int xsize, ysize;
  40. static int firstdir, prevdir;
  41. #define NONE -1
  42. #define FIRSTP 0
  43. #define NEXTP 1
  44. static int prevcall;
  45. static int firstx, lastx;
  46.  
  47. #define NOP 0
  48. #define ON 1
  49. #define OFF 2
  50. /* The need for on-to-off or off-to-on -transitions is determined 
  51.  * entirely by previous and current direction. */
  52. static int dir_code[4][4]= {
  53.   {NOP, ON,     ON,  NOP},
  54.   {NOP, ON,     ON,  ON|OFF},
  55.   {OFF, NOP,    NOP, OFF},
  56.   {OFF, ON|OFF, NOP, OFF}};
  57.  
  58.  
  59. /* dynamically allocate array */
  60. void initialize(nx, ny)
  61. int nx, ny;
  62. {
  63. int x;
  64. xsize= nx; ysize= ny;
  65. pix= (pixline *)malloc(xsize * sizeof(pixline));
  66. for (x= 0; x < xsize; x++) {
  67.   pix[x].ch= (int *)malloc(DEFSIZE * sizeof(int));
  68.   pix[x].size= DEFSIZE;
  69.   }
  70. for (x= 0; x < xsize; x++) {
  71.   pix[x].ch[0]= 0; /* first on-to-off transition */
  72.   pix[x].ch[1]= -1; /* end of pixline */
  73.   }
  74. prevcall= NONE;
  75. }
  76.  
  77.  
  78. /* free it as needed */
  79. void deinit()
  80. {
  81. int x;
  82. for (x= 0; x < xsize; x++) 
  83.   free(pix[x].ch);
  84. free(pix);
  85. }
  86.  
  87.  
  88. /* return next starting point for the crawling algorithm (or 0) */ 
  89. int first_point(nx, ny)
  90. int *nx, *ny;
  91. {
  92. int x, y1, y2;
  93. void next_point();
  94.  
  95. /* There are at least two special cases to be considered.
  96.  * 1) If first_point() is called two times in a row (that is, no
  97.  * next_point() in between) that means that the previous area
  98.  * consisted only of one single point. This is easily fixed by
  99.  * feeding next_point() some false input.
  100.  */
  101. if (prevcall == FIRSTP) {
  102.   prevdir= RIGHT;
  103.   next_point(LEFT);
  104.   }
  105. /* 2) Assume next_point() has been called. The first direction in the
  106.  * chain had to be wrapped to the end, because it's predecessor
  107.  * of all pixels has to be known. Now handle that first dir.
  108.  */
  109. else if (prevcall == NEXTP)
  110.   next_point(firstdir);
  111.  
  112. prevcall= FIRSTP; /* Now it is us that was the previously called one */
  113.  
  114. /* first remove redundancy from the pix array (that is, if in the
  115.  * same pixel position is both on-to-off and off-to-on -transition,
  116.  * discard both. */
  117. #ifdef DEBUG
  118. printf ("--------------------------------------\ncombining...\n");
  119. #endif
  120. for (x= firstx; x <= lastx; x++) {
  121. #ifdef DEBUG
  122. if (pix[x].ch[0] != 0 || pix[x].ch[1] != -1) {
  123.   int y;
  124.   printf ("Line %d (len %d):",x, pix[x].size);
  125.   for (y= 0; ; y++) {
  126.     printf ("%d ", pix[x].ch[y]);
  127.     if (pix[x].ch[y] < 0)
  128.       break;
  129.     }
  130.   printf ("\n");
  131.   }
  132. #endif
  133.   for (y1= y2= 0; ; y1++, y2++) {
  134.     while (pix[x].ch[y1] >= 0 &&
  135.            pix[x].ch[y1] == pix[x].ch[y1+1])
  136.              y1 += 2;
  137.     pix[x].ch[y2]= pix[x].ch[y1];
  138.     if (pix[x].ch[y1] < 0) break;
  139.     }
  140. #ifdef DEBUG
  141. if (pix[x].ch[0] != 0 || pix[x].ch[1] != -1) {
  142.   int y;
  143.   printf ("Line %d (len %d):",x, pix[x].size);
  144.   for (y= 0; ; y++) {
  145.     printf ("%d ", pix[x].ch[y]);
  146.     if (pix[x].ch[y] < 0)
  147.       break;
  148.     }
  149.   printf ("\n");
  150.   }
  151. #endif
  152.   }
  153.  
  154. px= 0; py= pix[0].ch[0];
  155. for (x= 1; x < xsize; x++)
  156.   if (pix[x].ch[0] < py) {
  157.     py= pix[x].ch[0];
  158.     px= x;
  159.     }
  160. *nx= px; *ny= py;
  161. firstx= xsize; lastx= 0;
  162. prevdir= NODIR;
  163. if (py >= ysize) return(0);
  164. return(1);
  165. }
  166.  
  167.  
  168. void next_point(dir)
  169. int dir;
  170. {
  171. int y;
  172. int code;
  173. if (prevdir == NODIR) {
  174.   /* This is the first dir in the chain. Because we do not
  175.    * know the previous dir, wrap this one to the end of the chain,
  176.    * since then we do know it. */
  177.   code= NOP;
  178.   firstdir= dir;
  179.   }
  180. else
  181.   code= dir_code[prevdir][dir];
  182.  
  183. #ifdef DEBUG
  184. printf ("prev= %d dir= %d -> %d\n", prevdir, dir, code);
  185. printf ("Line %d (len %d):",px, pix[px].size);
  186. for (y= 0; ; y++) {
  187.   printf ("%d ", pix[px].ch[y]);
  188.   if (pix[px].ch[y] < 0)
  189.     break;
  190.   }
  191. printf ("\n");
  192. #endif
  193.  
  194. /* Optimize a little.. keep track of which lines need to be rearranged
  195.  */
  196. if (px < firstx) firstx= px;
  197. if (px > lastx) lastx= px;
  198.  
  199. /* Store on-to-off and off-to-on transitions in an uniform manner
  200.  * (The only exception is that on-to-off is stored one pixel below)
  201.  */
  202. if (code & ON) {
  203.   int tmp1= py, tmp2;
  204.   y= 0;
  205.   while (pix[px].ch[y] < tmp1 && pix[px].ch[y] >= 0)
  206.     y++;
  207.   while (tmp1 >= 0) {
  208.     tmp2= pix[px].ch[y];
  209.     pix[px].ch[y]= tmp1;
  210.     tmp1= tmp2;
  211.     y++;
  212.     }
  213.   if (y >= pix[px].size)
  214.     pix[px].ch= (int *)realloc(pix[px].ch,
  215.             (pix[px].size += DEFSIZE) * sizeof(int));
  216.   pix[px].ch[y]= tmp1; /* == -1 */
  217.   }
  218.  
  219. if (code & OFF) {
  220.   int tmp1= py+1, tmp2;
  221.   y= 0;
  222.   while (pix[px].ch[y] < tmp1 && pix[px].ch[y] >= 0)
  223.     y++;
  224.   while (tmp1 >= 0) {
  225.     tmp2= pix[px].ch[y];
  226.     pix[px].ch[y]= tmp1;
  227.     tmp1= tmp2;
  228.     y++;
  229.     }
  230.   if (y >= pix[px].size)
  231.     pix[px].ch= (int *)realloc(pix[px].ch,
  232.             (pix[px].size += DEFSIZE) * sizeof(int));
  233.   pix[px].ch[y]= tmp1; /* == -1 */
  234.   }
  235.  
  236. #ifdef DEBUG
  237. printf ("Line %d (len %d):",px, pix[px].size);
  238. for (y= 0; ; y++) {
  239.   printf ("%d ", pix[px].ch[y]);
  240.   if (pix[px].ch[y] < 0)
  241.     break;
  242.   }
  243. printf ("\n\n");
  244. #endif
  245.  
  246. switch (dir) {
  247.   case UP:    py--; break;
  248.   case DOWN:  py++; break;
  249.   case LEFT:  px--; break;
  250.   case RIGHT: px++; break;
  251.   }
  252. prevdir= dir;
  253. prevcall= NEXTP;
  254. }
  255.  
  256.