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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def subtract(self, p):
    	return Point(self.x - p.x, self.y - p.y)

    def __str__(self):
        return '(' + str(self.x) + ', ' + str(self.y) + ')'

# calculates the cross product of vector p1 and p2
# if p1 is clockwise from p2 wrt origin then it returns +ve value
# if p2 is anti-clockwise from p2 wrt origin then it returns -ve value
# if p1 p2 and origin are collinear then it returs 0
def cross_product(p1, p2):
	return p1.x * p2.y - p2.x * p1.y

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
2
3
4
5
6

# returns the cross product of vector p1p3 and p1p2
# if p1p3 is clockwise from p1p2 it returns +ve value
# if p1p3 is anti-clockwise from p1p2 it returns -ve value
# if p1 p2 and p3 are collinear it returns 0
def direction(p1, p2, p3):
	return  cross_product(p3.subtract(p1), p2.subtract(p1))

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
2
3

# checks if p3 makes left turn at p2
def left(p1, p2, p3):
	return direction(p1, p2, p3) < 0

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
2
3

# checks if p3 makes right turn at p2
def right(p1, p2, p3):
	return direction(p1, p2, p3) > 0

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
2
3

# checks if p1, p2 and p3 are collinear
def collinear(p1, p2, p3):
	return direction(p1, p2, p3) == 0

References

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