home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / gems / g_gemsi.lha / GraphicsGems / PntOnLine.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-10  |  2.0 KB  |  53 lines
  1. /* 
  2. A Fast 2D Point-On-Line Test
  3. by Alan Paeth
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. #include "GraphicsGems.h"
  8.  
  9. int PntOnLine(px,py,qx,qy,tx,ty)
  10.    int px, py, qx, qy, tx, ty;
  11.    {
  12. /*
  13.  * given a line through P:(px,py) Q:(qx,qy) and T:(tx,ty)
  14.  * return 0 if T is not on the line through      <--P--Q-->
  15.  *        1 if T is on the open ray ending at P: <--P
  16.  *        2 if T is on the closed interior along:   P--Q
  17.  *        3 if T is on the open ray beginning at Q:    Q-->
  18.  *
  19.  * Example: consider the line P = (3,2), Q = (17,7). A plot
  20.  * of the test points T(x,y) (with 0 mapped onto '.') yields:
  21.  *
  22.  *     8| . . . . . . . . . . . . . . . . . 3 3
  23.  *  Y  7| . . . . . . . . . . . . . . 2 2 Q 3 3    Q = 2
  24.  *     6| . . . . . . . . . . . 2 2 2 2 2 . . .
  25.  *  a  5| . . . . . . . . 2 2 2 2 2 2 . . . . .
  26.  *  x  4| . . . . . 2 2 2 2 2 2 . . . . . . . .
  27.  *  i  3| . . . 2 2 2 2 2 . . . . . . . . . . .
  28.  *  s  2| 1 1 P 2 2 . . . . . . . . . . . . . .    P = 2
  29.  *     1| 1 1 . . . . . . . . . . . . . . . . .
  30.  *      +--------------------------------------
  31.  *        1 2 3 4 5 X-axis 10        15      19
  32.  *
  33.  * Point-Line distance is normalized with the Infinity Norm
  34.  * avoiding square-root code and tightening the test vs the
  35.  * Manhattan Norm. All math is done on the field of integers.
  36.  * The latter replaces the initial ">= MAX(...)" test with
  37.  * "> (ABS(qx-px) + ABS(qy-py))" loosening both inequality
  38.  * and norm, yielding a broader target line for selection.
  39.  * The tightest test is employed here for best discrimination
  40.  * in merging collinear (to grid coordinates) vertex chains
  41.  * into a larger, spanning vectors within the Lemming editor.
  42.  */
  43.  
  44.  
  45.     if ( ABS((qy-py)*(tx-px)-(ty-py)*(qx-px)) >=
  46.         (MAX(ABS(qx-px), ABS(qy-py)))) return(0);
  47.     if (((qx<px)&&(px<tx)) || ((qy<py)&&(py<ty))) return(1);
  48.     if (((tx<px)&&(px<qx)) || ((ty<py)&&(py<qy))) return(1);
  49.     if (((px<qx)&&(qx<tx)) || ((py<qy)&&(qy<ty))) return(3);
  50.     if (((tx<qx)&&(qx<px)) || ((ty<qy)&&(qy<py))) return(3);
  51.     return(2);
  52.     }
  53.