 Determining if two consecutive line segments turn left or right

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.

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.

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.

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.

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. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (n.d.). Introduction to algorithms (3rd ed.). The MIT Press.