In Part 1 we discussed the base technique for determining relative orientation. We used that to answer the first two questions: To find relative orientation of two points and two directed segments with a common end point. In Part 2 we answer the next two questions:

- Given two line segments p
_{0}p_{1}and p_{1}p_{2}, if we traverse from p_{0}to p_{2}, did we make a left, right or no turn at p_{1}? - Do line segments p
_{1}p_{2}and p_{3}p_{4}intersect?

We build on what we learned in Part 1, the **cross product**.

Download the demo application here

**Determining whether consecutive segments turn left or right**

Given two line segments p_{0}p_{1} and p_{1}p_{2} we simply check whether the directed segment p_{0}p_{2} is clockwise or counterclockwise relative to directed segment p_{0}p_{1}. This is similar to the solution to question 2 in Part 1. If the cross product is negative, then p_{0}p_{2} is counterclockwise to p_{0}p_{1}. Hence we should turn **left** when we reach p_{1} to reach p_{2} while traversing p_{0}, p_{1} and p_{2}. If the cross product is **0** (boundary condition) then it means all the three points are **collinear** (on the same line). The image below shows the three possible scenarios

**Determining whether two line segments intersect**

Two line segments intersect if and only if either or both of the following conditions are true:

- Each line segment straddles the other line segment.
- An end point of one line segment is on the other line segment

A line segment p_{1}p_{2} **straddles** another line if p_{1} and p_{2} are on opposite sides of the line. A boundary condition occurs when one of the end points is **on** the other line.

**Algorithm**

Calculate the orientation (using cross product!) d_{i} for each point of one segment w.r.t the end points of the other segment. For line segments p_{1}p_{2} and p_{3}p_{4} we will get d_{1}, d_{2}, d_{3} and d_{4}.

if none of the d_{i} are collinear (i.e. d_{i} !=0) we check if d_{1} and d_{2} **and** d_{3} and d_{4} have opposite orientations (if one is clockwise,other should be counterclockwise). If this condition is true then we know that the line segments **straddle** each other and hence **intersect**. If it is false we can straight away say they **don’t intersect**.

If any d_{i} is collinear (boundary condition) and the corresponding p_{i} is **on** the other line segment, the lines **intersect**.

bool Intersects(p_{1}, p_{2}, p_{3}, p_{4}) { d_{1}= CrossProduct (p_{1}p_{3}, p_{1}p_{2}) d_{2}= CrossProduct (p_{1}p_{4}, p_{1}p_{2}) d_{3}= CrossProduct (p_{3}p_{1}, p_{3}p_{4}) d_{4}= CrossProduct (p_{3}p_{2}, p_{3}p_{4}) if( ((d_{1}> 0 and d_{2}<0) or (d_{2}> 0 and d_{1}<0))and((d_{3}> 0 and d_{4}<0) or (d_{4}> 0 and d_{3}<0))) { then returntrue} else if (d_{1}= 0andPointOnLine (p_{3}, p_{4}, p_{1})) { then returntrue} else if (d_{2}= 0andPointOnLine (p_{3}, p_{4}, p_{2})) { then returntrue} else if (d_{3}= 0andPointOnLine (p_{1}, p_{2}, p_{3})) { then returntrue} else if (d_{4}= 0andPointOnLine (p_{1}, p_{2}, p_{4})) { then returntrue} else { returnfalse} } bool PointOnLine (p_{i}, p_{j}, p_{k}) { if ( Min (x_{i}, x_{j})<= x_{k}<= Max (x_{i}, x_{j})andMin (y_{i}, y_{j})<= y_{k}<= Max (y_{i}, y_{j}) ) { returntrue} else { returnfalse} }