[Back to GRAPHICS SWAG index]  [Back to Main SWAG index]  [Original]

{
FROM:	Paul R. Santa-Maria 71674,422, 71674,422
TO:	Gayle Davis, 72067,2726
DATE:	1/16/95 10:47 PM
Re:	SWAG submission (GRAPHICS)

{The algorithm of this line intersection routine is based on vector
cross products of the line endpoints.  The recursion is only one level 
deep, to handle a specific degenerate case (collinear lines).  If the 
degenerate case is detected, it nudges one end of one line and looks 
to see if the intersection criterion is still fulfilled.  If not, it 
nudges the other end and tries again.--Steve Schafer [CIS 76711,522]}
 
  function INTERSECT(L1X1, L1Y1, L1X2, L1Y2,
                     L2X1, L2Y1, L2X2, L2Y2 : LongInt) : Boolean;
  var
    Z1, Z2, Z3, Z4 : LongInt;
  begin
    Z1 := L1X1*(L2Y2-L2Y1)+L2X2*(L2Y1-L1Y1)+L2X1*(L1Y1-L2Y2);
    Z2 := L2X1*(L1Y1-L1Y2)+L1X1*(L1Y2-L2Y1)+L1X2*(L2Y1-L1Y1);
    Z3 := L1X2*(L2Y1-L2Y2)+L2X1*(L2Y2-L1Y2)+L2X2*(L1Y2-L2Y1);
    Z4 := L2X2*(L1Y2-L1Y1)+L1X2*(L1Y1-L2Y2)+L1X1*(L2Y2-L1Y2);
    if (Z1 = 0) and (Z2 = 0) and (Z3 = 0) and (Z4 = 0) then
      INTERSECT := (INTERSECT(L1X1, L1Y1, L1X2, L1Y2, L2X1, L2Y1, 
                              L2X1+L2Y2-L2Y1, L2Y1+L2X1-L2X2) or 
                    INTERSECT(L1X1, L1Y1, L1X2, L1Y2, L2X2+L2Y2-L2Y1,
                              L2Y2+L2X1-L2X2, L2X2, L2Y2))
    else if (((Z1 >= 0) and (Z2 >= 0) and (Z3 >= 0) and (Z4 >= 0)) or
             ((Z1 <= 0) and (Z2 <= 0) and (Z3 <= 0) and (Z4 <= 0))) then
      INTERSECT := True
    else
      INTERSECT := False;
  end;
 

[Back to GRAPHICS SWAG index]  [Back to Main SWAG index]  [Original]