Wednesday, October 23, 2013

How to Determine the Rotation Direction of a List of 3 Points in 2D

Clockwise and counter-clockwise are directions which are fairly intuitive to most of us. But if you were not so smart—say perhaps about the intelligence of a computer—how would you know whether a list of three points had been listed in clockwise or counter-clockwise order?

If you were given 3 points (in 2D) and asked this question about them, you would probably do the same type of thing I would: plot them, perhaps put numbers beside them, sort of trace the points in the air with your finger and ask yourself, "Am I moving my finger clockwise or counter-clockwise?"

For example, are these points given as clockwise or counter-clockwise?
If you figured out which direction they are numbered in (CW vs. CCW), you likely used your hands or at least mentally traced it and imagined it as (or compared it to) a movement.

Computers, unfortunately for them (fortunately for us maybe), don't have hands.  And if they did, you would have to explain to them the significance of their actions and I imagine that being a bit complicated.  Better get them to use math. Way easier!

If we draw a couple of arrows, the matter is easier to see.
What makes the above traversal of points clockwise, is that every turn is a right turn.  If I am travelling from 1 to 2 and then I turn to go from 2 to 3, I must turn myself right, or clockwise.  The direction from 1 to 2 can be stated as D1 = P2 – P1 and the direction from 2 to 3 as D2 = P3 – P2 (if you'll allow the introduction of some letters).  One way to test for whether the direction D2 is a right turn from D1 is to rotate the points so that the line from 1 to 2 is at standard position and then inspect the rotated version of D2 for which quadrant it is in.  (Implicit to the problem is that we are disallowing turns greater than or equal to 180°.  If this seems to you like weaseling or a limitation of the method, revisit the first picture and remind yourself what the question really is.)

Rotating the points produces the following (roughly).

So now it is pretty clear.  If we rotate D2 by an angle sufficient to bring D1 to standard position, we can identify a right turn by a negative y value in the rotated version of D2 (quadrant 3 or 4) and a left turn by a positive y value (quadrant 1 or 2).  What remains is a method of rotation.

Consider the complex representation of the direction vectors (where r1 and r2 are positive):
We are concerned only with direction and so the change in magnitude is not a concern.  If the imaginary part of this last number is negative, then the points are in clockwise order.  If the imaginary part is positive, then the points are in counter-clockwise order.

Note also that we have avoided any calls to trigonometric functions by using this method.  The trig functions show in the derivation as a matter of proof, but are not actually called at run-time.

Additional info: I later found a numerically less involved method in Introduction to Algorithms (Thomas H. Cormen, et. al.). Just take the cross-product, retaining only the z-coordinate (x and y are 0 anyway).  Instead of considering vectors from (1 to 2) and (2 to 3), take (1 to 2) versus (1 to 3). The determination is still made based on the sign of the sine, but now it is the sine of the angle between the vectors.

No comments: