Mastering Algorithms With C - Kyle Loudon [216]
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.
Example 17.2. Implementation for Testing Whether Line Segments Intersect
/*****************************************************************************
* *
* -------------------------------- 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;
}
Description of Convex Hulls
The convex hull of a set of points is the smallest convex polygon that encloses all points in the set. A polygon is convex if any line segment connecting two points inside the polygon lies completely inside the polygon itself (see Figure 17.3a); otherwise, the polygon is concave (see Figure 17.3b). To picture the convex hull for a set of points, imagine a series of pegs on a board. If we wrap a string tightly around the outermost pegs, the shape of the string is the convex hull.
Figure 17.3. (a) A convex polygon and (b) a concave polygon
Jarvis's March
One way to construct the convex hull for a set of points P is to use a method called Jarvis's march. Jarvis's march constructs a convex hull in two sections, called the right chain and left chain. The right chain consists of all points in the convex hull from the lowest point (the one with the smallest y-coordinate) to the highest. If two points are equally low, the lowest point is considered to be the one that is also the furthest to the left (the one with the smallest x-coordinate). The left chain consists of all points from the highest point back to the lowest. If two points are equally high, the highest point is considered to be the one that is also the furthest to the right.
We begin by finding the lowest point in P (as described a moment ago), adding it to the convex hull, and initializing another variable, p 0, to it. Next, we look at each point pi in P, excluding p 0, and locate the point pc that is clockwise from all others with respect to p 0. Picture a clock face centered on p 0. In the right chain, we start at the 3 o'clock position and sweep counterclockwise until we encounter a point. In the left