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.

If you have a 2D vector expressed as x and y, what's a good way of translating that into the closest compass direction?

e.g.

x:+1,  y:+1 => NE
x:0,   y:+3 => N
x:+10, y:-2 => E   // closest compass direction
share|improve this question
    
do you want it as a string or an enum? (yes, it matters) –  Philipp Feb 13 '13 at 16:08
    
Either, since it will be used both ways :) Though if I had to pick, I'd take a string. –  izb Feb 13 '13 at 16:10
1  
Are you concerned about the performance as well, or only about conciseness? –  Marcin Seredynski Feb 13 '13 at 16:59
1  
var angle = Math.atan2(y, x); return <Direction>Math.floor((Math.round(angle / (2 * Math.PI / 8)) + 8 + 2) % 8); I use this one –  Kikaimaru Feb 14 '13 at 10:53
    
Concise : marked by brevity of expression or statement : free from all elaboration and superfluous detail. Just throwing that out there... –  Dialock Feb 14 '13 at 18:56
add comment

7 Answers

Not sure if it's bad form to answer your own question, but I managed to come up with an alternative solution that doesn't use atan or anything beyond simple arithmetic...

The key was to realise you don't need to know the angle of the vector - only the gradient.

// Vector is in dx,dy

var gradientNS = tan(22.5);    // degrees. calculate once (tan, not atan)
var gradientEW = 1/gradiendNS; // calculate once

if (dy==0) {
    /* Special case avoiding division by 0 */
    if (dx==0) {
        /* Then direction does not change */
    } else {
        d = dx>0?'e':'w';
    }
} else {
    var r = dx/dy; /* Calculate slope */
    if (r>=0) {
        if (r < gradientNS) {
            d = dy>0?'s':'n';
        } else if(r > gradientEW) {
            d = dx>0?'e':'w';
        } else {
            d = dx>0?'se':'nw';
        }
    } else {
        if (r > -gradientNS) {
            d = dy>0?'s':'n';
        } else if(r < -gradientEW) {
            d = dx>0?'e':'w';
        } else {
            d = dx>0?'ne':'sw';
        }
    }
}

// direction is in 'd'

Not sure if it can be written more concisely, but it works.

share|improve this answer
    
It's perfectly OK to answer your own question. But I would consider not using atan2 to be a bad decision; your code is a lot longer and difficult to understand. It's also... very wrong: where did you get these 0.5 and 2 values? You would probably need sqrt(2)/2 and sqrt(2)+1 instead. –  Sam Hocevar Feb 14 '13 at 11:30
    
Yeah, 2 & 0.5 comes from splitting a square into equal segments along each edge instead of a circle. I'll tweak those figures.. –  izb Feb 14 '13 at 12:03
    
Tweaked with proper numbers –  izb Feb 14 '13 at 12:17
    
man that is ugly code... so many constants. bleg –  GameDev-er Feb 15 '13 at 22:26
    
Removed magic constants from inline code. –  izb Feb 17 '13 at 8:59
add comment

this seems to work:

public class So49290 {
    int piece(int x,int y) {
        double angle=Math.atan2(y,x);
        if(angle<0) angle+=2*Math.PI;
        int piece=(int)Math.round(n*angle/(2*Math.PI));
        if(piece==n)
            piece=0;
        return piece;
    }
    void run(int x,int y) {
        System.out.println("("+x+","+y+") is "+s[piece(x,y)]);
    }
    public static void main(String[] args) {
        So49290 so=new So49290();
        so.run(1,0);
        so.run(1,1);
        so.run(0,1);
        so.run(-1,1);
        so.run(-1,0);
        so.run(-1,-1);
        so.run(0,-1);
        so.run(1,-1);
    }
    int n=8;
    static final String[] s=new String[] {"e","ne","n","nw","w","sw","s","se"};
}
share|improve this answer
add comment

You have 8 options (or 16 or more if you want even finer precision).

enter image description here

Use atan2(y,x) to get the angle for your vector.

atan2() works in the following way:

enter image description here

So x=1, y=0 will result in 0, and it's discontinuous at x=-1, y=0, containing both π and -π.

Now we just need to map the output of atan2() to match that of the compass we have above.

Likely the simplest to implement is a incrementing check of angles. Here's some pseudo code that easily be modified for increased precision:

//start direction from the lowest value, in this case it's west with -π
enum direction {
west,
south,
east,
north
}

increment = (2PI)/direction.count
angle = atan2(y,x);
testangle = -PI + increment/2
index = 0

while angle > testangle
    index++
    if(index > direction.count - 1)
        return direction[0] //roll over
    testangle += increment


return direction[index]

Now to add more precision, simply add the values to the direction enum.

The algorithm works by checking increasing values around the compass to see if our angle lays somewhere between where we last checked and the new position. That's why we start at -PI + increment/2. We want to offset our checks to include equal space around each direction. Something like this:

enter image description here

