Getting a direction constant from normalized vector

Started by
15 comments, last by aggieblue92 10 years, 1 month ago

I have a method which returns the direction of a vector.

The direction can be either N, NE, E, SE, S, SW, W, NW(8 total).

Here is my method, which is horrible buggy:


	public static Direction getDirection(Point2D.Float normalizedPoint)
	{
		int x = Math.round(normalizedPoint.x);
		int y = Math.round(normalizedPoint.y);
		
		if	   (x == 1 && y == 1)
			return Direction.NW;
		else if(x == 1 && y == 0)
			return Direction.W;
		else if(x == 1 && y == -1)
			return Direction.SW;
		else if(x == 0 && y == -1)
			return Direction.S;
		else if(x == -1 && y == -1)
			return Direction.SE;
		else if(x == -1 &&  y == 0)
			return Direction.E;
		else if(x == -1 && y == 1)
			return Direction.NE;
		else if(x == 0 && y == 1)
			return Direction.E;
		
		return null;
	} 

How do I resolve this?

Advertisement

That doesn't work, since your vector is normalized so a direction of (1, 1) is not possible since it has length greater than 1. What you can do is calculate the angle of your vector (possibly one of the few places were angles are worthwhile) and then do interval checks e.g. if the angle is "near" zero degrees, the direction is E, etc.. for all eight cardinal directions. But I suspect you are doing this for an UI to create a directional arrow depending on the mouse position or something, if so you can just check each half-quadrant, i.e. (in degrees for ease of understanding):

angle -22.25 to +22.5 => E

angle +22.5 to +67.5 => NE

angle +67.5 to 112.5 => N

and so on, that way every vector has a direction. But this may not be what you want. If your vector can only have eight discrete directions, then enforce it in your vector class, don't overcomplicate things. If not, properly specify your requirements so you know exactly what you need out of this function (because having a function that can return null on valid inputs is almost certainly a design flaw).

(what I mean is, if you only need eight directions but need vectors for e.g. drawing things, then you might be better off working entirely with directions and converting them to vectors as needed, which is easy, i.e. the opposite of what you're doing here - but you haven't given enough information so this is merely speculation)

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

You can also cheat, and pre-normalize all the values to check against and store them in an array, then just iterate over the array, I think that's what I did in one of my implementations (in the other I did as Bacterius suggested)

EDIT: Oh wait, I take it back, my implementation was for getting the direction from a hardcoded direction, ie if I knew it was North, give me the normalized vector for North.

I like your idea with the rounding smile.png But as you can see it doesn't work, because the transition between your conditions doesn't happen when you want them.

So back to how to properly do it, I don't know C#, really, but I would use Atan2: http://msdn.microsoft.com/en-us/library/system.math.atan2(v=vs.110).aspx .

Once you have the angle you can just use ranges as Bacterious suggested. I think this is the most legible way and efficiency-wise it not that bad.

EDIT: And if you indeed care about performance, C0lumbo has an appropriate answer below.

“We should forget about small efficiencies, say about 97% of the time; premature optimization is the root of all evil” - Donald E. Knuth, Structured Programming with go to Statements

"First you learn the value of abstraction, then you learn the cost of abstraction, then you're ready to engineer" - Ken Beck, Twitter

People are probably correct suggesting that you shouldn't end up needing this function, but to implement it I would perhaps do something like:

float fThreshold = cos(PI / 8);

If (x > fThreshold)

return East;

else if (x < -fThreshold)

return West;

else if (y > fThreshold)

return North;

else if (y < -fThreshold)

return South;

else if (x > 0 && y > 0)

return NorthEast

else if (x > 0 && y < 0)

return SouthEast

else if (x < 0 && y > 0)

return NorthWest

else if (x < 0 && y < 0)

return SouthWest

(this is assuming positive x is east and positivie y is north)

That doesn't work, since your vector is normalized so a direction of (1, 1) is not possible since it has length greater than 1.

Well, the OP shows that the "normalized vector" is rounded component-wise before comparison, so a de-normalization is done and a direction of (1,1) is actually valid at that moment.

For 8 discrete directions in 45° steps the limits are at 22.5° + n * 45°, so the switch from e.g. E to NE takes place at 22.5°. Now the sine of 22.5° is approx. 0.3827 which is somewhat lower than 0.5, where 0.5 is the limit used with Math.round(). Hence the OP uses the range of [-30°;+30°] for E instead of [-22.5°;+22.5°], and similar for the other directions. In case that the input vector is actually normalized (besides the fact that a "point" cannot be normalized), the routine seems me able to return all 8 principle directions, but with wrong limits.

A solution to this problem is as described in the answers above: Use Math.atan2() to compute the angle, and check it against the limits (don't forget that atan2 returns an angle in radian).

Here is my method, which is horrible buggy:

As Bacterius has written: Could you please explain in detail what the problem is?

Take a normalized vector for each direction eg. 0,1 is up.

Dot product each with your normalized direction.

Find the largest value and that should be the closest direction.

o3o

Take a normalized vector for each direction eg. 0,1 is up.

Dot product each with your normalized direction.

Find the largest value and that should be the closest direction.

That would work, of course, but does it have any advange over the Atan2 or the cosine-threshold methods? I find it more expensive and less legible than both...

Well, I guess it is more generalizable to more directions, but still...

“We should forget about small efficiencies, say about 97% of the time; premature optimization is the root of all evil” - Donald E. Knuth, Structured Programming with go to Statements

"First you learn the value of abstraction, then you learn the cost of abstraction, then you're ready to engineer" - Ken Beck, Twitter

Take a normalized vector for each direction eg. 0,1 is up.

Dot product each with your normalized direction.

Find the largest value and that should be the closest direction.

That would work, of course, but does it have any advange over the Atan2 or the cosine-threshold methods? I find it more expensive and less legible than both...

Well, I guess it is more generalizable to more directions, but still...

The dot product is only 2 multiplications and an addition in 2D so i would expect it to be faster than trigonometric functions...

o3o

It's very simple really.


float cos30 = sqrt(3.0f) / 2.0f;
float cos60 = 0.5f;

int quadrantx = (x >= cos30)? 0 : (x >= cos60)? 1 : (x >= 0.0f)? 2 : (x >= -cos60)? 3 : (x >= -cos30)? 4 : 5;
int quadranty = (y >= 0.0f)? 0 : 1;

Direction directions[12] = { Direction.E, Direction.NE, Direction.N, Direction.N, Direction.NW, Direction.W, Direction.W, Direction.SW, Direction.S, Direction.S, Direction.SE, Direction.E };

int quadrant = quadranty * 6 + quadrantx;

return directions[quadrant];

Everything is better with Metal.

This topic is closed to new replies.

Advertisement