home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsiii / contour.c < prev    next >
C/C++ Source or Header  |  1992-12-14  |  10KB  |  509 lines
  1. /*****************************************************************************
  2. *
  3. *    contour.c
  4. *
  5. *    Author:    Tim Feldman
  6. *        Island Graphics Corporation
  7. *
  8. *    Vectorizes the outline of an elevation contour in a set of sampled
  9. *    data.  Uses Freeman chain encoding.
  10. *
  11. *****************************************************************************/
  12.  
  13. /*****************************************************************************
  14. *
  15. *    Include files
  16. *
  17. *****************************************************************************/
  18.  
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <malloc.h>
  22.  
  23. /*****************************************************************************
  24. *
  25. *    Constants
  26. *
  27. *****************************************************************************/
  28.  
  29. /***    these are the coordinates of the edges of the
  30.     rectangular array of sample points        ***/
  31.  
  32. #define X_MIN    0
  33. #define X_MAX    7
  34. #define Y_MIN    0
  35. #define Y_MAX    7
  36.  
  37. /*****************************************************************************
  38. *
  39. *    Structure definitions
  40. *
  41. *****************************************************************************/
  42.  
  43. /***    a Vector is one link in a simple chain that follows
  44.     the edge of a contour from sample point to sample point    ***/
  45.  
  46. struct vector
  47. {
  48.     short        dir;
  49.     struct vector *    next;
  50. };
  51.  
  52. typedef struct vector    Vector;
  53.  
  54. /***    these are the 'dir' values in a Vector:
  55.  
  56.     0    right
  57.     1    right and up
  58.     2    up
  59.     3    left and up
  60.     4    left
  61.     5    left and down
  62.     6    down
  63.     7    right and down        ***/
  64.  
  65. /*****************************************************************************
  66. *
  67. *    Global data
  68. *
  69. *****************************************************************************/
  70.  
  71. /***    this points to the first member in the Freeman chain of vectors    ***/
  72.  
  73. Vector *    chain;
  74.  
  75. /***    these are the coordinates of the starting point
  76.     of the Freeman chain, in the array of sample points    ***/
  77.  
  78. int    start_x;
  79. int    start_y;
  80.  
  81. /***    this is the elevation of the contour to be outlined
  82.     in the array of sample points                ***/
  83.  
  84. int    elev;
  85.  
  86. /***    this is the array of elevation samples for this example    ***/
  87.  
  88. int    sample[8][8] =
  89. {
  90.     100, 100, 100, 100, 100, 100, 100,   0,
  91.     100, 100, 200, 200, 200, 200, 100, 100,
  92.     100, 200, 200, 250, 255, 200, 100, 100,
  93.     100, 200, 200, 250, 200, 200, 100, 100,
  94.     100, 200, 200, 250, 200, 200, 100, 100,
  95.     100, 200, 100, 200, 100, 200, 200, 100,
  96.     100, 200, 100, 100, 100, 200, 200, 200,
  97.     100, 100, 100, 100, 100, 100, 100, 200
  98. };
  99.  
  100. /*****************************************************************************
  101. *
  102. *    Procedures
  103. *
  104. *****************************************************************************/
  105.  
  106. /*****************************************************************************
  107. *
  108. *    in_cont(x, y)
  109. *
  110. *    Determines whether the sample point at 'x, y' is within the contour
  111. *    being outlined.  Points outside of the array of samples are not
  112. *    in the contour.
  113. *
  114. *    Returns 0 if the point is not in the contour.
  115. *    Returns 1 if the point is     in the contour.
  116. *
  117. *****************************************************************************/
  118.  
  119. short
  120. in_cont(x, y)
  121.  
  122. int    x;
  123. int    y;
  124.  
  125. {
  126.     if ( (x < X_MIN) || (x > X_MAX) || (y < Y_MIN) || (y > Y_MAX) )
  127.         return(0);
  128.  
  129.     if (sample[x][y] == elev)
  130.         return(1);
  131.     else
  132.         return(0);
  133. }
  134.  
  135. /*****************************************************************************
  136. *
  137. *    probe(x, y, dir, new_x, new_y)
  138. *
  139. *    Checks a sample neighboring 'x, y' to see if it is in the contour
  140. *    being outlined.  'dir' specifies which neighboring sample to check.
  141. *    'new_x, new_y' always get the coordinates of the neighbor.
  142. *
  143. *    Returns 0 if the neighbor is not in the contour.
  144. *    Returns 1 if the neighbor is     in the contour.
  145. *
  146. *****************************************************************************/
  147.  
  148. short
  149. probe(x, y, dir, new_x, new_y)
  150.  
  151. int    x;
  152. int    y;
  153. int    dir;
  154. int *    new_x;
  155. int *    new_y;
  156.  
  157. {
  158.     /***    figure out coordinates of neighbor    ***/
  159.  
  160.     if ( (dir < 2) || (dir > 6) )
  161.         ++x;
  162.  
  163.     if ( (dir > 2) && (dir < 6) )
  164.         --x;
  165.  
  166.     if ( (dir > 0) && (dir < 4) )
  167.         ++y;
  168.  
  169.     if (dir > 4)
  170.         --y;
  171.  
  172.     /***    always return the new coordinates    ***/
  173.  
  174.     *new_x = x;
  175.     *new_y = y;
  176.  
  177.     /***    determine if the new sample point is in the contour    ***/
  178.  
  179.     return(in_cont(x, y));
  180. }
  181.  
  182. /*****************************************************************************
  183. *
  184. *    neighbor(x, y, last_dir, new_x, new_y)
  185. *
  186. *    Finds a neighbor of the sample at 'x, y' that is in the same
  187. *    contour.  Always follows the contour in a clockwise direction.
  188. *    'last_dir' is the direction that was used to get to 'x, y'
  189. *    when it was found.  'new_x, new_y' always get the coordinates
  190. *    of the neighbor.
  191. *
  192. *    This procedure should only be called for a sample that has at
  193. *    least one neighbor in the same contour.
  194. *
  195. *    Returns the direction to the neighbor.
  196. *
  197. *****************************************************************************/
  198.  
  199. int
  200. neighbor(x, y, last_dir, new_x, new_y)
  201.  
  202. int    x;
  203. int    y;
  204. int    last_dir;
  205. int *    new_x;
  206. int *    new_y;
  207.  
  208. {
  209. int    n;
  210. int    new_dir;
  211.  
  212.     /***    figure out where to start looking for a neighbor --
  213.         always look ahead and to the left of the last direction
  214.  
  215.         if the last vector was 0
  216.         then start looking at  1
  217.  
  218.         if the last vector was 1
  219.         then start looking at  3
  220.  
  221.         if the last vector was 2
  222.         then start looking at  3
  223.  
  224.         if the last vector was 3
  225.         then start looking at  5
  226.  
  227.         if the last vector was 4
  228.         then start looking at  5
  229.  
  230.         if the last vector was 5
  231.         then start looking at  7
  232.  
  233.         if the last vector was 6
  234.         then start looking at  7
  235.  
  236.         if the last vector was 7
  237.         then start looking at  1    ***/
  238.  
  239.     if (last_dir & 0x01)
  240.     {
  241.         /***    last dir is odd --
  242.             add 2 to it        ***/
  243.  
  244.         new_dir = last_dir + 2;
  245.     }
  246.     else
  247.     {
  248.         /***    last dir is even --
  249.             add 1 to it        ***/
  250.  
  251.         new_dir = last_dir + 1;
  252.     }
  253.  
  254.     /***    keep new_dir in the range 0 through 7    ***/
  255.  
  256.     if (new_dir > 7)
  257.         new_dir -= 8;
  258.  
  259.     /***    probe the neighbors, looking for one on the edge    ***/
  260.  
  261.     for (n = 0; n < 8; n++)
  262.     {
  263.         if (probe(x, y, new_dir, new_x, new_y))
  264.         {
  265.             /***    found the next clockwise edge neighbor --
  266.                 its coordinates have already been
  267.                 stuffed into new_x, new_y        ***/
  268.  
  269.             return(new_dir);
  270.         }
  271.         else
  272.         {
  273.             /***    check the next clockwise neighbor    ***/
  274.  
  275.             if (--new_dir < 0)
  276.                 new_dir += 8;
  277.         }
  278.     }
  279.     /***    should never exit routine by this way!    ***/
  280. }
  281.  
  282. /*****************************************************************************
  283. *
  284. *    build()
  285. *
  286. *    Builds a Freeman chain of vectors describing the edge of the
  287. *    contour with elevation 'elev'.  Always follows the contour
  288. *    in a clockwise direction.  Uses 'start_x, start_y' as tentative
  289. *    starting point; modifies them to hold coordinates of first point
  290. *    in chain.
  291. *
  292. *    Returns 0 if unsuccessful.
  293. *    Returns 1 if   successful.
  294. *
  295. *****************************************************************************/
  296.  
  297. short
  298. build()
  299.  
  300. {
  301. int        x;
  302. int        y;
  303. int        new_x;
  304. int        new_y;
  305. int        dir;
  306. int        last_dir;
  307. Vector *    new;
  308. Vector *    prev;
  309.  
  310.     /***    go left in the starting row until out of the contour    ***/
  311.  
  312.     while (in_cont(start_x, start_y))
  313.     {
  314.         --start_x;
  315.     }
  316.  
  317.     /***    move back right one point, to the leftmost edge
  318.         in the contour, in that row            ***/
  319.  
  320.     start_x++;
  321.  
  322.     /***    create the head of the chain    ***/
  323.  
  324.     chain = (Vector *)NULL;
  325.     prev = (Vector *)NULL;
  326.  
  327.     /***    check if the starting point
  328.         has no neighbors in the contour --
  329.         the starting direction to check is arbitrary    ***/
  330.  
  331.     x = start_x;
  332.     y = start_y;
  333.  
  334.     dir = 0;
  335.  
  336.     for ( ; ; )
  337.     {
  338.         if (probe(x, y, dir, &new_x, &new_y))
  339.         {
  340.             /***    found a neighbor in that direction
  341.                 (its coordinates are in new_x, new_y
  342.                 but we don't use them here)        ***/
  343.  
  344.             break;
  345.         }
  346.  
  347.         /***    try next direction    ***/
  348.  
  349.         if (++dir == 8)
  350.         {
  351.             /***    starting point has no neighbors --
  352.                 make the chain one vector long    ***/
  353.             
  354.             /***    allocate storage for the vector    ***/
  355.  
  356.             if ( (chain = (Vector *)malloc(sizeof(Vector))) == NULL)
  357.             {
  358.                 printf("Insufficient memory available.\n");
  359.                 return(0);
  360.             }
  361.  
  362.             /***    fill in the vector --
  363.                 the direction is arbitrary,
  364.                 since the point is isolated    ***/
  365.  
  366.             chain->dir = 0;
  367.             chain->next = (Vector *)NULL;
  368.  
  369.             return(1);
  370.         }
  371.     }
  372.  
  373.     /***    get ready to follow the edge --
  374.         since we are at the left edge,
  375.         force initial probe to be to upper left
  376.         by initializing last_dir to 1        ***/
  377.  
  378.     last_dir = 1;
  379.  
  380.     /***    follow the edge clockwise, building a Freeman chain    ***/
  381.  
  382.     for ( ; ; )
  383.     {
  384.         /***    get the next point on the edge
  385.             and the vector to it        ***/
  386.  
  387.         dir = neighbor(x, y, last_dir, &new_x, &new_y);
  388.  
  389.         /***    allocate storage for the new vector    ***/
  390.  
  391.         if ( (new = (Vector *)malloc(sizeof(Vector))) == NULL)
  392.         {
  393.             printf("Insufficient memory available.\n");
  394.             return(0);
  395.         }
  396.  
  397.         /***    fill in the new vector    ***/
  398.  
  399.         new->dir = dir;
  400.         new->next = (Vector *)NULL;
  401.  
  402.         if (prev)
  403.         {
  404.             /***    add it to the existing chain    ***/
  405.  
  406.             prev->next = new;
  407.         }
  408.         else
  409.         {
  410.             /***    it is the first vector in the chain    ***/
  411.  
  412.             chain = new;
  413.         }
  414.  
  415.         /***    maybe done with contour    ***/
  416.  
  417.         if ( (new_x == start_x) && (new_y == start_y) )
  418.             return(1);
  419.  
  420.         /***    else get ready to continue following the edge    ***/
  421.  
  422.         prev = new;
  423.         x = new_x;
  424.         y = new_y;
  425.         last_dir = dir;
  426.     }
  427. }
  428.  
  429. /*****************************************************************************
  430. *
  431. *    report()
  432. *
  433. *    Follows the Freeman chain of vectors describing the edge of the
  434. *    contour with elevation 'elev'.  Reports the elevation, start point,
  435. *    direction vectors, and the number of vectors in the chain.
  436. *
  437. *****************************************************************************/
  438.  
  439. void
  440. report()
  441.  
  442. {
  443. Vector *    p;
  444. int        n;
  445.  
  446.     printf("Elevation = %d\n", elev);
  447.     printf("Start point (x, y) = %d, %d\n", start_x, start_y);
  448.  
  449.     p = chain;
  450.     n = 0;
  451.  
  452.     while (p)
  453.     {
  454.         printf("%d\n", p->dir);
  455.         p = p->next;
  456.         ++n;
  457.     }
  458.  
  459.     if (n > 1)
  460.         printf("%d vectors in the chain.\n", n);
  461.     else
  462.         printf("1 vector in the chain.\n");
  463. }
  464.  
  465. /*****************************************************************************
  466. *
  467. *    main()
  468. *
  469. *    Describes the outline of an elevation contour in the sampled data.
  470. *
  471. *    Returns  0 if   successful.
  472. *    Returns -1 if unsuccessful.
  473. *
  474. *****************************************************************************/
  475.  
  476. int
  477. main()
  478.  
  479. {
  480.     /***    get the elevation of the contour to follow
  481.         and get a starting point within the contour --
  482.  
  483.         they are given explicitly in this example, but
  484.         in a real application the user would provide them,
  485.         or they would be found algorithmically            ***/
  486.  
  487.     elev = 200;
  488.     start_x = 3;
  489.     start_y = 2;
  490.  
  491.     /***    follow the edge of the contour,
  492.         building a Freeman chain of vectors        ***/
  493.  
  494.     if (build())
  495.     {
  496.         /***    report the results    ***/
  497.  
  498.         report();
  499.         return(0);
  500.     }
  501.     else
  502.     {
  503.         /***    failed    ***/
  504.  
  505.         return(-1);
  506.     }
  507. }
  508.  
  509.