West is broken in two because of the return values of atan2() at West are discontinuous.

share|improve this answer
4  
An easy way to "convert them to an angle" is to use atan2, although keep in mind that 0 degrees would probably be east and not north. –  Tetrad Feb 13 '13 at 16:39
1  
You don't need the angle >= checks in the code above; for example if the angle is less than 45 then the north will have been returned already so you don't need to check if angle >= 45 for the east check. Similarly you don't need any check at all before returning west - it's the only possibility remaining. –  MrKWatkins Feb 14 '13 at 11:43
3  
I wouldn't call this a concise way to get the direction. It seems rather clunky and will require a lot of changes to adapt this to different "resolutions". Not to speak of a ton of if statements if you want to go for 16 directions or more. –  bummzack Feb 14 '13 at 13:06
1  
No need to normalise the vector: the angle remains the same over changes in magnitude. –  Kylotan Feb 15 '13 at 14:42
    
Thanks @bummzack, I've edited the post to make it more concise and easy to increase the precision just by adding more enum values. –  Byte56 Feb 15 '13 at 15:24
show 2 more comments

Whenever you're dealing with vectors, consider fundamental vector operations instead of converting to angles in some particular frame.

Given a query vector v and a set of unit vectors s, the most-aligned vector is the vector s_i that maximizes dot(v,s_i). This is due to that the dot product given fixed lengths for the parameters has a maximum for vectors with the same direction and a minimum for vectors with opposing directions, changing smoothly inbetween.

This generalizes trivially into more dimensions than two, is extensible with arbitrary directions and doesn't suffer frame-specific problems like infinite gradients.

Implementation-wise, this would boil down to associating from a vector in each cardinal direction with an identifier (enum, string, whatever you need) representing that direction. You would then loop over your set of directions, finding the one with the highest dot product.

map<float2,Direction> candidates;
candidates[float2(1,0)] = E; candidates[float2(0,1)] = N; // etc.

for each (float2 dir in candidates)
{
    float goodness = dot(dir, v);
    if (goodness > bestResult)
    {
        bestResult = goodness;
        bestDir = candidates[dir];
    }    
}
share|improve this answer
2  
This implementation can also be written branchless and vectorized without too much trouble. –  Promit Feb 14 '13 at 16:52
1  
A map with float2 as the key? This doesn’t look very serious. –  Sam Hocevar Feb 17 '13 at 9:58
    
It's "pseudo-code" in a didactic manner. If you want panic-optimized implementations, GDSE is likely not the place to go for your copy-pasta. As for using float2 as a key, a float can exactly represent the whole numbers we use here, and you can make a perfectly good comparator for them. Floating point keys are only unsuitable if they contain special values or you try to look up computed results. Iterating over an associative sequence is fine. I could've used a linear search in an array, sure, but it'd just be pointless clutter. –  Lars Viklund Feb 18 '13 at 3:32
add comment

One way that hasn't been mentioned here is treating the vectors as complex numbers. They don't require trigonometry and can be pretty intuitive for adding, multiplying or rounding rotations, especially since you're already have your headings represented as pairs of numbers.

In case you're not familiar with them, the directions are expressed in the form of a + b(i) with a being the real component and b(i) is the imaginary. If you imagine the cartesian plane with the X being real and Y being imaginary, 1 would be east (right), i would be north.

Here is the key part: The 8 cardinal directions are represented exclusively with the numbers 1, -1 or 0 for their real and imaginary components. So all you have to do is reduce your X, Y coordinates as a ratio and round both to the closest whole number to get the direction.

NW (-1 + i)       N (i)        NE (1 + i)
W  (-1)          Origin        E  (1)
SW (-1 - i)      S (-i)        SE (1 - i)

For heading-to-nearest diagonal conversion, reduce both X and Y proportionally so the larger value is exactly 1 or -1. Set

// Some pseudocode

enum xDir { West = -1, Center = 0, East = 1 }
enum yDir { South = -1, Center = 0, North = 1 }

xDir GetXdirection(Vector2 heading)
{
    return round(heading.x / Max(heading.x, heading.y));
}

yDir GetYdirection(Vector2 heading)
{
    return round(heading.y / Max(heading.x, heading.y));
}

Rounding both components of what was originally (10, -2) gives you 1 + 0(i) or 1. So the closest direction is east.

The above doesn't actually require the use of a complex number structure, but thinking of them as such makes it quicker to find the 8 cardinal directions. You can do vector math the usual way if you want to get the net heading of two or more vectors. (As complex numbers, you don't add, but multiply for the result)

share|improve this answer
    
This is awesome, but makes a similar mistake to the one I made in my own attempt. The answers are close but not right. The boundary angle between E and NE is 22.5 degrees, but this cuts off at 26.6 degrees. –  izb Feb 15 '13 at 16:35
add comment

The simplest way is probably to get the angle of the vector using atan2(), as Tetrad suggests in the comments, and then scale and round it, e.g. (pseudocode):

