## Converting (x, y) into NESW direction

Sage
Posts: 1,403
Joined: 2005.07
Post: #1
If I have a vector of any length whats the quickest way to convert it to N E S W NE NW SE or SW?
I dont want to use atan, and a big nested if thingy isnt very nice..
and Ideas?

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
atan2 is definitely the obvious solution... find the angle, turn it into 0..7, do an array lookup.
Sage
Posts: 1,199
Joined: 2004.10
Post: #3
I'd flatten the z component and re-normalize. Then just compare x & y quantities...

Code:
```enum compass_quadrant {    North,    NorthEast,    East,    SouthEast,    South,    SouthWest,    West,    NorthWest }; compass_quadrant vectorToCompassQuadrant( vec3 v ) {    v.z = 0;    v.normalize();       // you could cache this as a literal ( 0.866025 )    const float cos30  = cosf( 30.0f * M_PI / 180.0f );       if ( v.x >= 0 && v.y >= 0 )    {       if ( v.x > cos30 ) return East;       if ( v.y > cos30 ) return North;       return NorthEast;    }       if ( v.x >= 0 && v.y <= 0 )    {       if ( v.x > cos30 ) return East;       if ( v.y < -cos30 ) return South;       return SouthEast;          }    if ( v.x <= 0 && v.y <= 0 )    {       if ( v.x < -cos30 ) return West;       if ( v.y < -cos30 ) return South;       return SouthWest;    }       if ( v.x < -cos30 ) return West;    if ( v.y > cos30 ) return North;    return NorthWest; }```
Member
Posts: 131
Joined: 2004.10
Post: #4
TomorrowPlusX's solution doesn't really need to normalize as you only need the slope.

slope = fabs(x/y);

Then you can compare with cos(22.5 degrees)/sin(22.5 degrees) and sin(22.5)/cos(22.5) which are 0.4142 and 2.4142 respectively (give or take.)
Sage
Posts: 1,199
Joined: 2004.10
Post: #5
This is why I should think before I post.
Sage
Posts: 1,403
Joined: 2005.07
Post: #6
That way looks fine, its just another method,
There is now 3 different ways I can see of doing this.

I wonder if theres any others?

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Member
Posts: 131
Joined: 2004.10
Post: #7
There is a problem with the slope case. If y is zero then you have a div/0 error so you have to check for it.

Sometimes a simpler yet clearer algorithm is better than one that is clever. I'd choose a sloppy algorithm that is easy to understand and works over a convoluted and heavily optimized one initially. I'm more concerned with getting something working than getting it working super fast.

Other ways? Probably.
Moderator
Posts: 1,563
Joined: 2003.10
Post: #8
TomorrowPlusX's method is the simple and easy way to do it. If you're really looking for alternative methods, another thing you could do would be to take the dot product between your vector and a vector for each of your eight directions, and return the direction corresponding to the one that gives you the highest result.
Luminary
Posts: 5,143
Joined: 2002.04
Post: #9
Code:
```#include <math.h> #include <stdio.h> #include <stdlib.h> const char *DIRECTION_NAMES[8] = { "W", "SW", "S", "SE", "E", "NE", "N", "NW" }; const char *direction(double x, double y) {     double angle = atan2(y, x) + M_PI;     double fraction = angle * 0.5 / M_PI;     fraction += 1.0 / 16.0;     if (fraction >= 1.0)     {         fraction -= 1.0;     }     int index = fraction * 8.0;          return DIRECTION_NAMES[index]; } int main(int argc, const char *argv[]) {     if (argc < 3)     {         return EXIT_FAILURE;     }          double x = atof(argv[1]);     double y = atof(argv[2]);          printf("(%f, %f) is %s\n", x, y, direction(x, y));     return EXIT_SUCCESS; }```
Sage
Posts: 1,403
Joined: 2005.07
Post: #10
TommorowPlusX
Code:
```#include <math.h> #include <stdio.h> #include <stdlib.h> const char *DIRECTION_NAMES[8] = { "N", "NE", "E", "SE", "S", "SW", "W", "NW" }; typedef enum {     North,     NorthEast,     East,     SouthEast,     South,     SouthWest,     West,     NorthWest } compass_quadrant; typedef struct {     double x, y, z; } vec3; void normalize(vec3 *v) { float d = sqrtf(v->x*v->x + v->y*v->y + v->z*v->z);                                     v->x /= d;  v->y /= d;  v->z /= d; } compass_quadrant vectorToCompassQuadrant( vec3 v ) {     v.z = 0;     normalize(&v);          // you could cache this as a literal ( 0.866025 )     const float pinion = cosf( 22.5f * M_PI / 180.0f );          if ( v.x >= 0 && v.y >= 0 )     {         if ( v.x > pinion ) return East;         if ( v.y > pinion ) return North;         return NorthEast;     }          if ( v.x >= 0 && v.y <= 0 )     {         if ( v.x > pinion ) return East;         if ( v.y < -pinion ) return South;         return SouthEast;           }          if ( v.x <= 0 && v.y <= 0 )     {         if ( v.x < -pinion ) return West;         if ( v.y < -pinion ) return South;         return SouthWest;     }          if ( v.x < -pinion ) return West;     if ( v.y > pinion ) return North;     return NorthWest; } int main(int argc, const char *argv[]) {     if (argc < 3)     {         return EXIT_FAILURE;     }          double x = atof(argv[1]);     double y = atof(argv[2]);          printf("(%f, %f) is %s\n", x, y, DIRECTION_NAMES[vectorToCompassQuadrant((vec3){x, y, 0})]);     return EXIT_SUCCESS; }```

