home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / gems / gemsiii / insectc.c < prev    next >
Text File  |  1992-03-17  |  2KB  |  92 lines
  1. /* Faster Line Segment Intersection   */
  2. /* Franklin Antonio                   */
  3.  
  4. /* return values */
  5. #define DONT_INTERSECT 0
  6. #define DO_INTERSECT   1
  7. #define COLLINEAR      2
  8.  
  9.  
  10. /* The SAME_SIGNS macro assumes arithmetic where the exclusive-or    */
  11. /* operation will work on sign bits.  This works for twos-complement,*/
  12. /* and most other machine arithmetic.                                */
  13. #define SAME_SIGNS( a, b ) \
  14.     (((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 )
  15.  
  16.  
  17. /* The use of some short working variables allows this code to run   */
  18. /* faster on 16-bit computers, but is not essential.  It should not  */
  19. /* affect operation on 32-bit computers.  The short working variables*/
  20. /* to not restrict the range of valid input values, as these were    */
  21. /* constrained in any case, due to algorithm restrictions.           */
  22.  
  23.  
  24. int lines_intersect(x1,y1,x2,y2,x3,y3,x4,y4,x,y) 
  25. long x1,y1,x2,y2,x3,y3,x4,y4,*x,*y;
  26. {
  27.  
  28. long Ax,Bx,Cx,Ay,By,Cy,d,e,f,temp,num,offset;
  29. short x1lo,x1hi,x3lo,x3hi,y1lo,y1hi,y3lo,y3hi;
  30.  
  31. Ax = x2-x1;
  32. Bx = x3-x4;
  33.  
  34. if(Ax<0) {                        /* X bound box test*/
  35.   x1lo=(short)x2; x1hi=(short)x1;
  36.   } else {
  37.   x1hi=(short)x2; x1lo=(short)x1;
  38.   }
  39. if(Bx>0) {
  40.   if(x1hi < (short)x4 || (short)x3 < x1lo) return DONT_INTERSECT;
  41.   } else {
  42.   if(x1hi < (short)x3 || (short)x4 < x1lo) return DONT_INTERSECT;
  43.   }
  44.  
  45. Ay = y2-y1;
  46. By = y3-y4;
  47.  
  48. if(Ay<0) {                        /* Y bound box test*/
  49.   y1lo=(short)y2; y1hi=(short)y1;
  50.   } else {
  51.   y1hi=(short)y2; y1lo=(short)y1;
  52.   }
  53. if(By>0) {
  54.   if(y1hi < (short)y4 || (short)y3 < y1lo) return DONT_INTERSECT;
  55.   } else {
  56.   if(y1hi < (short)y3 || (short)y4 < y1lo) return DONT_INTERSECT;
  57.   }
  58.  
  59.  
  60. Cx = x1-x3;
  61. Cy = y1-y3;
  62. d = By*Cx - Bx*Cy;                    /* alpha numerator*/
  63. f = Ay*Bx - Ax*By;                    /* both denominator*/
  64. if(f>0) {                        /* alpha tests*/
  65.   if(d<0 || d>f) return DONT_INTERSECT;
  66.   } else {
  67.   if(d>0 || d<f) return DONT_INTERSECT;
  68.   }
  69.  
  70. e = Ax*Cy - Ay*Cx;                    /* beta numerator*/
  71. if(f>0) {                        /* beta tests*/
  72.   if(e<0 || e>f) return DONT_INTERSECT;
  73.   } else {
  74.   if(e>0 || e<f) return DONT_INTERSECT;
  75.   }
  76.  
  77. /*compute intersection coordinates*/
  78.  
  79. if(f==0) return COLLINEAR;
  80. num = d*Ax;                        /* numerator */
  81. offset = SAME_SIGNS(num,f) ? f/2 : -f/2;        /* round direction*/
  82. *x = x1 + (num+offset) / f;                /* intersection x */
  83.  
  84. num = d*Ay;
  85. offset = SAME_SIGNS(num,f) ? f/2 : -f/2;
  86. *y = y1 + (num+offset) / f;                /* intersection y */
  87.  
  88. return DO_INTERSECT;
  89. }
  90.  
  91.  
  92.