Using the cross product to determine the orientation of edges and points in 2D

The cross product is an extremely valuable tool when doing geometric calculations. One of the many uses of it is it determine whether a point is to the left of an edge or to the right of an edge (also referred to as counter clockwise or clockwise).

cross product

 

Let’s consider the edge OA, and the point B as the edge and the point we would like to determine the orientation of.

To start, let’s connect B to O, to form OB, and then take the cross product OA with respect to OB, i.e. OA x OB. This will always be positive if B is on the left (or CCW) with respect to OA.

350px-Right-hand_grip_rule

Now, if we use the righthand corkscrew rule (which can be used to determine the direction of the vector in Z dimension) and curve our fingers in the direction of OA to OB, i.e. the direction if OA was rotated around O on to OB, we see that our thumb point upwards. Based on the convention that upwards is positive, you can easily see why the cross product works. If we, do the same from OA to OC, you will see that we have to twist our hand and the thumb point downwards. Thus, if the point is on to the right of OA (ex: C), the cross product will always be negative.

One of the uses of this is when your constructing a spatial graph (such as a road network), and you want to determine the order of edges in CW or CCW order around a vertex (or point). Then if you take the cross products between a chosen edge against all the other edges, and sort them in a descending manner according to the cross product value, the edges will be sorted in a CCW order. This happens because the value of the cross product will be highest, i.e. largest positive value at the edge that will be closest to 180 degrees, relative to the chosen edge, and lowest at the edge just adjacent to the largest positive edge, but in the CW order. This property aligns itself nicely, when a sorting of the edges are needed. And since the cross product is a very fast to compute, it will perform fast as well for interactive applications.

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