/* lines_intersect: AUTHOR: Mukesh Prasad
*
* This function computes whether two line segments,
* respectively joining the input points (x1,y1) -- (x2,y2)
* and the input points (x3,y3) -- (x4,y4) intersect.
* If the lines intersect, the output variables x, y are
* set to coordinates of the point of intersection.
*
* All values are in integers. The returned value is rounded
* to the nearest integer point.
*
* If non-integral grid points are relevant, the function
* can easily be transformed by substituting floating point
* calculations instead of integer calculations.
*
* Entry
* x1, y1, x2, y2 Coordinates of endpoints of one segment.
* x3, y3, x4, y4 Coordinates of endpoints of other segment.
*
* Exit
* x, y Coordinates of intersection point.
*
* The value returned by the function is one of:
*
* DONT_INTERSECT 0
* DO_INTERSECT 1
* COLLINEAR 2
*
* Error conditions:
*
* Depending upon the possible ranges, and particularly on 16-bit
* computers, care should be taken to protect from overflow.
*
* In the following code, 'long' values have been used for this
* purpose, instead of 'int'.
*
*/
#define DONT_INTERSECT 0
#define DO_INTERSECT 1
#define COLLINEAR 2
/**************************************************************
* *
* NOTE: The following macro to determine if two numbers *
* have the same sign, is for 2's complement number *
* representation. It will need to be modified for other *
* number systems. *
* *
**************************************************************/
#define SAME_SIGNS( a, b ) \
(((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 )
int lines_intersect( x1, y1, /* First line segment */
x2, y2,
x3, y3, /* Second line segment */
x4, y4,
x,
y /* Output value:
* point of intersection */
)
long
x1, y1, x2, y2, x3, y3, x4, y4,
*x, *y;
{
long a1, a2, b1, b2, c1, c2; /* Coefficients of line eqns. */
long r1, r2, r3, r4; /* 'Sign' values */
long denom, offset, num; /* Intermediate values */
/* Compute a1, b1, c1, where line joining points 1 and 2
* is "a1 x + b1 y + c1 = 0".
*/
a1 = y2 - y1;
b1 = x1 - x2;
c1 = x2 * y1 - x1 * y2;
/* Compute r3 and r4.
*/
r3 = a1 * x3 + b1 * y3 + c1;
r4 = a1 * x4 + b1 * y4 + c1;
/* Check signs of r3 and r4. If both point 3 and point 4 lie on
* same side of line 1, the line segments do not intersect.
*/
if ( r3 != 0 &&
r4 != 0 &&
SAME_SIGNS( r3, r4 ))
return ( DONT_INTERSECT );
/* Compute a2, b2, c2 */
a2 = y4 - y3;
b2 = x3 - x4;
c2 = x4 * y3 - x3 * y4;
/* Compute r1 and r2 */
r1 = a2 * x1 + b2 * y1 + c2;
r2 = a2 * x2 + b2 * y2 + c2;
/* Check signs of r1 and r2. If both point 1 and point 2 lie
* on same side of second line segment, the line segments do
* not intersect.
*/
if ( r1 != 0 &&
r2 != 0 &&
SAME_SIGNS( r1, r2 ))
return ( DONT_INTERSECT );
/* Line segments intersect: compute intersection point.
*/
denom = a1 * b2 - a2 * b1;
if ( denom == 0 )
return ( COLLINEAR );
offset = denom < 0 ? - denom / 2 : denom / 2;
/* The denom/2 is to get rounding instead of truncating. It
* is added or subtracted to the numerator, depending upon the
* sign of the numerator.
*/
num = b1 * c2 - b2 * c1;
*x = ( num < 0 ? num - offset : num + offset ) / denom;
num = a2 * c1 - a1 * c2;
*y = ( num < 0 ? num - offset : num + offset ) / denom;
return ( DO_INTERSECT );
} /* lines_intersect */
/* A main program to test the function.
*/
main()
{
long x1, x2, x3, x4, y1, y2, y3, y4;
long x, y;
for (;;) {
printf( "X1, Y1: " );
scanf( "%ld %ld", &x1, &y1 );
printf( "X2, Y2: " );
scanf( "%ld %ld", &x2, &y2 );
printf( "X3, Y3: " );
scanf( "%ld %ld", &x3, &y3 );
printf( "X4, Y4: " );
scanf( "%ld %ld", &x4, &y4 );
switch ( lines_intersect( x1, y1, x2, y2, x3, y3, x4, y4, &x, &y )) {
case DONT_INTERSECT:
printf( "Lines don't intersect\n" );
break;
case COLLINEAR:
printf( "Lines are collinear\n" );
break;
case DO_INTERSECT:
printf( "Lines intersect at %ld,%ld\n", x, y );
break;
}
}
} /* main */