home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / LIBIMAGE / DRAW.C next >
Encoding:
C/C++ Source or Header  |  1999-09-11  |  28.2 KB  |  1,195 lines
  1. /* 
  2.  * draw.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1999 SOS Software
  7.  */
  8.  
  9. #include "draw.h"
  10. #include "mtables.c"
  11.  
  12. #define ERRORMEM(arg1) {fprintf (stderr,"%s: not enough memory -- sorry\n", arg1);exit (1);}
  13. #define    SIGN(a)        ( ((a) == 0.0) ? 0 : ( ((a) < 0.0) ? -1 : 1 ) )
  14. #define F_TO_INT(x)     ( ((x)-(int)(x)<0.5) ? (int)(x) : (int)(x)+1 )
  15. #define    CS30        0.8660254
  16.  
  17.  
  18. /*
  19.  * draw_line()
  20.  *   DESCRIPTION:
  21.  *     draw_line draws a line from point (x1,y1) to (x2,y2) using Bresenham's algorithm.
  22.  *   ARGUMENTS:
  23.  *     x1, y1, x2, y2(int) start and end points of line
  24.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  25.  *     value(int) pixel value to use for line
  26.  *   RETURN VALUE:
  27.  *     none
  28.  */
  29. void
  30. draw_line (int x1, int y1, int x2, int y2, Image * imgIO, int value)
  31. {
  32.   int x = x1;
  33.   int y = y1;
  34.   int D = 0;
  35.   int dx = x2 - x1;
  36.   int dy = y2 - y1;
  37.   int c;
  38.   int M;
  39.   int xinc = 1;
  40.   int yinc = 1;
  41.  
  42.   if (dx < 0) {
  43.     xinc = -1;
  44.     dx = -dx;
  45.   }
  46.   if (dy < 0) {
  47.     yinc = -1;
  48.     dy = -dy;
  49.   }
  50.   if (dy < dx) {
  51.     c = 2 * dx;
  52.     M = 2 * dy;
  53.     while (x != x2) {
  54.       setpixel (x, y, imgIO, value);
  55.       x += xinc;
  56.       D += M;
  57.       if (D > dx) {
  58.         y += yinc;
  59.         D -= c;
  60.       }
  61.     }
  62.   }
  63.   else {
  64.     c = 2 * dy;
  65.     M = 2 * dx;
  66.     while (y != y2) {
  67.       setpixel (x, y, imgIO, value);
  68.       y += yinc;
  69.       D += M;
  70.       if (D > dy) {
  71.         x += xinc;
  72.         D -= c;
  73.       }
  74.     }
  75.   }
  76. }
  77.  
  78. /*
  79.  * draw_circle()
  80.  *   DESCRIPTION:
  81.  *     draw_circle draws a circle specified by a center point and radius.
  82.  *   ARGUMENTS:
  83.  *     xC, yC(int) center point of circle
  84.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  85.  *     value(int) pixel value to use for circle
  86.  *   RETURN VALUE:
  87.  *     none
  88.  */
  89. void
  90. draw_circle (int xC, int yC, int R, Image * imgIO, int value)
  91. {
  92.   int x = 0;
  93.   int y = R;
  94.   int u = 1;
  95.   int v = 2 * R - 1;
  96.   int E = 0;
  97.  
  98.   setpixel (xC, yC + R, imgIO, value);
  99.   setpixel (xC, yC - R, imgIO, value);
  100.   setpixel (xC + R, yC, imgIO, value);
  101.   setpixel (xC - R, yC, imgIO, value);
  102.  
  103.   while (x < y) {
  104.     x++;
  105.     E += u;
  106.     u += 2;
  107.     if (v < 2 * E) {
  108.       y--;
  109.       E -= v;
  110.       v -= 2;
  111.     }
  112.     if (x <= y) {
  113.       setpixel (xC + x, yC + y, imgIO, value);
  114.       setpixel (xC - x, yC + y, imgIO, value);
  115.       setpixel (xC + x, yC - y, imgIO, value);
  116.       setpixel (xC - x, yC - y, imgIO, value);
  117.       if (x < y) {
  118.         setpixel (xC + y, yC + x, imgIO, value);
  119.         setpixel (xC - y, yC + x, imgIO, value);
  120.         setpixel (xC + y, yC - x, imgIO, value);
  121.         setpixel (xC - y, yC - x, imgIO, value);
  122.       }
  123.     }
  124.   }
  125. }
  126. /*
  127.  * draw_filled_circle()
  128.  *   DESCRIPTION:
  129.  *     draw_circle draws a circle specified by a center point and radius.
  130.  *     fills the circle with value
  131.  *   ARGUMENTS:
  132.  *     xC, yC(int) center point of circle
  133.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  134.  *     value(int) pixel value to use for circle
  135.  *   RETURN VALUE:
  136.  *     none
  137.  */
  138. void
  139. draw_filled_circle (int xC, int yC, int R, Image * imgIO, int value)
  140. {
  141.   int x = 0;
  142.   int y = R;
  143.   int u = 1;
  144.   int v = 2 * R - 1;
  145.   int E = 0;
  146.  
  147.   draw_line (xC, yC + R, xC, yC - R, imgIO, value);
  148.   draw_line (xC + R, yC, xC - R, yC, imgIO, value);
  149.  
  150.   while (x < y) {
  151.     x++;
  152.     E += u;
  153.     u += 2;
  154.     if (v < 2 * E) {
  155.       y--;
  156.       E -= v;
  157.       v -= 2;
  158.     }
  159.     if (x <= y) {
  160.       draw_line (xC + x, yC + y, xC + x, yC - y, imgIO, value);
  161.       draw_line (xC - x, yC + y, xC - x, yC - y, imgIO, value);
  162.       if (x < y) {
  163.         draw_line (xC + y, yC + x, xC - y, yC + x, imgIO, value);
  164.         draw_line (xC + y, yC - x, xC - y, yC - x, imgIO, value);
  165.       }
  166.     }
  167.   }
  168. }
  169. /*
  170.  * NOTE:  The functions
  171.  * gdImageCharUp
  172.  * gdImageCharUp
  173.  * gdImageString
  174.  * gdImageStringUp
  175.  * draw_ellipse
  176.  * gdImageFill
  177.  * gdImageFillToBorder
  178.  * are taken from the gd library and used with permission
  179.  * from T. Boutell
  180.  * * */
  181.  
  182. /*
  183.  * gdImageChar()
  184.  *   DESCRIPTION:
  185.  *     gdImageChar draws a character at the specified point using the specified font.
  186.  *   ARGUMENTS:
  187.  *     f(gdFontPtr) pointer to the font (see gd.h)
  188.  *     x, y(int) point of origin for character
  189.  *     c(int) character to draw
  190.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  191.  *     value(int) pixel value to use for character
  192.  *   RETURN VALUE:
  193.  *     none
  194.  */
  195. void
  196. gdImageChar (gdFontPtr f, int x, int y, int c, Image * imgIO, int value)
  197. {
  198.   int cx, cy;
  199.   int px, py;
  200.   int fline;
  201.   cx = 0;
  202.   cy = 0;
  203.   if ((c < f->offset) || (c >= (f->offset + f->nchars))) {
  204.     return;
  205.   }
  206.   fline = (c - f->offset) * f->h * f->w;
  207.   for (py = y; (py < (y + f->h)); py++) {
  208.     for (px = x; (px < (x + f->w)); px++) {
  209.       if (f->data[fline + cy * f->w + cx]) {
  210.         setpixel (px, py, imgIO, value);
  211.       }
  212.       cx++;
  213.     }
  214.     cx = 0;
  215.     cy++;
  216.   }
  217. }
  218.  
  219. /*
  220.  * gdImageCharUp()
  221.  *   DESCRIPTION:
  222.  *     gdImageCharUp draws a character at the specified point using the specified font
  223.  *     rotated 90 degrees.
  224.  *   ARGUMENTS:
  225.  *     f(gdFontPtr) pointer to the font (see gd.h)
  226.  *     x, y(int) point of origin for character
  227.  *     c(int) character to draw
  228.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  229.  *     value(int) pixel value to use for character
  230.  *   RETURN VALUE:
  231.  *     none
  232.  */
  233. void
  234. gdImageCharUp (gdFontPtr f, int x, int y, char c, Image * imgIO, int value)
  235. {
  236.   int cx, cy;
  237.   int px, py;
  238.   int fline;
  239.   cx = 0;
  240.   cy = 0;
  241.   if ((c < f->offset) || (c >= (f->offset + f->nchars))) {
  242.     return;
  243.   }
  244.   fline = (c - f->offset) * f->h * f->w;
  245.   for (py = y; (py > (y - f->w)); py--) {
  246.     for (px = x; (px < (x + f->h)); px++) {
  247.       if (f->data[fline + cy * f->w + cx]) {
  248.         setpixel (px, py, imgIO, value);
  249.       }
  250.       cy++;
  251.     }
  252.     cy = 0;
  253.     cx++;
  254.   }
  255. }
  256.  
  257. /*
  258.  * gdImageString()
  259.  *   DESCRIPTION:
  260.  *     gdImageCharUp draws a string at the specified point using the specified font.
  261.  *   ARGUMENTS:
  262.  *     f(gdFontPtr) pointer to the font (see gd.h)
  263.  *     x, y(int) point of origin for character
  264.  *     c(char *) string to draw
  265.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  266.  *     value(int) pixel value to use for character
  267.  *   RETURN VALUE:
  268.  *     none
  269.  */
  270. void
  271. gdImageString (gdFontPtr f, int x, int y, char *s, Image * imgIO, int value)
  272. {
  273.   int i;
  274.   int l;
  275.   l = strlen (s);
  276.   for (i = 0; (i < l); i++) {
  277.     gdImageChar (f, x, y, s[i], imgIO, value);
  278.     x += f->w;
  279.   }
  280. }
  281.  
  282. /*
  283.  * gdImageStringUp()
  284.  *   DESCRIPTION:
  285.  *     gdImageStringUp draws a string at the specified point using the specified font
  286.  *     rotated 90 degrees.
  287.  *   ARGUMENTS:
  288.  *     f(gdFontPtr) pointer to the font (see gd.h)
  289.  *     x, y(int) point of origin for character
  290.  *     c(char *) string to draw
  291.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  292.  *     value(int) pixel value to use for character
  293.  *   RETURN VALUE:
  294.  *     none
  295.  */
  296. void
  297. gdImageStringUp (gdFontPtr f, int x, int y, char *s, Image * imgIO, int value)
  298. {
  299.   int i;
  300.   int l;
  301.   l = strlen (s);
  302.   for (i = 0; (i < l); i++) {
  303.     gdImageCharUp (f, x, y, s[i], imgIO, value);
  304.     y -= f->w;
  305.   }
  306. }
  307.  
  308. /*
  309.  * draw_ellipse()
  310.  *   DESCRIPTION:
  311.  *     draw_ellipse draws an ellipse.
  312.  *   ARGUMENTS:
  313.  *     cx, cy(int) point of origin for ellipse
  314.  *     w, h(int) width and height for ellipse
  315.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  316.  *     value(int) pixel value to use for character
  317.  *   RETURN VALUE:
  318.  *     none
  319.  */
  320.  
  321. void
  322. draw_ellipse (int cx, int cy, int w, int h, Image * imgIO, int value)
  323. {
  324.   int i;
  325.   int lx = 0, ly = 0;
  326.   int w2, h2;
  327.   w2 = w / 2;
  328.   h2 = h / 2;
  329.   for (i = 0; (i <= 360); i++) {
  330.     int x, y;
  331.     x = ((long) cost[i % 360] * (long) w2 / costScale) + cx;
  332.     y = ((long) sint[i % 360] * (long) h2 / sintScale) + cy;
  333.     if (i) {
  334.       draw_line (lx, ly, x, y, imgIO, value);
  335.     }
  336.     lx = x;
  337.     ly = y;
  338.   }
  339. }
  340.  
  341. /*
  342.  * gdImageFillToBorder()
  343.  *   DESCRIPTION:
  344.  *     gdImageFillToBorder floods a portion of the image with the specified value,
  345.  *     beginning at the specified point and stopping at the specified border value.
  346.  *   ARGUMENTS:
  347.  *     x, y(int) point to start fill
  348.  *     border(int) value of border at which to stop.
  349.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  350.  *     value(int) value to use for fill
  351.  *   RETURN VALUE:
  352.  *     # pixels filled
  353.  */
  354. long
  355. gdImageFillToBorder (int x, int y, int border, Image * imgIO, int value)
  356. {
  357.   int lastBorder;
  358.   /* Seek left */
  359.   int leftLimit, rightLimit;
  360.   int i;
  361.   long nfill = 0;
  362.   leftLimit = (-1);
  363.   if (border < 0) {
  364.     /* Refuse to fill to a non-solid border */
  365.     return (nfill);
  366.   }
  367.   for (i = x; (i >= 0); i--) {
  368.     //if (gdImageGetPixel(imgIO, i, y) == border) {
  369.     if (getpixel (i, y, imgIO) == border) {
  370.       break;
  371.     }
  372.     //gdImageSetPixel(im, i, y, color);
  373.     setpixel (i, y, imgIO, value);
  374.     nfill++;
  375.     leftLimit = i;
  376.   }
  377.   if (leftLimit == (-1)) {
  378.     return (nfill);
  379.   }
  380.   /* Seek right */
  381.   rightLimit = x;
  382.   for (i = (x + 1); (i < imgIO->width); i++) {
  383.     //if (gdImageGetPixel(im, i, y) == border) {
  384.     if (getpixel (i, y, imgIO) == border) {
  385.       break;
  386.     }
  387.     //gdImageSetPixel(im, i, y, color);
  388.     setpixel (i, y, imgIO, value);
  389.     nfill++;
  390.     rightLimit = i;
  391.   }
  392.   /* Look at lines above and below and start paints */
  393.   /* Above */
  394.   if (y > 0) {
  395.     lastBorder = 1;
  396.     for (i = leftLimit; (i <= rightLimit); i++) {
  397.       int c;
  398.       //c = gdImageGetPixel(im, i, y-1);
  399.       c = getpixel (i, y - 1, imgIO);
  400.       if (lastBorder) {
  401.         if ((c != border) && (c != value)) {
  402.           nfill += gdImageFillToBorder (i, y - 1,
  403.                                         border, imgIO, value);
  404.           lastBorder = 0;
  405.         }
  406.       }
  407.       else if ((c == border) || (c == value)) {
  408.         lastBorder = 1;
  409.       }
  410.     }
  411.   }
  412.   /* Below */
  413.   if (y < ((imgIO->height) - 1)) {
  414.     lastBorder = 1;
  415.     for (i = leftLimit; (i <= rightLimit); i++) {
  416.       int c;
  417.       //c = gdImageGetPixel(im, i, y+1);
  418.       c = getpixel (i, y + 1, imgIO);
  419.       if (lastBorder) {
  420.         if ((c != border) && (c != value)) {
  421.           nfill += gdImageFillToBorder (i, y + 1,
  422.                                         border, imgIO, value);
  423.           lastBorder = 0;
  424.         }
  425.       }
  426.       else if ((c == border) || (c == value)) {
  427.         lastBorder = 1;
  428.       }
  429.     }
  430.   }
  431.   return (nfill);
  432. }
  433.  
  434. /*
  435.  * gdImageFill()
  436.  *   DESCRIPTION:
  437.  *     gdImageFill floods a portion of the image with the specified color,
  438.  *     beginning at the specified point and flooding the surrounding region
  439.  *     of the same color as the starting point.
  440.  *   ARGUMENTS:
  441.  *     x, y(int) point to start fill
  442.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  443.  *     value(int) value to use for fill
  444.  *   RETURN VALUE:
  445.  *     # pixels filled
  446.  */
  447. long
  448. gdImageFill (int x, int y, Image * imgIO, int value)
  449. {
  450.   int lastBorder;
  451.   int old;
  452.   int leftLimit, rightLimit;
  453.   int i;
  454.   int nfill = 0;
  455.   old = getpixel (x, y, imgIO);
  456.   //old = gdImageGetPixel(im, x, y);
  457.   if (old == value) {
  458.     /* Nothing to be done */
  459.     return (nfill);
  460.   }
  461.   /* Seek left */
  462.   leftLimit = (-1);
  463.   for (i = x; (i >= 0); i--) {
  464.     //if (gdImageGetPixel(im, i, y) != old) {
  465.     if (getpixel (i, y, imgIO) != old) {
  466.       break;
  467.     }
  468.     //gdImageSetPixel(im, i, y, color);
  469.     setpixel (i, y, imgIO, value);
  470.     nfill++;
  471.     leftLimit = i;
  472.   }
  473.   if (leftLimit == (-1)) {
  474.     return (nfill);
  475.   }
  476.   /* Seek right */
  477.   rightLimit = x;
  478.   for (i = (x + 1); (i < imgIO->width); i++) {
  479.     //if (gdImageGetPixel(im, i, y) != old) {
  480.     if (getpixel (i, y, imgIO) != old) {
  481.       break;
  482.     }
  483.     //gdImageSetPixel(im, i, y, color);
  484.     setpixel (i, y, imgIO, value);
  485.     nfill++;
  486.     rightLimit = i;
  487.   }
  488.   /* Look at lines above and below and start paints */
  489.   /* Above */
  490.   if (y > 0) {
  491.     lastBorder = 1;
  492.     for (i = leftLimit; (i <= rightLimit); i++) {
  493.       int c;
  494.       //c = gdImageGetPixel(im, i, y-1);
  495.       c = getpixel (i, y - 1, imgIO);
  496.       if (lastBorder) {
  497.         if (c == old) {
  498.           //gdImageFill(im, i, y-1, color);               
  499.           nfill += gdImageFill (i, y - 1, imgIO, value);
  500.           lastBorder = 0;
  501.         }
  502.       }
  503.       else if (c != old) {
  504.         lastBorder = 1;
  505.       }
  506.     }
  507.   }
  508.   /* Below */
  509.   if (y < ((imgIO->height) - 1)) {
  510.     lastBorder = 1;
  511.     for (i = leftLimit; (i <= rightLimit); i++) {
  512.       int c;
  513.       //c = gdImageGetPixel(im, i, y+1);
  514.       c = getpixel (i, y + 1, imgIO);
  515.       if (lastBorder) {
  516.         if (c == old) {
  517.           //gdImageFill(im, i, y+1, color);               
  518.           nfill += gdImageFill (i, y + 1, imgIO, value);
  519.           lastBorder = 0;
  520.         }
  521.       }
  522.       else if (c != old) {
  523.         lastBorder = 1;
  524.       }
  525.     }
  526.   }
  527.   return (nfill);
  528. }
  529.  
  530. /*
  531.  * fill Voronoi diagram containing site (x, y)
  532.  */
  533. /*
  534.  * fill_Voronoi()
  535.  *   DESCRIPTION:
  536.  *     fill Voronoi diagram containing site (x, y)
  537.  *   ARGUMENTS:
  538.  *     x, y(double) coordinate of Voronoi site
  539.  *     n(int) coordination number
  540.  *     mode(int) fill mode
  541.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  542.  *   RETURN VALUE:
  543.  *     none
  544.  */
  545.  
  546.  
  547. void
  548. fill_Voronoi (double x, double y, int n, Image * imgIO, int mode)
  549. {
  550.   int ix, iy;
  551.  
  552.   int ind_5 = 3 * PIX_RANGE / 8;
  553.   int ind_7 = 5 * PIX_RANGE / 8;
  554.   int ind_4 = PIX_RANGE / 8;
  555.   int ind_8 = 7 * PIX_RANGE / 8;
  556.   ix = F_TO_INT (x);
  557.   iy = F_TO_INT (y);
  558.   ix += 3;
  559.   iy += 3;
  560.   if (mode == DISC_ONLY) {
  561.     if (n == 5)
  562.       gdImageFill (ix, iy, imgIO, ind_5);
  563.     if (n == 7)
  564.       gdImageFill (ix, iy, imgIO, ind_7);
  565.     if (n == 4)
  566.       gdImageFill (ix, iy, imgIO, ind_4);
  567.     if (n == 8)
  568.       gdImageFill (ix, iy, imgIO, ind_8);
  569.   }
  570. }
  571.  
  572. /*
  573.  * draw_poly()
  574.  *   DESCRIPTION:
  575.  *     draw_poly draws a closed polygon with the specified value.
  576.  *   ARGUMENTS:
  577.  *     x, y(int *) list of (x,y) points for vertices
  578.  *     n(int) number of (x,y) points
  579.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  580.  *     value(int) value to use for polygon border
  581.  *   RETURN VALUE:
  582.  *     none
  583.  */
  584. void
  585. draw_poly (int *x, int *y, int n, Image * imgIO, int value)
  586. {
  587.   int X;
  588.   int Y;
  589.   int i;
  590.  
  591.   X = x[n - 1];
  592.   Y = y[n - 1];
  593.   for (i = 0; i < n; i++) {
  594.     draw_line (X, Y, x[i], y[i], imgIO, value);
  595.     X = x[i];
  596.     Y = y[i];
  597.   }
  598. }
  599.  
  600. /*
  601.  * draw_poly_ovl()
  602.  *   DESCRIPTION:
  603.  *     draw_poly_ovl draws features over an existing polygon depending on polytype.
  604.  *   ARGUMENTS:
  605.  *     x, y(int *) list of (x,y) points for vertices
  606.  *     n(int) number of (X,Y) points
  607.  *     xc, yc(int) centroid of polygon
  608.  *     av_dirn(double) average direction of polygon
  609.  *     polytype(int) type of polygon
  610.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  611.  *     value(int) value to use for drawing
  612.  *   RETURN VALUE:
  613.  *     none
  614.  */
  615. void
  616. draw_poly_ovl (int *x, int *y, int n,
  617.                int xc, int yc,
  618.                double av_dirn, int polytype,
  619.                Image * imgIO, int value)
  620. {
  621.   int radius = 4;
  622.  
  623.   int i;
  624.  
  625.   if (polytype == APOLY) {
  626.     for (i = 0; i < n; i++)
  627.       draw_filled_circle (*(x + i), *(y + i), radius, imgIO, value);
  628.   }
  629.   else {
  630.     draw_poly (x, y, n, imgIO, value);
  631.  
  632.     draw_square (xc, yc, radius, imgIO, value);
  633.     draw_normal (xc, yc, av_dirn, imgIO, value);
  634.   }
  635. }
  636.  
  637. /*
  638.  * draw_polyfill()
  639.  *   DESCRIPTION:
  640.  *     draw_polyfill draws a closed polygon and fills it with the specified value.
  641.  *   ARGUMENTS:
  642.  *     x, y(int *) list of (x,y) points for vertices
  643.  *     n(int) number of (x,y) points
  644.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  645.  *     value(int) value to use for polygon border and fill
  646.  *   RETURN VALUE:
  647.  *     number of pixels filled
  648.  */
  649. unsigned long
  650. draw_polyfill (int *X, int *Y, int n, Image * imgIO, int value)
  651. {
  652.   int x;
  653.   int y;
  654.   int i;
  655.   int ymin = 10000;
  656.   int ymax = 0;
  657.   int j;
  658.   int ny;
  659.   int i1;
  660.   int xP;
  661.   int yP;
  662.   int xQ;
  663.   int yQ;
  664.   int temp;
  665.   int dx;
  666.   int dy;
  667.   int m;
  668.   int dyQ;
  669.   int E;
  670.   int xleft;
  671.   int xright;
  672.  
  673.   typedef struct element {
  674.     int xP;
  675.     int yQ;
  676.     int dx;
  677.     int dy;
  678.     int E;
  679.     struct element *next;
  680.   } element;
  681.   element **table, *p, *start, *end, *p0, *q;
  682.   unsigned long n_pixels;
  683.  
  684.   n_pixels = 0;
  685.   x = X[n - 1];
  686.   y = Y[n - 1];
  687.   for (i = 0; i < n; i++) {
  688.     draw_line (x, y, X[i], Y[i], imgIO, value);
  689.     x = X[i];
  690.     y = Y[i];
  691.     if (y < ymin)
  692.       ymin = y;
  693.     if (y > ymax)
  694.       ymax = y;
  695.   }
  696.   ny = ymax - ymin + 1;
  697.   if ((table = (element **) calloc (ny, sizeof (element **))) == 0)
  698.     ERRORMEM ("draw_polyfill")
  699.       for (j = 0; j < ny; j++)
  700.       table[j] = NULL;
  701.   for (i = 0; i < n; i++) {
  702.     i1 = i + 1;
  703.     if (i1 == n)
  704.       i1 = 0;
  705.     xP = X[i];
  706.     yP = Y[i];
  707.     xQ = X[i1];
  708.     yQ = Y[i1];
  709.     if (yP == yQ)
  710.       continue;
  711.     if (yQ < yP) {
  712.       temp = xP;
  713.       xP = xQ;
  714.       xQ = temp;
  715.       temp = yP;
  716.       yP = yQ;
  717.       yQ = temp;
  718.     }
  719.     if ((p = (element *) calloc (1, sizeof (element))) == 0)
  720.       ERRORMEM ("draw_polyfill")
  721.         p->xP = xP;
  722.     p->dx = xQ - xP;
  723.     p->yQ = yQ;
  724.     p->dy = yQ - yP;
  725.     j = yP - ymin;
  726.     p->next = table[j];
  727.     table[j] = p;
  728.   }
  729.   if ((start = end = (element *) calloc (1, sizeof (element))) == 0)
  730.     ERRORMEM ("draw_polyfill")
  731.       for (j = 0; j < ny; j++) {
  732.       y = ymin + j;
  733.       p = start;
  734.       while (p != end) {
  735.         if (p->yQ == y) {
  736.           if ((q = p->next) == end)
  737.             end = p;
  738.           else
  739.             *p = *q;
  740.           free (q);
  741.         }
  742.         else {
  743.           if ((dx = p->dx) != 0) {
  744.             x = p->xP;
  745.             dy = p->dy;
  746.             E = p->E;
  747.             m = dx / dy;
  748.             dyQ = 2 * dy;
  749.             x += m;
  750.             E += 2 * dx - m * dyQ;
  751.             if (E > dy || E < -dy) {
  752.               if (dx > 0) {
  753.                 x++;
  754.                 E -= dyQ;
  755.               }
  756.               else {
  757.                 x--;
  758.                 E += dyQ;
  759.               }
  760.             }
  761.             p->xP = x;
  762.             p->E = E;
  763.           }
  764.           p = p->next;
  765.         }
  766.       }
  767.       p = table[j];
  768.       while (p != NULL) {
  769.         x = end->xP = p->xP;
  770.         yQ = p->yQ;
  771.         dx = p->dx;
  772.         dy = p->dy;
  773.         q = start;
  774.         while (q->xP < x ||
  775.                q->xP == x && q != end &&
  776.                (long) q->dx * dy < (long) dx * q->dy)
  777.           q = q->next;
  778.         p0 = p;
  779.         p = p->next;
  780.         if (q == end)
  781.           end = p0;
  782.         else
  783.           *p0 = *q;
  784.         q->xP = x;
  785.         q->yQ = yQ;
  786.         q->dx = dx;
  787.         q->dy = dy;
  788.         q->E = 0;
  789.         q->next = p0;
  790.       }
  791.       for (p = start; p != end; p = p->next) {
  792.         xleft = p->xP + 1;
  793.         p = p->next;
  794.         xright = p->xP - 1;
  795.         if (xleft <= xright) {
  796.           draw_horline (xleft, xright, y, imgIO, value);
  797.           /* calculate # pixels filled for area */
  798.           n_pixels = n_pixels + xright - xleft + 2;
  799.         }
  800.       }
  801.     }
  802.   p = start;
  803.   while (p != end) {
  804.     p0 = p;
  805.     p = p->next;
  806.     free (p0);
  807.   }
  808.   free (start);
  809.   free (table);
  810.   return (n_pixels);
  811. }
  812.  
  813. /*
  814.  * draw_square()
  815.  *   DESCRIPTION:
  816.  *     draw_square draws a square with center at (x,y) and sides of size.
  817.  *   ARGUMENTS:
  818.  *     x, y(int) center point of square
  819.  *     size(int) length of square sides
  820.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  821.  *     value(int) value to use for border
  822.  *   RETURN VALUE:
  823.  *     none
  824.  */
  825. void
  826. draw_square (int x, int y, int size, Image * imgIO, int value)
  827. {
  828.   draw_horline (x - size / 2, x + size / 2, y - size / 2, imgIO, value);
  829.   draw_horline (x - size / 2, x + size / 2, y + size / 2, imgIO, value);
  830.   draw_verline (x - size / 2, y - size / 2, y + size / 2, imgIO, value);
  831.   draw_verline (x + size / 2, y - size / 2, y + size / 2, imgIO, value);
  832. }
  833.  
  834. /*
  835.  * draw_rect()
  836.  *   DESCRIPTION:
  837.  *     draw_rect draws a rectangle specified by an upper left point and a lower right point.
  838.  *   ARGUMENTS:
  839.  *     x1, y1(int) upper left point
  840.  *     x2, y2(int) lower right point
  841.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  842.  *     value(int) value to use for border
  843.  *   RETURN VALUE:
  844.  *     none
  845.  */
  846. void
  847. draw_rect (int x1, int y1, int x2, int y2, Image * imgIO, int value)
  848. {
  849.   draw_horline (x1, x2, y1, imgIO, value);
  850.   draw_horline (x1, x2, y2, imgIO, value);
  851.   draw_verline (x1, y1, y2, imgIO, value);
  852.   draw_verline (x2, y1, y2, imgIO, value);
  853. }
  854.  
  855. /*
  856.  * draw_cross()
  857.  *   DESCRIPTION:
  858.  *     draw_cross draws a cross with at the point (x,y).
  859.  *   ARGUMENTS:
  860.  *     x, y(int) center point of cross
  861.  *     size(int) length in pixels for cross legs
  862.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  863.  *     value(int) value to use for border
  864.  *   RETURN VALUE:
  865.  *     none
  866.  */
  867. void
  868. draw_cross (int x, int y, int size, Image * imgIO, int value)
  869. {
  870.   draw_line (x - size / 2, y - size / 2, x + size / 2, y + size / 2, imgIO, value);
  871.   draw_line (x + size / 2, y - size / 2, x - size / 2, y + size / 2, imgIO, value);
  872. }
  873.  
  874. /*
  875.  * draw_up_triang()
  876.  *   DESCRIPTION:
  877.  *     draw_up_triang draws an up triangle at the point (x,y).
  878.  *   ARGUMENTS:
  879.  *     x, y(int) center point of triangle
  880.  *     offset(int) size of triangle in pixels
  881.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  882.  *     value(int) value to use for border
  883.  *   RETURN VALUE:
  884.  *     none
  885.  */
  886. void
  887. draw_up_triang (int x, int y, int offset, Image * imgIO, int value)
  888. {
  889.   int x_up, x_ll, x_lr, y_up, y_ll, y_lr;
  890.  
  891.   x_up = x;
  892.   x_ll = x - (int) (offset * CS30);
  893.   x_lr = x + (int) (offset * CS30);
  894.   y_up = y - offset;
  895.   y_ll = y_lr = y + (offset / 2);
  896.   draw_line (x_up, y_up, x_ll, y_ll, imgIO, value);
  897.   draw_line (x_ll, y_ll, x_lr, y_lr, imgIO, value);
  898.   draw_line (x_lr, y_lr, x_up, y_up, imgIO, value);
  899. }
  900.  
  901.  
  902.  
  903. /*
  904.  * draw_dn_triang()
  905.  *   DESCRIPTION:
  906.  *     draw_up_triang draws a down triangle at the point (x,y).
  907.  *   ARGUMENTS:
  908.  *     x, y(int) center point of triangle
  909.  *     offset(int) size of triangle in pixels
  910.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  911.  *     value(int) value to use for border
  912.  *   RETURN VALUE:
  913.  *     none
  914.  */
  915. void
  916. draw_dn_triang (int x, int y, int offset, Image * imgIO, int value)
  917. {
  918.   int x_lw, x_ul, x_ur, y_lw, y_ul, y_ur;
  919.  
  920.   x_lw = x;
  921.   x_ul = x - (int) (offset * CS30);
  922.   x_ur = x + (int) (offset * CS30);
  923.   y_lw = y + offset;
  924.   y_ul = y_ur = y - (offset / 2);
  925.   draw_line (x_lw, y_lw, x_ul, y_ul, imgIO, value);
  926.   draw_line (x_ul, y_ul, x_ur, y_ur, imgIO, value);
  927.   draw_line (x_ur, y_ur, x_lw, y_lw, imgIO, value);
  928. }
  929.  
  930. /*
  931.  * draw_horline()
  932.  *   DESCRIPTION:
  933.  *     draw_horline draws a horizontal line.
  934.  *   ARGUMENTS:
  935.  *     xmin, xmax(int) min and max values for line
  936.  *     y(int) y value for line
  937.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  938.  *     value(int) value to use for line
  939.  *   RETURN VALUE:
  940.  *     none
  941.  */
  942. void
  943. draw_horline (int xmin, int xmax, int y, Image * imgIO, int value)
  944. {
  945.   while (xmin <= xmax)
  946.     setpixel (xmin++, y, imgIO, value);
  947. }
  948.  
  949. /*
  950.  * draw_verline()
  951.  *   DESCRIPTION:
  952.  *     draw_verline draws a vertical line.
  953.  *   ARGUMENTS:
  954.  *     x(int) x value for line
  955.  *     ymin, ymax(int) ymin and ymax values for line
  956.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  957.  *     value(int) value to use for line
  958.  *   RETURN VALUE:
  959.  *     none
  960.  */
  961. void
  962. draw_verline (int x, int ymin, int ymax, Image * imgIO, int value)
  963. {
  964.   while (ymin <= ymax)
  965.     setpixel (x, ymin++, imgIO, value);
  966. }
  967.  
  968. /*
  969.  * draw_normal()
  970.  *   DESCRIPTION:
  971.  *     draw_normal draws the direction normal to the average direction of segments in the
  972.  *     present group list (given by their average slope, m) at the specified point;
  973.  *     the slope of the normal is given by: mn = -1.0/m;
  974.  *   ARGUMENTS:
  975.  *     x, y(int) point to draw normal
  976.  *     m(double) average slope
  977.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  978.  *     value(int) value to use for line
  979.  *   RETURN VALUE:
  980.  *     none
  981.  */
  982. void
  983. draw_normal (int x, int y, double m, Image * imgIO, int value)
  984. {
  985.   int offset = 10;
  986.   double foffset;
  987.   double fdelx, fdely;
  988.   int x_mn, x_pl, y_mn, y_pl;
  989.   int delx, dely;
  990.   double lolim = 0.01, uplim = 200.0;
  991.  
  992.   if (fabs (m) < lolim) {       /* horizontal segm */
  993.     x_mn = x_pl = x;
  994.     y_mn = y - offset;
  995.     y_pl = y + offset;
  996.   }
  997.   else if (fabs (m) > uplim) {  /* vertical segm */
  998.     x_mn = x - offset;
  999.     x_pl = x + offset;
  1000.     y_mn = y_pl = y;
  1001.   }
  1002.   else {
  1003.     foffset = (double) offset;
  1004.     fdely = foffset / sqrt (m * m + 1.0);
  1005.     fdelx = fabs (m) * fdely;
  1006.     if ((fdelx - (int) fdelx) < 0.5)
  1007.       delx = (int) fdelx;
  1008.     else
  1009.       delx = (int) fdelx + 1;
  1010.     if ((fdely - (int) fdely) < 0.5)
  1011.       dely = (int) fdely;
  1012.     else
  1013.       dely = (int) fdely + 1;
  1014.  
  1015.     y_mn = y - dely;
  1016.     y_pl = y + dely;
  1017.     if ((int) SIGN (m) > 0) {   /* normal slope: SIGN(mn) < 0 */
  1018.       x_mn = x + delx;
  1019.       x_pl = x - delx;
  1020.     }
  1021.     else {                      /* normal slope: SIGN(mn) > 0 */
  1022.       x_mn = x - delx;
  1023.       x_pl = x + delx;
  1024.     }
  1025.   }
  1026.   draw_line (x_mn, y_mn, x_pl, y_pl, imgIO, value);
  1027. }
  1028.  
  1029. /*
  1030.  * setpixel()
  1031.  *   DESCRIPTION:
  1032.  *     setpixel sets the pixel at (x,y) with the supplied value
  1033.  *   ARGUMENTS:
  1034.  *     x, y(int) pixel point
  1035.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  1036.  *     value(int) pixel value to set
  1037.  *   RETURN VALUE:
  1038.  *     none
  1039.  */
  1040. void
  1041. setpixel (int x, int y, Image * imgIO, int value)
  1042. {
  1043.   unsigned char **image;        /* input/output image */
  1044.  
  1045.   image = imgIO->img;
  1046.   if (x < 0 || x >= imgIO->width || y < 0 || y >= imgIO->height) {
  1047.     return;
  1048.   }
  1049.   else {
  1050.     /*image is indexed by y first */
  1051.     image[y][x] = (unsigned char) value;
  1052.   }
  1053. }
  1054.  
  1055. /*
  1056.  * getpixel()
  1057.  *   DESCRIPTION:
  1058.  *     getpixel gets the pixel at (x,y)
  1059.  *   ARGUMENTS:
  1060.  *     x, y(int) pixel point
  1061.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  1062.  *   RETURN VALUE:
  1063.  *     pixel value(unsigned char)
  1064.  */
  1065. unsigned char
  1066. getpixel (int x, int y, Image * imgIO)
  1067. {
  1068.   unsigned char **image;        /* input/output image */
  1069.  
  1070.   image = imgIO->img;
  1071.   if (x < 0 || x >= imgIO->width || y < 0 || y >= imgIO->height) {
  1072.     return (0);
  1073.   }
  1074.   else {
  1075.     /*image is indexed by y first */
  1076.     return (image[y][x]);
  1077.   }
  1078. }
  1079.  
  1080. /*
  1081.  * getrow()
  1082.  *   DESCRIPTION:
  1083.  *     getrow gets the row of pixels 
  1084.  *   ARGUMENTS:
  1085.  *     row_p(unsigned char *) pointer to row buffer
  1086.  *     row(int) which row to get
  1087.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  1088.  *   RETURN VALUE:
  1089.  *     none
  1090.  */
  1091. void
  1092. getrow (unsigned char *row_p, int row, Image * imgIO)
  1093. {
  1094.   unsigned char **image;        /* input/output image */
  1095.   int ix;
  1096.  
  1097.   image = imgIO->img;
  1098.   for (ix = 0; ix < imgIO->width; ix++, row_p++) {
  1099.     *row_p = image[row][ix];
  1100.   }
  1101. }
  1102.  
  1103. /*
  1104.  * draw_border()
  1105.  *   DESCRIPTION:
  1106.  *     draw_border sets a border defined by the
  1107.  *     upper left corner (jmin, imin) and
  1108.  *     lower right corner (jmax, imax) with value
  1109.  *   ARGUMENTS:
  1110.  *     (jmin, imin), (jmax, imax) bounding box
  1111.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  1112.  *     value(int) pixel value to set
  1113.  *   RETURN VALUE:
  1114.  *     none
  1115.  */
  1116. void
  1117. draw_border (int jmin, int imin, int jmax, int imax, Image * imgIO, int value)
  1118. {
  1119.   int ibmin, jbmin, ibmax, jbmax;
  1120.   int ir, jc;
  1121.  
  1122.   ibmin = 0;
  1123.   ibmax = imgIO->height;
  1124.   jbmin = 0;
  1125.   jbmax = imgIO->width;
  1126.  
  1127.   if (jmin < 0)
  1128.     jmin = 0;
  1129.   if (imin < 0)
  1130.     imin = 0;
  1131.   if (jmax >= imgIO->width)
  1132.     jmax = imgIO->width;
  1133.   if (imax >= imgIO->height)
  1134.     imax = imgIO->height;
  1135.  
  1136.   /* horizontal lines */
  1137.   for (ir = ibmin; ir < imin; ir++)
  1138.     draw_line (jbmin, ir, jbmax, ir, imgIO, value);
  1139.   for (ir = imax + 1; ir < ibmax; ir++)
  1140.     draw_line (jbmin, ir, jbmax, ir, imgIO, value);
  1141.  
  1142.   /* vertical lines */
  1143.   for (jc = jbmin; jc < jmin; jc++)
  1144.     draw_line (jc, ibmin, jc, ibmax, imgIO, value);
  1145.   for (jc = jmax + 1; jc < jbmax; jc++)
  1146.     draw_line (jc, ibmin, jc, ibmax, imgIO, value);
  1147. }
  1148.  
  1149. /*
  1150.  * zero_border()
  1151.  *   DESCRIPTION:
  1152.  *     zero_border sets a n-pixel wide border around the image to zero
  1153.  *   ARGUMENTS:
  1154.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  1155.  *     npix border width in pixels
  1156.  *   RETURN VALUE:
  1157.  *     none
  1158.  */
  1159. void
  1160. zero_border (Image * imgIO, int npix)
  1161. {
  1162.   int i;
  1163.  
  1164.   if (npix <= 0)
  1165.     npix = 1;
  1166.   for (i = 0; i < npix; i++) {
  1167.     draw_line (i, i, imgIO->width - (1 + i), i, imgIO, BLACK);
  1168.     draw_line (i, imgIO->height - (1 + i), imgIO->width - (1 + i), imgIO->height - (1 + i), imgIO, BLACK);
  1169.     draw_line (i, i, i, imgIO->height - (1 + i), imgIO, BLACK);
  1170.     draw_line (imgIO->width - (1 + i), i, imgIO->width - (1 + i), imgIO->height - (1 + i), imgIO, BLACK);
  1171.   }
  1172. }
  1173.  
  1174. /*
  1175.  * reset_image()
  1176.  *   DESCRIPTION:
  1177.  *     reset_image sets all the pixels in the entire image to value
  1178.  *   ARGUMENTS:
  1179.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  1180.  *     value grayscale value to use (0-255)
  1181.  *   RETURN VALUE:
  1182.  *     none
  1183.  */
  1184. void
  1185. reset_image (Image * imgIO, int value)
  1186. {
  1187.   int ix;
  1188.   int iy;
  1189.  
  1190.   for (ix = 0; ix < imgIO->width; ix++)
  1191.     for (iy = 0; iy < imgIO->height; iy++)
  1192.       setpixel (ix, iy, imgIO, value);
  1193.  
  1194. }
  1195.