Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Lets say we have a jagged shape:

shape0

And two creatures moving along it's outline.

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

We get this:

smooth

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

enter image description here

share|improve this question
    
Here is my 2 cents: i.imgur.com/zrBdw.png –  Kendall Frey Nov 8 '12 at 17:34

5 Answers 5

up vote 25 down vote accepted

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.

example

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
share|improve this answer
    
do you include the line creature moving on? –  Ali.S 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
1  
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 –  Zehelvion 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.

share|improve this answer
    
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? –  Ali.S 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.
share|improve this answer
    
Very clever answer –  Zehelvion 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? –  Ali.S 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. –  Ali.S 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.
share|improve this answer

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.

share|improve this answer
    
Related: stackoverflow.com/questions/1165647/… –  Trevor Powell Nov 7 '12 at 23:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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