Linesegment Properties
Linesegment properties: Several of the computationalgeometry algorithms in this chapter will require answers to questions about the properties of line segments. A convex combination of two distinct points p_{1} = (x_{1}, y_{1}) and p_{2} = (x_{2}, y_{2}) is any point p_{3} = (x_{3}, y_{3}) such that for some α in the range 0 ≤ α ≤ 1, we have x_{3} = αx_{1} (1  α)x_{2} and y_{3} = αy_{1} (1  α)y_{2}. We also write that p_{3} = αp_{1} (1  α)p_{2}. Intuitively, p_{3} is any point that is on the line passing through p_{1} and p_{2} and is on or between p_{1} and p_{2} on the line. Given two distinct points p_{1} and p_{2}, the line segment is the set of convex combinations of p_{1} and p_{2}. We call p_{1} and p_{2} the endpoints of segment . Sometimes the ordering of p_{1} and p_{2} matters, and we speak of the directed segment . If p_{1} is the origin (0, 0), then we can treat the directed segment as the vector p_{2}.
In this section, we shall explore the following questions:

Given two directed segments and , is clockwise from with respect to their common endpoint p_{0}?

Given two line segments and , if we traverse and then , do we make a left turn at point p_{1}?

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 roundoff error. For example, the "straightforward" method of determining whether two segments intersectcompute the line equation of the form y = mx b for each segment (m is the slope and b is the yintercept), find the point of intersection of the lines, and check whether this point is on both segmentsuses 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 linesegment methods. Consider vectors p_{1} and p_{2}, shown in Figure 33.1(a). The cross product p_{1} × p_{2} can be interpreted as the signed area of the parallelogram formed by the points (0, 0), p_{1}, p_{2}, and p_{1} p_{2} = (x_{1} x_{2}, y_{1} y_{2}). An equivalent, but more useful, definition gives the cross product as the determinant of a matrix:
If p_{1} × p_{2} is positive, then p_{1} is clockwise from p_{2} with respect to the origin (0, 0); if this cross product is negative, then p_{1} is counterclockwise from p_{2}. 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 p_{0}, we simply translate to use p_{0} as the origin. That is, we let p_{1}  p_{0} denote the vector , where and , and we define p_{2}  p_{0} similarly. We then compute the cross product
(p_{1}  p_{0}) × (p_{2}  p_{0}) = (x_{1}  x_{0})(y_{2}  y_{0})  (x_{2}  x_{0})(y_{1}  y_{0}).
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 p_{1}. Equivalently, we want a method to determine which way a given angle ∠ p_{0}p_{1}p_{2} 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 (p_{2}  p_{0}) × (p_{1}  p_{0}). If the sign of this cross product is negative, then is counterclockwise with respect to , and thus we make a left turn at p_{1}. A positive cross product indicates a clockwise orientation and a right turn. A cross product of 0 means that points p_{0}, p_{1}, and p_{2} are collinear.
Figure 33.2: Using the cross product to determine how consecutive line segments and turn at point p_{1}. 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.