ThemsAllTook
Code:
```#include <math.h> #include <stdio.h> #include <stdlib.h> #define SQRT2 0.4142 const char *DIRECTION_NAMES[8] = { "N", "NE", "E", "SE", "S", "SW", "W", "NW" }; const double DIRECTION_VALUES[16] = {1, 0, SQRT2, SQRT2, 0, 1, SQRT2, -SQRT2, 0, -1, -SQRT2, -SQRT2, -1, 0, -SQRT2, SQRT2}; const double dot(double x1, double y1, double x2, double y2) {     return x1*x2+y1*y2; } const char *direction(double x, double y) {     double dot_products[8];     int index;     for(index = 0; index < 8; index++)         dot_products[index] = dot(x, y, DIRECTION_VALUES[2*index+0], DIRECTION_VALUES[2*index+1]);          int max_index = 1;     for(index = 1; index < 8; index++)         if(dot_products[index] > dot_products[max_index])             max_index = index;          return DIRECTION_NAMES[max_index]; } int main(int argc, const char *argv[]) {     if (argc < 3)     {         return EXIT_FAILURE;     }          double x = atof(argv[1]);     double y = atof(argv[2]);          printf("(%f, %f) is %s\n", x, y, direction(x, y));     return EXIT_SUCCESS; }```

Ill put up yours Zekaric's when I do that, as well as an Idea I had using inequalities that means I can do it with a maximum of 4 checks. But I havent slept for 23 hours so I better go just now..

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Luminary
Posts: 5,143
Joined: 2002.04
Post: #11
what is wrong with my code? It's about 10x shorter, and works very nicely
Sage
Posts: 1,199
Joined: 2004.10
Post: #12
If you do use mine, switch from

Code:
`const float cos30  = cosf( 30.0f * M_PI / 180.0f );`

to something like:

Code:
`const float pinion = cosf( 22.5f * M_PI / 180.0f );`

Since I wasn't thinking clearly and was using 30 degree chunks when they should have been 45. Too early in the morning...
Member
Posts: 184
Joined: 2004.07
Post: #13

He has something against atan, which makes absolutely no sense, considering every single programming environment I've ever used has had a fast implementation of it.
Member
Posts: 131
Joined: 2004.10
Post: #14
OSC:
Nothing's wrong with your code asside from the function call (which is probably inlined so not really a function call but it'll have other potentially expensive operations internally) 2 adds, 2 multiplys, 2 divides and one if. But then optimizing a call like this seems rather silly unless someone has a valid argument to do so.

Unknown:
Check your 'normalize' macro. d is not = to distance. Missing a square root.

