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!
Quote this message in a 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.
Quote this message in a reply
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;
}
Quote this message in a reply
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.)
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #5
This is why I should think before I post.
Quote this message in a reply
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!
Quote this message in a 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.
Quote this message in a reply
Moderator
Posts: 1,560
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.
Quote this message in a reply
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;
}
Quote this message in a reply
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!
Quote this message in a 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 Rasp
Quote this message in a reply
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...
Quote this message in a reply
Member
Posts: 184
Joined: 2004.07
Post: #13
OneSadCookie Wrote:what is wrong with my code? It's about 10x shorter, and works very nicely Rasp

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.
Quote this message in a reply
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.
Quote this message in a reply
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!
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Direction of normal Miglu 3 3,622 Oct 4, 2010 05:08 PM
Last Post: Skorche
  Direction formula? TimMcD 2 5,284 Nov 11, 2009 11:42 PM
Last Post: TimMcD
  Converting Int To String Nick 4 14,225 Jun 2, 2005 02:13 AM
Last Post: hangt5
  converting xyz rotation to something else reubert 10 5,951 Mar 5, 2005 07:33 PM
Last Post: Puzzler183
  Converting strings to functions Joseph Duchesne 10 5,437 Feb 23, 2005 11:42 PM
Last Post: Skorche