Implementation and Analysis of Testing Whether Line Segments Intersect
To test whether two line segments intersect, we first
must have a way to represent each segment. Let
p1 and p2 define
the endpoints of one of the segments and p3
and p4 define the endpoints of the other.
Each endpoint is a Point structure. This
structure consists of three members, x,
y, and z, that
are the coordinates of a point. Recall that we ignore all
z-coordinates since lint
works in two dimensions.
The lint operation (see Example 17.2) begins by performing the
quick rejection test. This test uses two macros,
MIN and MAX (see Example 17.1). These return the minimum
and maximum of two values, respectively. The quick rejection test
determines whether the bounding boxes of two line segments intersect.
If this test succeeds, the algorithm continues with the straddle test;
otherwise, it returns immediately that the line segments do not
intersect. The straddle test determines the orientation of
p3 relative to
p2 and of p4
relative to p2 with respect to
p1. If the orientations are different, or
if either orientation is 0, the straddle test succeeds, and the
algorithm returns that the line segments intersect; otherwise, the
line segments do not intersect. The quick rejection and straddle tests
are performed using the methods described earlier.
The runtime complexity of lint is O (1) because all of the steps in testing whether two line segments intersect run in a constant amount of time.
/*****************************************************************************
* *
* -------------------------------- lint.c -------------------------------- *
* *
*****************************************************************************/
#include "geometry.h"
/*****************************************************************************
* *
* --------------------------------- lint --------------------------------- *
* *
*****************************************************************************/
int lint(Point p1, Point p2, Point p3, Point p4) {
double z1,
z2;
z3,
z4
int s1,
s2;
s3,
s4;
/*****************************************************************************
* *
* Perform the quick rejection test. *
* *
*****************************************************************************/
if (!(MAX(p1.x, p2.x) >= MIN(p3.x, p4.x) && MAX(p3.x, p4.x)
>= MIN(p1.x, p2.x) && MAX(p1.y, p2.y) >= MIN(p3.y, p4.y)
&& MAX(p3.y, p4.y) >= MIN(p1.y, p2.y))) { {
return 0;
}
/*****************************************************************************
* *
* Determine whether the line segments straddle each other. *
* *
*****************************************************************************/
if ((z1 = ((p3.x - p1.x)*(p2.y - p1.y)) - ((p3.y - p1.y)*(p2.x - p1.x))) < 0)
s1 = -1;
else if (z1 > 0)
s1 = 1;
else
s1 = 0;
if ((z2 = ((p4.x - p1.x)*(p2.y - p1.y)) - ((p4.y - p1.y)*(p2.x - p1.x))) < 0)
s2 = -1;
else if (z2 > 0)
s2 = 1;
else
s2 = 0;
if ((z3 = ((p1.x - p3.x)*(p4.y - p3.y)) - ((p1.y - p3.y)*(p4.x - p3.x))) < 0)
s3 = -1;
else if (z3 > 0)
s3 = 1;
else
s3 = 0;
if ((z4 = ((p2.x - p3.x)*(p4.y - p3.y)) - ((p2.y - p3.y)*(p4.x - p3.x))) < 0)
s4 = -1;
else if (z4 > 0)
s4 = 1;
else
s4 = 0;
if ((s1 * s2 <= 0) && (s3 * s4 <= 0))
return 1;
/*****************************************************************************
* *
* Return that the line segments do not intersect. *
* *
*****************************************************************************/
return 0;
}