To save you some time, here's my uber ugly if confabulation. Look away, look away...
Code:
```#include <float.h> #include <math.h> #include <stdio.h> #include <stdlib.h> typedef enum                     { WST, SWST, STH, SEST, EST, NEST, NTH, NWST } DIRECTION_INDEX; const char *DIRECTION_NAMES[8] = { "W", "SW", "S", "SE", "E", "NE", "N", "NW" }; const char *direction(double x, double y) {    double fraction;    if (fabs(y) < DBL_EPSILON) {       if (x > 0) {          return DIRECTION_NAMES[EST];       }       return DIRECTION_NAMES[WST];    }    fraction = fabs(x/y);    if (y > 0) {              if (x > 0) {          if      (2.4142 < x) {             return DIRECTION_NAMES[EST];          }          else if (x < 0.4142) {             return DIRECTION_NAMES[NTH];          }          return DIRECTION_NAMES[NEST];       }       if      (2.4142 < -x) {          return DIRECTION_NAMES[WST];       }       else if (-x < 0.4142) {          return DIRECTION_NAMES[NTH];       }       return DIRECTION_NAMES[NWST];    }       if (x > 0) {       if      (2.4142 < x) {          return DIRECTION_NAMES[EST];       }       else if (x < 0.4142) {          return DIRECTION_NAMES[STH];       }       return DIRECTION_NAMES[SEST];    }    if      (2.4142 < -x) {       return DIRECTION_NAMES[WST];    }    else if (-x < 0.4142) {       return DIRECTION_NAMES[STH];    }    return DIRECTION_NAMES[SWST]; } int main(int argc, const char *argv[]) {    double x;    double y;    if (argc < 3)    {       return EXIT_FAILURE;    }       x = atof(argv[1]);    y = atof(argv[2]);       printf("(%f, %f) is %s\n", x, y, direction(x, y));       return EXIT_SUCCESS; }```
Hopefully error free. Just cursory testing with it.
Sage
Posts: 1,403
Joined: 2005.07
Post: #15
Here is my train of though, im just coding it now
Code:
```(2)+          (1)+    +-----------+-----------+    |NW    \    ' N  /    NE|    |       \       /       | (4)|._      \  '  /       ,|(3) + |  `-._   \   /    ,,-' | +    |      `-._\'/ ,,-'    E|    +-  -  -  - X.' -  -  - +    |W     ,,-'/'\`-..      |    |  ,,-'   /   \   `-._  | (3)|-'      /  '  \      `-|(4) + |       /       \       | +    |SW    /    '  S \    SE|    +-----------+-----------+        (1)+          (2)+              _     m = (2+v'2)   (1) y<mx                   (2) y>-mx                   (3) y<1/mx                   (4) y>-1/mx```

whats what
Code:
```N = !(1)& (2) NE =  (1)&!(3) E =  (3)&!(4) SE =  (2)& (4) S =  (1)&!(2) SW = !(1)& (3) W = !(3)& (4) NW = !(2)&!(4)```

if's and else's
Code:
```(1):      (2):          (3):              (4):SE             !(4):E         !(3):NE     !(2):S !(1):      (2):          N     !(2):          (3):SW         !(3):              (4):W             !(4):NW```

optimised:
Code:
```(1):     !(2):S      (2):         !(3):NE          (3):              (4):SE             !(4):E !(1):      (2):          N     !(2):          (3):SW         !(3):              (4):W             !(4):NW```

There seems to be a slight problem with this, it never gets E or W,
Code:
```#include <float.h> #include <math.h> #include <stdio.h> #include <stdlib.h> #define M 0.414213562373 #define ONE   (y<x/M) #define TWO   (y>-M*x/M) #define THREE (y<M*x) #define FOUR  (y<M*x) //                                  0     1    2     3    4     5    6     7 const char *DIRECTION_NAMES[9] = { "W", "SW", "S", "SE", "E", "NE", "N", "NW", "?"}; const char *direction(double x, double y) {     if((ONE))         if(!(TWO))             return DIRECTION_NAMES[2];         else             if(!(THREE))                 return DIRECTION_NAMES[5];             else                 if(!(FOUR))                     return DIRECTION_NAMES[4]; // never called                 else                     return DIRECTION_NAMES[3];     else         if((TWO))             return DIRECTION_NAMES[6];         else             if((THREE))                 return DIRECTION_NAMES[1];             else                 if((FOUR))                     return DIRECTION_NAMES[0]; // never called                 else                     return DIRECTION_NAMES[7];         } int main(int argc, const char *argv[]) {         double theta;      #define ONDEG (M_PI/180.0)          for(theta = 0; theta < 360; theta += 10)         printf("(%f, %f) is %s\n", 5*cos(theta*ONDEG), 5*sin(theta*ONDEG), direction(5*cos(theta*ONDEG), 5*sin(theta*ONDEG)));          return EXIT_SUCCESS; }```

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!