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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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)

Answer 5

Wonder, why so complicated? (not sure what language, so keep it general)

If you want the 8 direction from a Vector2, just normalize it and then round it. Maybe something like:

var length = Math.sqrt(x * x + y * y);
x /= length;
y /= length;

Then round:

rX = Math.round(x);
rY = Math.round(y);

Then you could still convert to String, like Philipp explained:

string result = "";
if (rY < 0.1)
    result.Append("N");
else if (rY > 0.1)
    result.Append("S");
if (rX < 0.1)
    result.Append("W");
else if (rX > 0.1)
    result.Append("E");

0.1 is just in case if floating point precision issues, except you rounded to int, then you are safe with 0. Or do I miss something?

Answer 6

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

Answer 7

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)

Answer 8

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.