Path: utzoo!mnetor!uunet!husc6!cmcl2!nrl-cmf!ames!ncar!oddjob!gargoyle!att-ih!alberta!calgary!allan
From: allan@calgary.UUCP (Jeff Allan)
Newsgroups: comp.graphics
Subject: Re: Lines intersecting with a triangle...
Message-ID: <1501@vaxb.calgary.UUCP>
Date: 30 Mar 88 01:08:17 GMT
References: <14212@hc.DSPO.GOV>
Organization: U. of Calgary, Calgary, Ab.
Lines: 80
Summary: The solution boils down to line / line intersections

In article <14212@hc.DSPO.GOV>, siegel@hc.DSPO.GOV (Josh Siegel) writes:
> 
> When given a line, and three points that make up a triangle,
> how do I tell if the line intersects the triangle and where it
> intersects....

The solution is to intersect the line with each line of the triangle
then check to see if the intersection points lie between the end-points
of the triangle. There are, however, a number of optional ways of doing 
things depending on your situation.

If it is actually a line segment that you are comparing with the triangle,
then you can compare the rectangular extents of both figures. If the 
extents do not overlap then the figures don't either. But if they do overlap
the figures still may not. You can check this by comparing the two line segment
end-points against each side of the triangle. If both end-points lie outside
of any one edge of the triangle then the figures do not overlap. If this is
not the case then you will still have to do the intersections.

If, on the other hand, you are actually dealing with an infinite line then
you can quickly check whether there is an intersection by checking to see
if all three points of the triangle lie on one side of the line. If so then 
there is no intersection.

Here are some algorithms which may come in handy.

/************************************************************************/
/* 	INTERSECT2							*/
/* Finds the intersection of 2 lines in 2D.				*/
/* The homogeneous representation of each line segment is found.	*/
/*     Ax + By + C = 0							*/
/* The intersection is found when the determinant of the matrix:	*/
/*     A1	A2  x							*/
/*     B1	B2  y							*/
/*     C1	C2  w							*/
/* is zero. The determinant is calculated by co-factor expansion.	*/
/* The resulting homogeneous point (x,y,w) is the intersection point.	*/
/* This is not the most efficient algorithm but it is numerically stable*/
/************************************************************************/
int intersect2 (p1, p2, q1, q2, result)
POINTSTRUCT	*p1, *p2, *q1, *q2, *result;
{
    POINTSTRUCT    homo;
    double  a1,b1,c1,a2,b2,c2, w, t;

    a1 = p1->y - p2->y;
    b1 = p2->x - p1->x;
    c1 = p1->x * p2->y - p2->x * p1->y;
    a2 = q1->y - q2->y;
    b2 = q2->x - q1->x;
    c2 = q1->x * q2->y - q2->x * q1->y;

    w = a1*b2 - a2*b1;
    if (-0.00001 < w  && w < 0.00001) return 0; /* Parallel lines */
    homo.x = b1*c2 - b2*c1;
    homo.y = c1*a2 - c2*a1;
    result->x = homo.x / w;
    result->y = homo.y / w;

    return 1;
}

/************************************************************************/
  Point on one side of a line
/************************************************************************/

The point (x1,y1) lies on one side of the line from (x2,y2) to (x3,y3) if
the sign of:
	(x2-y3)*(x3-y2) + (x1-y3)*(x3-y1) + (x1-y2)*(x2-y1)
is positive and on the other if it is negative (I can never remember which).
This can be though of as the z component of the cross product of two vectors
or as the determinant to the 3X3 matrix:
	|x1 y1 1|
	|x2 y2 1|
	|x3 y3 1|

I hope this helps.
-- 
        Jeff Allan,  University of Calgary
	..!{ubc-vision,ihnp4}!alberta!calgary!allan