• Choose a category
• All
• Classic-Fiction

* *

*****************************************************************************/

#define DEGTORAD(deg) (((deg) * 2.0 * PI) / 360.0)

#define RADTODEG(rad) (((rad) * 360.0) / (2.0 * PI))

/*****************************************************************************

* *

* Define a structure for points in rectilinear coordinates. *

* *

*****************************************************************************/

typedef struct Point_ {

double x,

y,

z;

} Point;

/*****************************************************************************

* *

* Define a structure for points in spherical coordinates. *

* *

*****************************************************************************/

typedef struct SPoint_ {

double rho,

theta,

phi;

} SPoint;

/*****************************************************************************

* *

* --------------------------- Public Interface --------------------------- *

* *

*****************************************************************************/

int lint(Point p1, Point p2, Point p3, Point p4);

int cvxhull(const List *P, List *polygon);

void arclen(SPoint p1, SPoint p2, double *length);

#endif

Description of Testing Whether Line Segments Intersect

One fundamental problem in computational geometry is determining whether two line segments intersect. Line segments are lines that have a beginning and an end. The points that define either end are a line segment's endpoints . To determine whether two line segments intersect, we first need to understand a little about lines and line segments in general.

One representation of a line is point-intercept form , or y = mx + b, where m is the line's slope and b is where the line crosses the y-axis. Using this, for any value of x, we can compute a corresponding value for y (see Figure 17.1a). For a line segment with endpoints p 1 = (x 1, y 1) and p 2 = (x 2, y 2), the slope m and y-intercept b are calculated by applying the following formulas:

Using m and b, the line segment is represented as a line in point-intercept form with endpoints p 1 and p 2 understood (see Figure 17.1b).

Figure 17.1. (a) A line and (b) a line segment with endpoints p1 and p2

Standard Test for Intersecting Line Segments

One way to determine whether two line segments intersect is first to determine the intersection point pi = (xi , y i ) of the two lines on which each segment lies, then determine whether pi is on both segments. If pi is on both segments, the line segments intersect. We start with the point-intercept representations of the two lines on which the segments lie, which are:

The following formulas are used to compute pi = (xi , y i ). Notice that one special case we must avoid when computing xi is two lines with slopes that are equal. In this case, the denominator in the expression for xi becomes 0. This occurs when two lines are parallel, in which case the segments will not intersect unless they lie on top of one another to some extent.

Once we've computed pi , we perform the following tests to determine whether the point is actually on both line segments. In these tests, p 1 = (x 1, y 1) and p 2 = (x 2, y 2) are the endpoints of one line segment, and p 3 = (x 3, y 3) and p 4 = (x 4, y 4 ) are the endpoints of the other. If each of the tests is true, the line segments intersect.

This approach is common for determining whether line segments intersect. However, because the division required while calculating xi is prone to round-off error and precision problems, in computing we take a different approach.

Computer Test for Intersecting Line Segments

In computing, to determine whether two lines intersect, a two-step process is used: first, we perform a quick rejection test. If this test succeeds, we then perform a straddle test. Two line segments intersect only when the quick rejection test and straddle test both succeed.

We begin the quick rejection test by constructing a bounding box around each line segment. The bounding box of a line segment is the smallest