home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / gems / gemsiii / contour.c < prev    next >
C/C++ Source or Header  |  1992-03-17  |  10KB  |  508 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. }
  280.  
  281. /*****************************************************************************
  282. *
  283. *    build()
  284. *
  285. *    Builds a Freeman chain of vectors describing the edge of the
  286. *    contour with elevation 'elev'.  Always follows the contour
  287. *    in a clockwise direction.  Uses 'start_x, start_y' as tentative
  288. *    starting point; modifies them to hold coordinates of first point
  289. *    in chain.
  290. *
  291. *    Returns 0 if unsuccessful.
  292. *    Returns 1 if   successful.
  293. *
  294. *****************************************************************************/
  295.  
  296. short
  297. build()
  298.  
  299. {
  300. int        x;
  301. int        y;
  302. int        new_x;
  303. int        new_y;
  304. int        dir;
  305. int        last_dir;
  306. Vector *    new;
  307. Vector *    prev;
  308.  
  309.     /***    go left in the starting row until out of the contour    ***/
  310.  
  311.     while (in_cont(start_x, start_y))
  312.     {
  313.         --start_x;
  314.     }
  315.  
  316.     /***    move back right one point, to the leftmost edge
  317.         in the contour, in that row            ***/
  318.  
  319.     start_x++;
  320.  
  321.     /***    create the head of the chain    ***/
  322.  
  323.     chain = (Vector *)NULL;
  324.     prev = (Vector *)NULL;
  325.  
  326.     /***    check if the starting point
  327.         has no neighbors in the contour --
  328.         the starting direction to check is arbitrary    ***/
  329.  
  330.     x = start_x;
  331.     y = start_y;
  332.  
  333.     dir = 0;
  334.  
  335.     for ( ; ; )
  336.     {
  337.         if (probe(x, y, dir, &new_x, &new_y))
  338.         {
  339.             /***    found a neighbor in that direction
  340.                 (its coordinates are in new_x, new_y
  341.                 but we don't use them here)        ***/
  342.  
  343.             break;
  344.         }
  345.  
  346.         /***    try next direction    ***/
  347.  
  348.         if (++dir == 8)
  349.         {
  350.             /***    starting point has no neighbors --
  351.                 make the chain one vector long    ***/
  352.             
  353.             /***    allocate storage for the vector    ***/
  354.  
  355.             if ( (chain = (Vector *)malloc(sizeof(Vector))) == NULL)
  356.             {
  357.                 printf("Insufficient memory available.\n");
  358.                 return(0);
  359.             }
  360.  
  361.             /***    fill in the vector --
  362.                 the direction is arbitrary,
  363.                 since the point is isolated    ***/
  364.  
  365.             chain->dir = 0;
  366.             chain->next = (Vector *)NULL;
  367.  
  368.             return(1);
  369.         }
  370.     }
  371.  
  372.     /***    get ready to follow the edge --
  373.         since we are at the left edge,
  374.         force initial probe to be to upper left
  375.         by initializing last_dir to 1        ***/
  376.  
  377.     last_dir = 1;
  378.  
  379.     /***    follow the edge clockwise, building a Freeman chain    ***/
  380.  
  381.     for ( ; ; )
  382.     {
  383.         /***    get the next point on the edge
  384.             and the vector to it        ***/
  385.  
  386.         dir = neighbor(x, y, last_dir, &new_x, &new_y);
  387.  
  388.         /***    allocate storage for the new vector    ***/
  389.  
  390.         if ( (new = (Vector *)malloc(sizeof(Vector))) == NULL)
  391.         {
  392.             printf("Insufficient memory available.\n");
  393.             return(0);
  394.         }
  395.  
  396.         /***    fill in the new vector    ***/
  397.  
  398.         new->dir = dir;
  399.         new->next = (Vector *)NULL;
  400.  
  401.         if (prev)
  402.         {
  403.             /***    add it to the existing chain    ***/
  404.  
  405.             prev->next = new;
  406.         }
  407.         else
  408.         {
  409.             /***    it is the first vector in the chain    ***/
  410.  
  411.             chain = new;
  412.         }
  413.  
  414.         /***    maybe done with contour    ***/
  415.  
  416.         if ( (new_x == start_x) && (new_y == start_y) )
  417.             return(1);
  418.  
  419.         /***    else get ready to continue following the edge    ***/
  420.  
  421.         prev = new;
  422.         x = new_x;
  423.         y = new_y;
  424.         last_dir = dir;
  425.     }
  426. }
  427.  
  428. /*****************************************************************************
  429. *
  430. *    report()
  431. *
  432. *    Follows the Freeman chain of vectors describing the edge of the
  433. *    contour with elevation 'elev'.  Reports the elevation, start point,
  434. *    direction vectors, and the number of vectors in the chain.
  435. *
  436. *****************************************************************************/
  437.  
  438. void
  439. report()
  440.  
  441. {
  442. Vector *    p;
  443. int        n;
  444.  
  445.     printf("Elevation = %d\n", elev);
  446.     printf("Start point (x, y) = %d, %d\n", start_x, start_y);
  447.  
  448.     p = chain;
  449.     n = 0;
  450.  
  451.     while (p)
  452.     {
  453.         printf("%d\n", p->dir);
  454.         p = p->next;
  455.         ++n;
  456.     }
  457.  
  458.     if (n > 1)
  459.         printf("%d vectors in the chain.\n", n);
  460.     else
  461.         printf("1 vector in the chain.\n");
  462. }
  463.  
  464. /*****************************************************************************
  465. *
  466. *    main()
  467. *
  468. *    Describes the outline of an elevation contour in the sampled data.
  469. *
  470. *    Returns  0 if   successful.
  471. *    Returns -1 if unsuccessful.
  472. *
  473. *****************************************************************************/
  474.  
  475. int
  476. main()
  477.  
  478. {
  479.     /***    get the elevation of the contour to follow
  480.         and get a starting point within the contour --
  481.  
  482.         they are given explicitly in this example, but
  483.         in a real application the user would provide them,
  484.         or they would be found algorithmically            ***/
  485.  
  486.     elev = 200;
  487.     start_x = 3;
  488.     start_y = 2;
  489.  
  490.     /***    follow the edge of the contour,
  491.         building a Freeman chain of vectors        ***/
  492.  
  493.     if (build())
  494.     {
  495.         /***    report the results    ***/
  496.  
  497.         report();
  498.         return(0);
  499.     }
  500.     else
  501.     {
  502.         /***    failed    ***/
  503.  
  504.         return(-1);
  505.     }
  506. }
  507.  
  508.