home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / LIBIP / PH.C < prev    next >
Encoding:
C/C++ Source or Header  |  1999-09-11  |  10.7 KB  |  419 lines
  1. /* 
  2.  * ph.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /*
  10.  * P(oly_)H(ull)
  11.  *
  12.  */
  13.  
  14. /*
  15.  * Code fragments for computation of convex hull of a given boundary.
  16.  * To use, call routine convex_hull(), 
  17.  * to obtain conv. hull of approximated polygon.
  18.  *
  19.  * construction of the convex hull of a polygon is accomplished by
  20.  * employing convex hull routine in poly_approx.c; the 
  21.  * Wall-Danielsson fitting routine poly_approx() is employed with a 
  22.  * tolerance of zero and thus reproduces the input set of vertices 
  23.  * (supplied in bdp->v) in the array ap; as in poly_edge, the input 
  24.  * polygon is assumed to be closed, containing n_vert+1 points, last 
  25.  * and first vertices being identical.
  26.  */
  27.  
  28. #include <stdio.h>
  29. #include <stdlib.h>
  30. #include <math.h>
  31. #include "ip.h"
  32.  
  33.  
  34. #define    APOLY        0
  35. #define    HULLPOLY    1
  36.  
  37. #define    OFF        0
  38. #define    ON        1
  39.  
  40. #undef    ECHO_INPUT
  41.  
  42. static struct spoint pnull;
  43.  
  44. /* globals */
  45. extern int loop_switch;
  46. extern int hull_switch;
  47. extern int n_ap_max;
  48.  
  49. /*
  50.  * fill_bdy_structure()
  51.  *   DESCRIPTION:
  52.  *     fill_bdy_structure fills the polygon boundary structure
  53.  *     that is used in p_app.c, as defined in ph.h
  54.  *     note:
  55.  *     by default, it is assumed here (as in poly_approx() !!) that the 
  56.  *     array {x_vertex, y_vertex} represents a closed polygon of n_vertex+1
  57.  *     vertices; in struct bdp, vn is set to n_vertex!! (not n_vertex+1)
  58.  *   ARGUMENTS:
  59.  *     bdp(Bdy *) pointer tp polygon boundary struct to be filled (see ph.h)
  60.  *     v(point *) pointer to vertices of polygon (see ph.h)
  61.  *     nv(long) number of vertices
  62.  *     tot_phi(double) total angular bend (not currently used)
  63.  *   RETURN VALUE:
  64.  *     none
  65.  */
  66. void
  67. fill_bdy_structure (struct Bdy *bdp, struct spoint *v, long nv, double tot_phi)
  68. {
  69.   int i;
  70.   struct spoint *temp_v;
  71.  
  72.   bdp->ident = 1;
  73.   bdp->per = 1L;                /* assn dummy number of pixels in perimeter */
  74.   bdp->vn = nv;                 /* input polygon */
  75.   bdp->an = 0L;                 /* for polyapprox(): should be init to 0L */
  76.   /* if not 0L, statement free(bdp->ap) in */
  77.   /* poly_approx() leads to memory leaks!! */
  78.   bdp->hn = 0;                  /* for convex_hull() */
  79.  
  80. /*
  81.  * assign memory to (x,y) structure field
  82.  */
  83.   if ((bdp->v = (struct spoint *) malloc ((size_t) (bdp->vn + 1) * sizeof (struct spoint))) == NULL) {
  84.     printf ("\n...memory allocation for bdp->v failed!!\n");
  85.     exit (1);
  86.   }
  87.  
  88. /*
  89.  * assign vertex coordinates to (x,y) in bdp structure 
  90.  */
  91.   temp_v = bdp->v;              /* save v[] pointer */
  92.   for (i = 0; i <= (int) bdp->vn; i++) {
  93.     temp_v->x = (v + i)->x;
  94.     temp_v->y = (v + i)->y;
  95.     temp_v++;
  96.   }
  97. }
  98.  
  99. /*
  100.  * poly_hull()
  101.  *   DESCRIPTION:
  102.  *     poly_hull implements smoothing of original polygon by edge fitting, employing
  103.  *     routine poly_approx().
  104.  *     note:
  105.  *     the approximated polygon returned by poly_approx() is not(!) closed;
  106.  *     if a closed polygon is desired (as for example for the purpose of
  107.  *     plotting it; see poly_ovl), the last vertex must be explicitly set
  108.  *     to be equal to the first vertex; the same applies, mutis mutandis,
  109.  *     to the routine convex_hull();
  110.  *   ARGUMENTS:
  111.  *     bdp(Bdy *) pointer tp polygon boundary struct (see ph.h)
  112.  *     v(point *) pointer to approximated vertices of polygon (see ph.h)
  113.  *     av_dirn(double) average direction of polygon
  114.  *     hull_area(int *) pointer to hull area
  115.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  116.  *     value(int) value to use for drawing
  117.  *   RETURN VALUE:
  118.  *     pointer to convex hull center point
  119.  */
  120. struct spoint *
  121. poly_hull (struct Bdy *bdp, struct spoint *v_ap,
  122.            double av_dirn, int *hull_area,
  123.            Image * imgIO, int value)
  124. {
  125.   struct spoint ***temp_h;
  126.   struct spoint *hullctr;
  127.  
  128.   int *x_ap, *y_ap;
  129.   int *x_hp, *y_hp;
  130.   int n_ap, n_hp;
  131.   int apoly = 0, hullpoly = 1;
  132.   int i;
  133.   int skip = 1;
  134.   char c = '\0';
  135.   double tol = 1.0;
  136.   char in_buf[IN_BUF_LEN];
  137.  
  138.  
  139.   do {
  140.     printf ("\n...enter tolerance for polyg approx(float):");
  141.     readlin (in_buf);
  142.     sscanf (in_buf, "%lf", &tol);
  143.  
  144.     poly_approx (bdp, (float) tol);
  145.  
  146. /* 
  147.  * copy the output of polyapprox() into the (x_ap, y_ap) format
  148.  * and into
  149.  * struct v_ap, for later use in calling function;   
  150.  * n_ap is preserved through the process; 
  151.  */
  152.     n_ap = (int) bdp->an;
  153.     printf ("\n...%d vertices in approx. polygon", n_ap);
  154.  
  155.     skip = 0;
  156.     if (n_ap > n_ap_max) {
  157.       printf ("...exceeds max of %d vertices\n", n_ap_max);
  158.       skip = 1;
  159.     }
  160.  
  161.     if (n_ap < 1) {
  162.       printf ("...no vertices to plot\n");
  163.       return (&pnull);
  164.     }
  165.  
  166.     if (skip == 0) {
  167.       if ((x_ap = (int *) calloc ((size_t) (n_ap + 1), sizeof (int))) == NULL)
  168.           exitmess ("\n...mem allocation for x_ap failed\n", 1);
  169.       if ((y_ap = (int *) calloc ((size_t) (n_ap + 1), sizeof (int))) == NULL)
  170.           exitmess ("\n...mem allocation for y_ap failed\n", 1);
  171.  
  172.  
  173.       for (i = 0; i < n_ap; i++) {
  174.         *(x_ap + i) = (v_ap + i)->x = bdp->ap[i]->x;
  175.         *(y_ap + i) = (v_ap + i)->y = bdp->ap[i]->y;
  176.       }
  177.  
  178. /* 
  179.  * close approx. polygon:
  180.  * set last point equal to first point: tot #pts = n_ap+1!! 
  181.  */
  182.       *(x_ap + n_ap) = (v_ap + n_ap)->x = bdp->ap[0]->x;
  183.       *(y_ap + n_ap) = (v_ap + n_ap)->y = bdp->ap[0]->y;
  184.  
  185. /* 
  186.  * draw new vertices
  187.  */
  188.       draw_poly_ovl (x_ap, y_ap, n_ap + 1,
  189.                      0, 0,
  190.                      av_dirn, APOLY,
  191.                      imgIO, value);
  192.     }
  193.     printf ("\n...repeat(y/n)?");
  194.   } while ((loop_switch != OFF) && ((c = readlin (in_buf)) != 'n'));
  195.  
  196.  
  197. /*
  198.  * compute and display convex hull
  199.  */
  200.   if (hull_switch == OFF) {
  201.     free (x_ap);
  202.     free (y_ap);
  203.     return (&pnull);
  204.   }
  205.   else if (hull_switch == ON) {
  206.     printf ("\n...compute convex hull:\n");
  207.  
  208.     convex_hull (bdp);
  209.  
  210. /* obtain location of convex hull center (as evaluated in convex_hull()) */
  211.     hullctr = reprt_hull_center ();
  212.  
  213. /* 
  214.  * copy the output of convex_hull() into the (x_hp, y_hp) format
  215.  * n_hp is preserved through the process 
  216.  */
  217.     n_hp = (int) bdp->hn;
  218.     if (n_hp < 1) {
  219.       printf ("\n no vertices to plot\n");
  220.       return (&pnull);
  221.     }
  222.  
  223. /*
  224.  * allocate memory   
  225.  */
  226.     if ((x_hp = (int *) calloc ((size_t) (n_hp + 1), sizeof (int))) == NULL)
  227.         exitmess ("\n...mem allocation for x_hp failed\n", 1);
  228.     if ((y_hp = (int *) calloc ((size_t) (n_hp + 1), sizeof (int))) == NULL)
  229.         exitmess ("\n...mem allocation for y_hp failed\n", 1);
  230.  
  231.     temp_h = (bdp->hpp);
  232.     for (i = 0; i < n_hp; i++) {
  233.       *(x_hp + i) = (**temp_h)->x;
  234.       *(y_hp + i) = (**temp_h)->y;
  235.       temp_h++;
  236.     }
  237.  
  238. /* 
  239.  * close convex_hull:
  240.  * set last point equal to first point: tot #pts = n_hp+1!! 
  241.  */
  242.     *(x_hp + n_hp) = (**(bdp->hpp))->x;
  243.     *(y_hp + n_hp) = (**(bdp->hpp))->y;
  244.  
  245. /* 
  246.  * evaluate convex hull area (function zero_moment() in sgl_stats.c)
  247.  */
  248.     *hull_area = zero_moment (n_hp, x_hp, y_hp);
  249.  
  250.  
  251. /* overlay new vertices on existing image */
  252.     draw_poly_ovl (x_hp, y_hp, n_hp + 1,
  253.                    hullctr->x, hullctr->y,
  254.                    av_dirn, HULLPOLY,
  255.                    imgIO, value);
  256.  
  257.  
  258.     free (x_hp);
  259.     free (y_hp);
  260.     if (!skip) {
  261.       free (x_ap);
  262.       free (y_ap);
  263.     }
  264.  
  265.     return (hullctr);
  266.   }
  267. }
  268.  
  269. /*
  270.  * poly_hull_tol()
  271.  *   DESCRIPTION:
  272.  *     variation on poly_hull()
  273.  *     does not ask for tolerance.
  274.  *     instead, tolerance is in argument list.
  275.  *   ARGUMENTS:
  276.  *     bdp(Bdy *) pointer tp polygon boundary struct (see ph.h)
  277.  *     v(point *) pointer to approximated vertices of polygon (see ph.h)
  278.  *     av_dirn(double) average direction of polygon
  279.  *     hull_area(int *) pointer to hull area
  280.  *     imgIO(Image *) pointer to Image struct (see tiffimage.h)
  281.  *     value(int) value to use for drawing
  282.  *   RETURN VALUE:
  283.  *     pointer to convex hull center point
  284.  */
  285.  
  286. struct spoint *
  287. poly_hull_tol (struct Bdy *bdp, struct spoint *v_ap,
  288.                double av_dirn, int *hull_area, float tol,
  289.                Image * imgIO, int value)
  290. {
  291.   struct spoint ***temp_h;
  292.   struct spoint *hullctr;
  293.  
  294.   int *x_ap, *y_ap;
  295.   int *x_hp, *y_hp;
  296.   int n_ap, n_hp;
  297.   int apoly = 0, hullpoly = 1;
  298.   int i;
  299.   int skip = 1;
  300.   char c = '\0';
  301.  
  302.  
  303.   poly_approx (bdp, (float) tol);
  304.  
  305. /* 
  306.  * copy the output of polyapprox() into the (x_ap, y_ap) format
  307.  * and into
  308.  * struct v_ap, for later use in calling function;   
  309.  * n_ap is preserved through the process; 
  310.  */
  311.   n_ap = (int) bdp->an;
  312.   skip = 0;
  313.   if (n_ap > n_ap_max) {
  314.     printf ("...exceeds max of %d vertices\n", n_ap_max);
  315.     skip = 1;
  316.   }
  317.  
  318.   if (n_ap < 1) {
  319.     printf ("...no vertices to plot\n");
  320.     return (&pnull);
  321.   }
  322.  
  323.   if (skip == 0) {
  324.     if ((x_ap = (int *) calloc ((size_t) (n_ap + 1), sizeof (int))) == NULL)
  325.         exitmess ("\n...mem allocation for x_ap failed\n", 1);
  326.     if ((y_ap = (int *) calloc ((size_t) (n_ap + 1), sizeof (int))) == NULL)
  327.         exitmess ("\n...mem allocation for y_ap failed\n", 1);
  328.  
  329.  
  330.     for (i = 0; i < n_ap; i++) {
  331.       *(x_ap + i) = (v_ap + i)->x = bdp->ap[i]->x;
  332.       *(y_ap + i) = (v_ap + i)->y = bdp->ap[i]->y;
  333.     }
  334.  
  335. /* 
  336.  * close approx. polygon:
  337.  * set last point equal to first point: tot #pts = n_ap+1!! 
  338.  */
  339.     *(x_ap + n_ap) = (v_ap + n_ap)->x = bdp->ap[0]->x;
  340.     *(y_ap + n_ap) = (v_ap + n_ap)->y = bdp->ap[0]->y;
  341.  
  342. /* 
  343.  * draw new vertices
  344.  */
  345.     draw_poly_ovl (x_ap, y_ap, n_ap + 1, 0, 0, av_dirn, APOLY, imgIO, value);
  346.   }
  347.  
  348.  
  349. /*
  350.  * compute and display convex hull
  351.  */
  352.   if (hull_switch == OFF) {
  353.     free (x_ap);
  354.     free (y_ap);
  355.     return (&pnull);
  356.   }
  357.   else if (hull_switch == ON) {
  358.  
  359.     convex_hull (bdp);
  360.  
  361. /* obtain location of convex hull center (as evaluated in convex_hull()) */
  362.     hullctr = reprt_hull_center ();
  363.  
  364. /* 
  365.  * copy the output of convex_hull() into the (x_hp, y_hp) format
  366.  * n_hp is preserved through the process 
  367.  */
  368.     n_hp = (int) bdp->hn;
  369.     if (n_hp < 1) {
  370.       printf ("\n no vertices to plot\n");
  371.       return (&pnull);
  372.     }
  373.  
  374. /*
  375.  * allocate memory   
  376.  */
  377.     if ((x_hp = (int *) calloc ((size_t) (n_hp + 1), sizeof (int))) == NULL)
  378.         exitmess ("\n...mem allocation for x_hp failed\n", 1);
  379.     if ((y_hp = (int *) calloc ((size_t) (n_hp + 1), sizeof (int))) == NULL)
  380.         exitmess ("\n...mem allocation for y_hp failed\n", 1);
  381.  
  382.     temp_h = (bdp->hpp);
  383.     for (i = 0; i < n_hp; i++) {
  384.       *(x_hp + i) = (**temp_h)->x;
  385.       *(y_hp + i) = (**temp_h)->y;
  386.       temp_h++;
  387.     }
  388.  
  389. /* 
  390.  * close convex_hull:
  391.  * set last point equal to first point: tot #pts = n_hp+1!! 
  392.  */
  393.     *(x_hp + n_hp) = (**(bdp->hpp))->x;
  394.     *(y_hp + n_hp) = (**(bdp->hpp))->y;
  395.  
  396. /* 
  397.  * evaluate convex hull area (function zero_moment() in sgl_stats.c)
  398.  */
  399.     *hull_area = zero_moment (n_hp, x_hp, y_hp);
  400.  
  401.  
  402. /* overlay new vertices on existing image */
  403.     draw_poly_ovl (x_hp, y_hp, n_hp + 1,
  404.                    hullctr->x, hullctr->y,
  405.                    av_dirn, HULLPOLY,
  406.                    imgIO, value);
  407.  
  408.  
  409.     free (x_hp);
  410.     free (y_hp);
  411.     if (!skip) {
  412.       free (x_ap);
  413.       free (y_ap);
  414.     }
  415.  
  416.     return (hullctr);
  417.   }
  418. }
  419.