## Introduction

To get the intuition of what is left and what is right turn, consider an example shown below.

In both figures, there are three points $p_1$, $p_2$ and $p_3$ and two line segments $\overline{p_1p_2}$ and $\overline{p_2p_3}$. Point $p_2$ is common to both the line segments. In figure (a), segment $\overline{p_2p_3}$ is making a right turn at point $p_2$ whereas in figure (b), segment $\overline{p_2p_3}$ is making a left turn at the common point $p_2$. It is easier for our eyes to quickly identify whether a segment is making a left turn or a right turn just looking at the figure because your eyes have natural ability to identify things very fast. In this post I shall talk about how the computers identify this using geometric algorithms.

## Algorithm

### Cross Product of two points

Given two points $p_1(x_1, y_1)$ and $p_2(x_2, y_2)$, we need to first determine whether point $p_1$ is clockwise or is anti-clockwise from point $p_2$ with respect to origin. One way of solving this problem is by calculating the angle made by both $\overline{p_1}$ and $\overline{p_2}$ with $x$-axis and the difference in the angle can tell whether one point is clockwise or anti-clockwise from other. There is an easier and efficient solution to this than finding the angle which is calculating the **cross product** of the vector $\overline{p_1}$ and $\overline{p_2}$. Mathematically the cross product of two vectors $\overline{p_1}$ and $\overline{p_2}$ is given by

$$ p_1 \times p_2 = x_1y_2 - x_2y_1$$

If the value of $p_1 \times p_2$ is positive then $p_1$ is clockwise from $p_2$ with respect to origin as shown in the figure below.

Similarly, if $p_1 \times p_2$ is negative then $p_1$ is anti-clockwise from $p_2$ with respect to origin and if the value is 0 then points $p_1$, $p_2$ and origin are collinear. Following python code implements the cross product.

1 | class Point: |

### Cross product of two segments

Consider two segments whose end points are $p_1(x_1, y_1)$, $p_2(x_2, y_2)$ and $p_1(x_1, y_1)$, $p_3(x_3, y_3)$ respectively. In order to calculate the cross product of two segments, we need to convert them into the vectors. This can be done in the following way.

$$\overline{p_1p_2} = (x_2 - x_1, y_2 - y_1), \overline{p_1p_3} = (x_3 - x_1, y_3 - y_1)$$

Once we have two two vectors, we can call `cross_product`

to calculate the cross product as shown in the code below.

1 | # returns the cross product of vector p1p3 and p1p2 |

### Left turn

To determine if a segment $p_2p_3$ turns left from a segment $p_1p_2$ at point $p_2$, we draw a next vector $\overline{p_1p_3}$ and check if the new vector is anti-clockwise from a vector $\overline{p_2p_3}$. This is illustrated in the figure below.

Figure in the right shows vector $\overline{p_1p_3}$ is anti-clockwise from vector $\overline{p_1p_2}$ and therefore we can say that the segment $p_2p_3$ turns left from segment $p_1p_2$ at point $p_2$. The python implementation is given below.

1 | # checks if p3 makes left turn at p2 |

### Right turn

This is same as the left turn the only difference is the vector $\overline{p_1p_3}$ is clockwise from vector $\overline{p_2p_3}$. The python implementation is given below.

1 | # checks if p3 makes right turn at p2 |

### Collinear

One special case arises when the method `direction`

returns neither positive value nor negative value but zero. In this case, all the points $p_1$, $p_2$ and $p_3$ lies on the same line. In this case segment $p_2p_3$ doesn’t turn to any direction.

1 | # checks if p1, p2 and p3 are collinear |

## References

- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (n.d.). Introduction to algorithms (3rd ed.). The MIT Press.