// enumerated counterclockwise, starting from east = 0:
enum compassDir {
    E = 0, NE = 1,
    N = 2, NW = 3,
    W = 4, SW = 5,
    S = 6, SE = 7
};

// for string conversion, if you can't just do e.g. dir.toString():
const string[8] headings = { "E", "NE", "N", "NW", "W", "SW", "S", "SE" };

// actual conversion code:
float angle = atan2( vector.y, vector.x );
int octant = round( 8 * angle / (2*PI) + 8 ) % 8;

compassDir dir = (compassDir) octant;  // typecast to enum: 0 -> E etc.
string dirStr = headings[octant];

The octant = round( 8 * angle / (2*PI) + 8 ) % 8 line might need some explanation. In pretty much all languages that I know of that have it, the atan2() function returns the angle in radians. Dividing it by 2π converts it from radians to fractions of a full circle, and multiplying by 8 then converts it to eighths of a circle, which we then round to the nearest integer. Finally, we reduce it modulo 8 to take care of the wrap-around, so that both 0 and 8 are correctly mapped to east.

The reason for the + 8, which I skipped past above, is that in some languages atan2() may return negative results (i.e. from −π to +π rather than from 0 to 2π) and the modulo operator (%) may be defined to return negative values for negative arguments (or its behavior for negative arguments may be undefined). Adding 8 (i.e. one full turn) to the input before reduction ensures that the arguments are always positive, without affecting the result in any other way.

If your language doesn't happen to provide a convenient round-to-nearest function, you can use a truncating integer conversion instead and just add 0.5 to the argument, like this:

int octant = int( 8 * angle / (2*PI) + 8.5 ) % 8;  // int() rounds down

Note that, in some languages, the default float-to-integer conversion rounds negative inputs up towards zero rather than down, which is another reason to make sure that the input is always positive.

Of course, you can replace all occurrences of 8 on that line with some other number (e.g. 4 or 16, or even 6 or 12 if you're on a hex map) to divide the circle into that many directions. Just adjust the enum/array accordingly.

share|improve this answer
    
Note that it's usually atan2(y,x), not atan2(x,y). –  Sam Hocevar Feb 14 '13 at 11:11
    
@Sam: Oops, corrected. Of course, atan2(x,y) would work too, if one just listed the compass headings in clockwise order starting from north instead. –  Ilmari Karonen Feb 14 '13 at 12:06
2  
+1 by the way, I really think this is the most straightforward and rigourous answer. –  Sam Hocevar Feb 14 '13 at 23:18
    
What is the equivalent of the octant equation if angle is in degrees? –  TheLima Sep 21 '13 at 18:36
1  
@TheLima: octant = round(8 * angle / 360 + 8) % 8 –  Ilmari Karonen Sep 21 '13 at 22:45
add comment

When you want a string:

h_axis = ""
v_axis = ""

if (x > 0) h_axis = "E"    
if (x < 0) h_axis = "W"    
if (y > 0) v_axis = "S"    
if (y < 0) v_axis = "N"

return v_axis.append_string(h_axis)

This gives you constants by utilizing bitfields:

// main direction constants
DIR_E = 0x1
DIR_W = 0x2
DIR_S = 0x4
DIR_N = 0x8
// mixed direction constants
DIR_NW = DIR_N | DIR_W    
DIR_SW = DIR_S | DIR_W
DIR_NE = DIR_N | DIR_E
DIR_SE = DIR_S | DIR_E

// calculating the direction
dir = 0x0

if (x > 0) dir |= DIR_E 
if (x < 0) dir |= DIR_W    
if (y > 0) dir |= DIR_S    
if (y < 0) dir |= DIR_N

return dir

A slight performance improvement would be to put the <-checks into the else-branch of the corresponding >-checks, but I refrained from doing that because it harms readability.

share|improve this answer
1  
Sorry, but that won't give exactly the answer I'm looking for. With that code it will only yield "N" if the vector is precisely north, and NE or NW if x is any other value. What I need is the closest compass direction, e.g. if the vector is closer to N than NW then it will yield N. –  izb Feb 13 '13 at 16:16
    
Would this actually give the closest direction? It seems a vector of (0.00001,100) would give you north east. edit: you beat me to it izb. –  CiscoIPPhone Feb 13 '13 at 16:16
    
you didn't say that you want the closest direction. –  Philipp Feb 13 '13 at 16:18
1  
Sorry, I hid that in the title. Should have been clearer in the question body –  izb Feb 13 '13 at 16:30
1  
What about using the infinite norm? Dividing by max(abs(vector.components)) gives you a normalized vector with respect to that norm. Now you could write a small check-up table based on if (x > 0.9) dir |= DIR_E and all the rest. It should be better than Phillipp's original code and a bit cheaper than using the L2 norm and atan2. Maybe.. or maybe not. –  teodron Feb 13 '13 at 16:43
show 2 more comments

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.