home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 11932 < prev    next >
Encoding:
Text File  |  1992-11-16  |  2.6 KB  |  80 lines
  1. Path: sparky!uunet!gossip.pyramid.com!olivea!spool.mu.edu!agate!eos!aio!norm!goza
  2. From: goza@norm.JSC.NASA.GOV (Mike Goza)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Point inside a triangle
  5. Message-ID: <1992Nov16.143820.19300@aio.jsc.nasa.gov>
  6. Date: 16 Nov 92 14:38:20 GMT
  7. References: <7bv1svg@rpi.edu> <BxsLL1.5H5@slipknot.rain.com> <1992Nov16.115211.23169@sophia.smith.edu>
  8. Sender: goza@norm (Mike Goza)
  9. Organization: IGOAL
  10. Lines: 68
  11.  
  12. I happen to use the edge crossing method as stated by an earlier post.  It works for convex and
  13. concave polygons and only requires counting of crossing edges to determine in/out for any polygon, not just triangles.  If odd number of crossings then interior to poly.  Below is included the
  14. code that I used for testing points in/out of polys in the projection plane.  You can easily 
  15. modify it for 3D points and your own data structures.  In 3D just determine the largest component
  16. of the polygon normal and use the other two coordinates for the 2D projection.  The algorithm
  17. works perfectly well that way.  I would have sent the 3D version, but I found this version first.
  18. The only difference is a little code right at the beginning to determine whether I use XY, XZ, or 
  19. YZ coordinates.  Hope this will be of some use.
  20.  
  21.  
  22. /****************************************************************************
  23.  *
  24.  *  InteriorProjPoly - determines if point is interior to projected poly
  25.  *
  26.  *  Args:  pntintp - point to check
  27.  *         projpnt - array of projection points for list
  28.  *         list - array of index numbers for poly
  29.  *         npnts - number of points
  30.  *
  31.  *  Written By:  S. Michael Goza, NASA-JSC, 8/27/92
  32.  *
  33.  ***************************************************************************/
  34. int
  35. InteriorProjPoly(POINT_2D pntintp, POINT_2D *projpnt, INDEX *list, int npnts)
  36. {
  37.    float Ua, Va, Ub, Vb;
  38.    int NC, SH, NSH;
  39.    float xint;
  40.    float *ptmp;
  41.    register i, ind;
  42.  
  43. /*  SET THE SIGN HOLDER  */
  44.  
  45.    NC = 0;
  46.    ptmp = projpnt[list[0]];
  47.    Ua = ptmp[0] - pntintp[0];
  48.    Va = ptmp[1] - pntintp[1];
  49.    SH = (Va < 0.0)? -1: 1;
  50.  
  51. /*  NOW GO THROUGH EDGES AND LOOK FOR CROSS POINTS  */
  52.  
  53.    for(i=1,ind=1; i<=npnts; i++,ind++) {
  54.       if(ind >= npnts) ind = 0;
  55.       ptmp = projpnt[list[ind]];
  56.       Ub = ptmp[0] - pntintp[0];
  57.       Vb = ptmp[1] - pntintp[1];
  58.       NSH = (Vb < 0.0)? -1: 1;
  59.  
  60. /*  FOUND CROSS POINT SO SEE IF A POSITIVE INTERCEPT  */
  61.  
  62.       if(SH != NSH) {
  63.          xint = Ua - Va*(Ub -Ua) / (Vb - Va);
  64.          if(xint > 0.0) NC++;
  65.       }
  66.  
  67.       Ua = Ub;
  68.       Va = Vb;
  69.       SH = NSH;
  70.    }
  71.  
  72. /*  IF ODD NUMBER OF CROSSES THEN INTERIOR  */
  73.  
  74.    return(NC & 0x1);
  75. }
  76.  
  77. Mike Goza
  78. goza@cheers.jsc.nasa.gov
  79.   
  80.