Category : C Source Code
Archive   : GRAFGEM2.ZIP
Filename : XLINES.C

 
Output of file : XLINES.C contained in archive : GRAFGEM2.ZIP
/* 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 condititions:
*
* 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 */





  3 Responses to “Category : C Source Code
Archive   : GRAFGEM2.ZIP
Filename : XLINES.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/