# How can I tell whether an object is moving CW or CCW around a connected path?

Lets say we have a jagged shape:

And two creatures moving along it's outline.

Then we smooth the shape completely by pulling the corners out.

We get this:

It is easy to see now that Orange is moving CW and green CCW. How can I tell in which direction they are moving without smoothing out the shape?

New image

Draw a line to infinity and count how many times you cross the shape (even or odd), not counting the segment where the creature lies. Then check whether the creature is going left or right of that line.

In this example, we cross the shape twice (so even) and we go to the left. The result is immediate from this table:

   # Crosses | even  | odd
Direction  |       |
-------------+-------+------
left     | CCW   |  CW
right    |  CW   | CCW


In pseudocode:

x, y = position of creature
vx, vy = direction of creature movement
crossings = 0
for each x1, y1, x2, y2 in shape segments:
if (x1 < x and x <= x2) or (x2 < x and x <= x1):
if y - y1 > (x - x1) * (y2 - y1) / (x2 - x1):
++crossings
if (crossings & 1) == (vx < 0):
return CW
else
return CCW

• do you include the line creature moving on? – Ali1S232 Nov 7 '12 at 23:23
• @Gajoo: no, hence the > instead of >= at line 6. I will add a note about this. But note that you could include the line, and just reverse the table contents. – sam hocevar Nov 7 '12 at 23:24
• I was tossing up between giving an answer based on this method, and the answer which I gave. I'm glad we have both approaches represented here. This one is conceptually simpler and very elegant, but requires performing line segment intersection tests, which can be tricky to make robust. – Trevor Powell Nov 7 '12 at 23:46
• @TrevorPowell True. Finding the furthest edge could be confusing. I checked first based on the edge's most distant vertex and then I by drawing a line from the shape's center and through the two edges' centers (the two that share the vertex) and seeing if one of the lines crosses another edge on the way to infinity after crossing one of these edges. It worked out alright – wolfdawn Nov 8 '12 at 0:14

It depends on what information you have available from your shape data structure, but a creature moving CW along the outline of a shape will always have the inside of the shape on its right, and a creature moving CCW will have the inside of the shape on its left.

• A much simpler solution, and also my first thought. – Amplify91 Nov 7 '12 at 23:17
• how do you know which direction is inside of the shape? I mean moving along an edge inside of the shape is either on your left or on your right. how do you know which way it is? – Ali1S232 Nov 7 '12 at 23:19
• A very elegant solution, but not true in general. Imagine a doughnut, flattened on a table to make a two-dimensional shape. You can walk along the edge of this shape, keep the inside of the shape on your left and make either a clockwise or a counter-clockwise lap depending on where you started. – Marcks Thomas Nov 8 '12 at 16:35
1. Calculate the center point of your shape.
2. Pick the most distant edge of your shape from the center.
• (Picking the most distant edge ensures that you don't start from an inverted, concave part of the shape, which would result in getting the clockwise/anticlockwise determination backward for the whole shape)
3. Determine which direction along that edge is clockwise
• (A simple implementation of this would involve comparing the angles from the center of the shape to each end of the selected edge. The sign of the difference between the angles will tell your clockwise vs. counter-clockwise)
4. Iterate over all the edges of the shape, starting from the edge you picked in step 2, building a list of edges. For each edge, store its two vertices in clockwise order.
• (If your shape isn't changing over time, then you can store this edge list for later use, so you don't have to do the first four steps every frame)
• (you may already have an edge list. If so, you can store this clockwise vertex order in that same list.)
5. To determine whether an entity is moving clockwise or anticlockwise:
• Determine which edge the entity is moving along.
• Do a dot product of the entity's direction of movement against the vector from that edge's clockwise start->end vertices which you determined back in step 4.
• If the result of the dot product is a value greater than zero, the entity is moving clockwise. Less than zero means anticlockwise.
• Very clever answer – wolfdawn Nov 7 '12 at 22:50
• I've got a little question? assuming vertices in his shape are numbered starting from the most left point CWW, based on your answer how can I tell if moving from 6->7 or 9->10 (zero based) is moving clockwise? – Ali1S232 Nov 7 '12 at 23:08
• You start with the most distant edge, and figure out which way is clockwise on that edge. Let's say that edge A is clockwise from vertex 'a' to 'b'. Then if we move to edge B (which has vertices 'b' and 'c'), we know that B is clockwise from 'b' to 'c'. Similarly, edge C is going to be clockwise from 'c' to 'd'. Once we know the correct clockwise direction from one edge (steps 1-3), by continuing in that clockwise direction around the shape's edges we can deduce the correct 'clockwise' direction for every edge, without actually looking at where its edges are located, so concavity is ok. – Trevor Powell Nov 7 '12 at 23:15
• how can you tell if edge A is clockwise from 'a' to 'b' or if it's clockwise from 'b' to 'a'? I think you missed that part. – Ali1S232 Nov 7 '12 at 23:30
• @Gajoo That's the parenthetical point on step 3. Probably shouldn't be parenthetical, since it's really the critical step of the whole process. – Trevor Powell Nov 7 '12 at 23:40

You need to know which way round the polygon is defined, which way the vertices go round it.

If you don't know this, you can work it out by calculating the area of the polygon:

float Polygon::area() {
float result = 0.0f;

for(int a = 0; a < vertexCount; a ++) {
int b = (a+1) % vertexCount;
result += vertices[a].x * vertices[b].y;
result -= vertices[a].y * vertices[b].x;
}

return result * .5f;
}


The sign of the result (positive or negative) will tell you whether it is clockwise or anticlockwise. You need to try this to see which way round it is for you because it depends on your coordinate system.

If the shape is clockwise:

• A creature going forward round the shape is going clockwise, and
• A creature going backward round the shape is going anticlockwise.

If the shape is anticlockwise:

• A creature going forward round the shape is going anticlockwise, and
• A creature going backward round the shape is going clockwise.

It seems Trevor already covered this question, but here is my solution:

1. compute the area your shape covers, meaning

area = 0
foreach (edge in shape)
area += edge.begin.x * edge.end.y - edge.begin.y * edge.end.x

2. using area computed as above you can easily tell if the shape itself is clockwise or not. it's clockwise only if area is below zero.

3. check if object(s) is(are) moving the same way as vertices are order or in the opposite direction.

• – Trevor Powell Nov 7 '12 at 23:27