Right and Left Turns

In my previous post on line segment intersection I introduced the two dimensional cross product as v1 \times v2 = {v1}_x \cdot {v2}_y - {v2}_x \cdot {v1}_y. The cross product can also be used to determine if a set of three points p_1, p_2, \textrm{ and } p_3 make a right turn.

First note that if v_1 \times v_2 > 0 then the angle between v_1 and v_2 is strictly less than \pi. For example the two vectors (1, 0) \times (0, 1) = 1 \cdot 1 - 0 = 1 > 0. Similarly if v_1 \times v_2 < 0 then the angle between them is strictly greater than \pi. In the below image I've shown an example where the three points p_1, p_2, \textrm{ and } p_3 make a right turn.

Points p1, p2, p3 making a right turn

To mathematically determine if the points make a right turn we let v_1 = p_1 - p_2 \textrm{ and } v_2 = p_3 - p_2. Then taking the cross product of v_1 \textrm{ and } v_2, we have v_1 \times v_2 > 0 which implies that the angle between them is less than \pi that is they make a right turn.

This method for determining whether the points make a right or left turn is very useful for determining the convex hull of a set of points.

I’ve posted an example webpage, here, where using javascript the lines change color depending on whether the turn is to the right or the left. Please note that the page uses the html5 canvas element so it will not work in internet explorer 7, or 6.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s