SKEDSOFT

Design Analysis Of Algorithm

Line-segment properties: Several of the computational-geometry algorithms in this chapter will require answers to questions about the properties of line segments. A convex combination of two distinct points p1 = (x1, y1) and p2 = (x2, y2) is any point p3 = (x3, y3) such that for some α in the range 0 ≤ α ≤ 1, we have x3 = αx1 (1 - α)x2 and y3 = αy1 (1 - α)y2. We also write that p3 = αp1 (1 - α)p2. Intuitively, p3 is any point that is on the line passing through p1 and p2 and is on or between p1 and p2 on the line. Given two distinct points p1 and p2, the line segment is the set of convex combinations of p1 and p2. We call p1 and p2 the endpoints of segment . Sometimes the ordering of p1 and p2 matters, and we speak of the directed segment . If p1 is the origin (0, 0), then we can treat the directed segment as the vector p2.

In this section, we shall explore the following questions:

  1. Given two directed segments and , is clockwise from with respect to their common endpoint p0?

  2. Given two line segments and , if we traverse and then , do we make a left turn at point p1?

  3. Do line segments and intersect?

There are no restrictions on the given points.

We can answer each question in O(1) time, which should come as no surprise since the input size of each question is O(1). Moreover, our methods will use only additions, subtractions, multiplications, and comparisons. We need neither division nor trigonometric functions, both of which can be computationally expensive and prone to problems with round-off error. For example, the "straightforward" method of determining whether two segments intersect-compute the line equation of the form y = mx b for each segment (m is the slope and b is the y-intercept), find the point of intersection of the lines, and check whether this point is on both segments-uses division to find the point of intersection. When the segments are nearly parallel, this method is very sensitive to the precision of the division operation on real computers. The method in this section, which avoids division, is much more accurate.

Cross products: Computing cross products is at the heart of our line-segment methods. Consider vectors p1 and p2, shown in Figure 33.1(a). The cross product p1 × p2 can be interpreted as the signed area of the parallelogram formed by the points (0, 0), p1, p2, and p1 p2 = (x1 x2, y1 y2). An equivalent, but more useful, definition gives the cross product as the determinant of a matrix:

Figure 33.1: (a) The cross product of vectors p1 and p2 is the signed area of the parallelogram. (b) The lightly shaded region contains vectors that are clockwise from p. The darkly shaded region contains vectors that are counterclockwise from p.

If p1 × p2 is positive, then p1 is clockwise from p2 with respect to the origin (0, 0); if this cross product is negative, then p1 is counterclockwise from p2. Figure 33.1(b) shows the clockwise and counterclockwise regions relative to a vector p. A boundary condition arises if the cross product is 0; in this case, the vectors are collinear, pointing in either the same or opposite directions.

To determine whether a directed segment is clockwise from a directed segment with respect to their common endpoint p0, we simply translate to use p0 as the origin. That is, we let p1 - p0 denote the vector , where and , and we define p2 - p0 similarly. We then compute the cross product

(p1 - p0) × (p2 - p0) = (x1 - x0)(y2 - y0) - (x2 - x0)(y1 - y0).

If this cross product is positive, then is clockwise from ; if negative, it is counterclockwise.

Determining whether consecutive segments turn left or right: Our next question is whether two consecutive line segments and turn left or right at point p1. Equivalently, we want a method to determine which way a given angle ∠ p0p1p2 turns. Cross products allow us to answer this question without computing the angle. As shown in Figure 33.2, we simply check whether directed segment is clockwise or counterclockwise relative to directed segment . To do this, we compute the cross product (p2 - p0) × (p1 - p0). If the sign of this cross product is negative, then is counterclockwise with respect to , and thus we make a left turn at p1. A positive cross product indicates a clockwise orientation and a right turn. A cross product of 0 means that points p0, p1, and p2 are collinear.


Figure 33.2: Using the cross product to determine how consecutive line segments and turn at point p1. We check whether the directed segment is clockwise or counterclockwise relative to the directed segment . (a) If counterclockwise, the points make a left turn. (b) If clockwise, they make a right turn.