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

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.