3
$\begingroup$

Given a directed cycle in the plane I need to walk it and detect whether it is clockwise or counterclockwise.

My first idea is to gather the sum of the turn angles, where a "left" turn is a negative angle, and a "right" turn is a positive angle. If I go with this one, I need a good way to calculate the angle between two vectors, and also which sign this angle should have (+/-).

Even if I had the right tools to calculate the (+/-) angle I feel like this could be done simpler.c

$\endgroup$
5
  • $\begingroup$ Looks like a homework problem. $\endgroup$
    – Tunococ
    Oct 29, 2010 at 10:16
  • $\begingroup$ So it does! It's not, though. (depending on a fitting definition of homework) $\endgroup$ Oct 29, 2010 at 10:24
  • $\begingroup$ Assuming the cycle is embedded: Walk along the cycle once to find any rightmost vertex, $v$. At $v$, the exiting edge is (above) below the entering edge iff the cycle is (counter) clockwise. $\endgroup$
    – Sam Nead
    Oct 29, 2010 at 11:24
  • $\begingroup$ Ok, it is more precise to say that the entering and exiting edges form two angles, one of these angles is "to the left" and the arrangement of the edges about the left angle tells you what you want. $\endgroup$
    – Sam Nead
    Oct 29, 2010 at 11:28
  • $\begingroup$ You can calculate the signed area of the polygon and check if it is positive or negative. $\endgroup$
    – Jules
    Oct 28, 2016 at 11:27

1 Answer 1

5
$\begingroup$

The orientation of a triangle (clockwise/counterclockwise) is the sign of the determinant $\begin{bmatrix} 1&x_1&y_1\\\\ 1&x_2&y_2\\\\ 1&x_3&y_3 \end{bmatrix}$, where $(x_1,y_1), (x_2,y_2), (x_3,y_3)$ are the Cartesian coordinates of the three vertices of the triangle.

$\endgroup$
2
  • $\begingroup$ Let me get this straight. What you're saying is that I can check whether the angle between any two "connected" vectors in the cycle by viewing them as forming a triangle. That seems to work! (unless they're bearing the same direction of course) So my initial idea is not as bad as I thought? $\endgroup$ Oct 29, 2010 at 10:16
  • $\begingroup$ If u is the vector of x-coordinates and v is the vector of y-coordinates, then this determinant is equal to the dot product of u cross v with the vector of all 1s? $\endgroup$ Oct 28, 2016 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.