# What's the best way of transforming a 2D vector into the closest 8-way compass direction?

If you have a 2D vector expressed as x and y, what's a good way of transforming 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

• 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
• Are you concerned about the performance as well, or only about conciseness? – Marcin Seredynski Feb 13 '13 at 16:59
• 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

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.


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.

• 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
• +1 by the way, I really think this is the most straightforward and rigourous answer. – sam hocevar Feb 14 '13 at 23:18
• @TheLima: octant = round(8 * angle / 360 + 8) % 8 – Ilmari Karonen Sep 21 '13 at 22:45
• Do note that this can easily be converted to a 4-way compass: quadtant = round(4 * angle / (2*PI) + 4) % 4 and using enum: { E, N, W, S }. – Spoike May 13 '16 at 22:23

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

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

atan2() works in the following way:

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:

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

• 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
• 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
• 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
• 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. – MichaelHouse Feb 15 '13 at 15:24

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];
}
}

• This implementation can also be written branchless and vectorized without too much trouble. – Promit Feb 14 '13 at 16:52
• 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

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 }

{
}

{
}


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)

• 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
• Max(x, y) should be Max(Abs(x, y)) to work for the negative quadrants. I tried it and got the same result as izb — this switches compass directions at the wrong angles. I would guess it would switch when heading.y/heading.x crosses 0.5 (so the rounded value switches from 0 to 1), which is arctan(0.5) = 26.565°. – amitp Nov 27 '18 at 19:51
• A different way to use complex numbers here is to observe that multiplication of complex numbers involves a rotation. If you construct a complex number that represents 1/8th of a rotation around a circle, then every time you multiply by it, you move one octant. So you could ask: can we count how many multiplications did it take to go from East to the current heading? The answer to "how many times do we have to multiply by this" is a logarithm. If you look up logarithms for complex numbers … it uses atan2. So this ends up being equivalent to Ilmari's answer. – amitp Nov 27 '18 at 20:09

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"};
}

• why is this being voted down? – Ray Tayek Jan 24 '15 at 0:00
• Most likely because there are no explanation behind your code. Why is this the solution and how does it work? – Alexandre Vaillancourt Jan 24 at 15:55
• did you run it? – Ray Tayek Jan 25 at 16:40
• No, and given the name of the class, I assumed you did and it worked. And that's great. But you asked why people voted down and I answered; I never implied that it did not work :) – Alexandre Vaillancourt Jan 25 at 18:45

E=0,NE=1,N=2,NW=3,W=4,SW=5,S=6,SE=7

f(x,y)=mod((4-2*(1+sign(x))* (1-sign(y^2))-(2+sign(x))*sign(y)

    -(1+sign(abs(sign(x*y)*atan((abs(x)-abs(y))/(abs(x)+abs(y))))

-pi()/(8+10^-15)))/2*sign((x^2-y^2)*(x*y))),8)

• For now, this is just a bunch of characters that don't make much sense; why is this a solution that would work for the question, how does it work? – Alexandre Vaillancourt Jan 24 at 16:03
• I write the formula as I wrote jn excel and is working perfectly. – theodore panagos Jan 24 at 20:26
• =MOD((4-2*(1+SIGN(X1))* (1-SIGN(Y1^2))-(2+SIGN(X1))*SIGN(Y1)-(1+SIGN(ABS(SIGN(X1*Y1)*ATAN((ABS(X1)-ABS(Y1))/(ABS(X1)+ABS(Y1))))-PI()/(8+10^-15)))/2*SIGN((X1^2-Y1^2)*(X1*Y1))),8) – theodore panagos Jan 24 at 20:41

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.

• 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
• Sorry, I hid that in the title. Should have been clearer in the question body – izb Feb 13 '13 at 16:30
• 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