# 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

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.

-
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

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

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. – Byte56 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

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.

-
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
What is the equivalent of the `octant` equation if `angle` is in degrees? – AlmightyR Sep 21 '13 at 18:36
@TheLima: `octant = round(8 * angle / 360 + 8) % 8` – Ilmari Karonen Sep 21 '13 at 22:45

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