home *** CD-ROM | disk | FTP | other *** search
/ Encyclopedia of Graphics File Formats Companion / GFF_CD.ISO / software / unix / saoimage / sao1_07.tar / csrpoly3.c < prev    next >
C/C++ Source or Header  |  1990-04-20  |  6KB  |  195 lines
  1. #ifndef lint
  2. static char SccsId[] = "%W%  %G%";
  3. #endif
  4.  
  5. /* Module:    csrpoly3.c (Cursor Polygon Line)
  6.  * Purpose:    Manipulate vertex lists for drawing polygon cursor
  7.  * Subroutine:    closest_polygon_line()        returns: int
  8.  * Copyright:    1989 Smithsonian Astrophysical Observatory
  9.  *        You may do anything you like with this file except remove
  10.  *        this copyright.  The Smithsonian Astrophysical Observatory
  11.  *        makes no representations about the suitability of this
  12.  *        software for any purpose.  It is provided "as is" without
  13.  *        express or implied warranty.
  14.  * Modified:    {0} Michael VanHilst    initial version        30 June 1989
  15.  *        {n} <who> -- <does what> -- <when>
  16.  */
  17.  
  18. #include <math.h>        /* define sqrt() */
  19. #include <X11/Xlib.h>        /* X window stuff */
  20.  
  21. #define ABS(a) ((a) < 0 ? (-(a)) : (a))
  22. #define SQR(a) ((a) * (a))
  23.  
  24. /*
  25.  * Subroutine:    closest_polygon_line
  26.  * Purpose:    Test for the closest polygon segment
  27.  * Note:    in case of tie chose segment forming smallest angle with
  28.  *        vector from pointer to closest point on segment
  29.  * Method:    top down search
  30.  */
  31. int closest_polygon_line ( x, y, vertex, cnt )
  32.      int x, y;
  33.      XPoint *vertex;
  34.      int cnt;
  35. {
  36.   double min_distance, min_cosine;
  37.   double new_distance, new_cosine;
  38.   int min_endpoint, endpoint;
  39.   int min_j;
  40.   int i, j;
  41.   static double distance_from_segment(), cos_to_segment();
  42.  
  43.   min_distance = 1.0E30;
  44.   min_j = 0;
  45.   for( j=cnt, i=j-1; i>=0; i--, j-- ) {
  46.     new_distance = distance_from_segment(x, y, vertex[i].x, vertex[i].y,
  47.                      vertex[j].x, vertex[j].y, &endpoint);
  48.     if( new_distance <= min_distance ) {
  49.       if( new_distance < min_distance ) {
  50.     min_j = j;
  51.     min_distance = new_distance;
  52.     min_cosine = -1.0;
  53.     min_endpoint = endpoint;
  54.       } else {
  55.     if( min_cosine < 0.0 )
  56.       min_cosine =
  57.         cos_to_segment(x, y, vertex[min_j-1].x, vertex[min_j-1].y,
  58.                vertex[min_j].x, vertex[min_j].y, min_endpoint);
  59.     new_cosine = cos_to_segment(x, y, vertex[i].x, vertex[i].y,
  60.                     vertex[j].x, vertex[j].y, endpoint);
  61.     if( new_cosine < min_cosine ) {
  62.       min_j = j;
  63.       min_cosine = new_cosine;
  64.       min_endpoint = endpoint;
  65.     }
  66.       }
  67.     }
  68.   }
  69.   return( min_j );
  70. }
  71.  
  72. /*
  73.  * Subroutine:    distance_from_segment
  74.  * Returns:    square of shortest distance from reference to line segment
  75.  * Method:    Determine closest point on line, if it is in segment, return
  76.  *        its distance, else return distance to  closest endpoint
  77.  * Method:      Equation of the line of the segement: ax + b = y
  78.  *          a = (y2-y1)/(x2-x1), b = y1 - (a * x1)
  79.  *        Perpendicular line passing through x, y: aax + bb = y
  80.  *          aa = -1/a, bb = y_ref - (aa * x_ref)
  81.  *        Intersection of two lines: x_norm, y_norm
  82.  *          x_norm = (b - bb) / (a - aa), y_norm = (a * x_norm) + b
  83.  */
  84. static double distance_from_segment ( x_ref, y_ref, x1, y1, x2, y2, endpoint )
  85.      int x_ref, y_ref;        /* i: coordinates of reference point */
  86.      int x1, y1, x2, y2;    /* i: coordinates of segment endpoints */
  87.      int *endpoint;        /* o: closest pt end1=1 end2=2 between=0 */
  88. {
  89.   double x_norm, y_norm;
  90.   int orthogonal;
  91.  
  92.   /* determine closest point of line to reference point */
  93.   if( x2 == x1 ) {
  94.     /* line runs vertical or not at all */
  95.     x_norm = (double)x1;
  96.     y_norm = (double)y_ref;
  97.     orthogonal = 1;
  98.   } else if( y2 == y1 ) {
  99.     /* line runs horizontal */
  100.     x_norm = (double)x_ref;
  101.     y_norm = (double)y1;
  102.     orthogonal = -1;
  103.   } else {
  104.     register double a, b;
  105.     register double aa, bb;
  106.  
  107.     orthogonal = 0;
  108.     a = (double)(y2 - y1) / (double)(x2 - x1);
  109.     aa = -1.0 / a;
  110.     b = (double)y1 - (a * (double)x1);
  111.     bb = (double)y_ref - (aa * (double)x_ref);
  112.     x_norm = (b - bb) / (aa - a);
  113.     y_norm = (a * x_norm) + b;
  114.   }
  115.   *endpoint = 3;
  116.   /* determine if point is in segment */
  117.   if( orthogonal == 1 ) {
  118.     /* vertical line, better to check y coords (all x the same) */
  119.     if( y1 > y2 ) {
  120.       if( (y_norm <= (double)y1) && (y_norm >= (double)y2) )
  121.     *endpoint = 0;
  122.     } else {
  123.       if( (y_norm >= (double)y1) && (y_norm <= (double)y2) )
  124.     *endpoint = 0;
  125.     }
  126.   } else {
  127.     /* determine if point is in segment */
  128.     if( x1 > x2 ) {
  129.       if( (x_norm <= (double)x1) && (x_norm >= (double)x2) )
  130.     *endpoint = 0;
  131.     } else {
  132.       if( (x_norm >= (double)x1) && (x_norm <= (double)x2) )
  133.     *endpoint = 0;
  134.     }
  135.   }
  136.   if( *endpoint == 0 ) {
  137.     return( SQR((double)x_ref - x_norm) + SQR((double)y_ref - y_norm) );
  138.   } else {
  139.     int d1, d2;
  140.  
  141.     d1 = SQR(x_ref - x1) + SQR(y_ref - y1);
  142.     d2 = SQR(x_ref - x2) + SQR(y_ref - y2);
  143.     if( d1 < d2 ) {
  144.       *endpoint = 1;
  145.       return( (double)d1 );
  146.     } else {
  147.       *endpoint = 2;
  148.       return( (double)d2 );
  149.     }
  150.   }
  151. }
  152.  
  153. /*
  154.  * Subroutine:    cos_to_segment
  155.  * Returns:    cosine squared of angle between vector from reference to
  156.  *        closest point on line and vector along line away from reference
  157.  * Method:    cos = vector scalar (cross) product / product of lengths
  158.  * Note:    Cosine-squared uses one multiply where cosine needs 2 sqrts
  159.  */
  160. static double cos_to_segment ( x_ref, y_ref, x1, y1, x2, y2, endpoint )
  161.      int x_ref, y_ref;        /* i: coordinates of reference point */
  162.      int x1, y1, x2, y2;    /* i: coordinates of segment endpoints */
  163.      int endpoint;        /* i: closest pt end1=-1 end2=1 between=0 */
  164. {
  165.   int segment_i, segment_j;
  166.   int ray_i, ray_j;
  167.   int segment_len;
  168.  
  169.   if( endpoint == 0 )
  170.     /* closest point was on segment, angle is 90 deg, cos = 0 */
  171.     return( 0.0 );
  172.   segment_i = x2 - x1;
  173.   segment_j = y2 - y1;
  174.   if( (segment_len = SQR(segment_i) + SQR(segment_j)) == 0 )
  175.     /* if segment has no length, make it a sure loser for insertion */
  176.     return( 1.1 );
  177.   if( endpoint == 1 ) {
  178.     ray_i = x1 - x_ref;
  179.     ray_j = y1 - y_ref;
  180.   } else {
  181.     /* reverse sense since segment is also going other way */
  182.     ray_i = x_ref - x2;
  183.     ray_j = y_ref - y2;
  184.   }
  185.   /*
  186.   return( ((double)SQR((segment_i * ray_i) + (segment_j * ray_j)) /
  187.        (double)(segment_len * (SQR(ray_i) + SQR(ray_j))))) );
  188.   */
  189.   segment_i *= ray_i;
  190.   segment_j *= ray_j;
  191.   segment_i += segment_j;
  192.   return( (double)(segment_i * segment_i) /
  193.       (double)(segment_len * (SQR(ray_i) + SQR(ray_j))) );
  194. }
  195.