# What is a good way to determine if a vector is between two other vectors in 2D?

I could operate with the angles, but I do not have the angles calculated yet (and would like to avoid having to do that). It would be possible to calculate and cache the local-coordinate-frame angles, though.

This is a routine that is run on every vertex of every convex polygon within the convex decomposition of every physically simulated object, so it should be as fast as possible.

I've got a corner of a convex polygon, so I have a vector from vertex to vertex-1 and another vector from vertex to vertex+1. It is easy to see that for a convex polygon, the interior of the polygon lies in the direction of the average of these two vectors.

I want to determine given any vector whether it points into that region or outside of it. Can I accomplish this using only cross products and dot products and similar fast operations? I am thinking about eventually offloading these calculations to a vertex shader, but as it changes the number of vertices required depending on an object's velocity, I imagine the logic could get dicey. Either way, before I attempt a vertex or geometry shader implementation I had better get a CPU solution working correctly first.

Here's an example: I want to find if N is between A and B. A points right at -10 (=350) degrees, B is at 15 degrees. So it looks somewhat like the < symbol. Function should return true only if N is between -10 and 15, between 350 and 375, etc. This was just to paint a mental picture, the input to the function are vectors: I want to avoid operating on angles because I do not want to call atan2.

It may help if it is known that A cross B is always positive. This is the case because my polygon is CCW winded and convex.

-
You hit the nail on the head with your update there. – Steve H Jan 14 '12 at 15:33
You should at least make your "update" an answer. – Josh Petrie Jan 16 '12 at 18:16

I think the best way to solve this, given A x B > 0, is to simply check A x N and N x B are also both positive. It seems to be working well.

-
the cross product produces a vector. how do you determine if it's "positive"? – TravisG Jan 16 '12 at 20:10
Sorry I'm working in 2D, it's a scalar in that case. The entire problem only really makes sense inside of a plane anyhow, because the 3 vectors need to be coplanar for "in between" to make any sense. Not that this concept can't be extended to 3D, but I'm not dealing with that. – Steven Lu Jan 16 '12 at 21:12
edit: nevermind, some research showed that there actually is a cross product between two vectors in 2D . weird. – TravisG Jan 16 '12 at 23:15
@TravisG In essence, the 'cross product' in 2d is the dot product between one of the two vectors and a vector orthogonal to the other - it's an immensely useful operation for this sort of 'side' information (and is at the core of the solution to the classic 'steer this 2d car' game programming interview question). – Steven Stadnicki Jun 19 '13 at 1:10
You can get even easier, when both cross AxN and NxB have the same sign you are done, no matter if AxB is positive or not – Martin Dec 15 '13 at 23:10

Endpoint vectors A and B, in 2d space. Third vector, C, might be somewhere between them. This is what we are checking for.

If A+(B-A)*(Distance(A,C)/Distance(A,B))=C, then the line segments intersect.

-
Hey Ryan, welcome to the site! If you could expand your answer a bit more by explaining the steps of your question and the reasoning behind it you'd get some votes for sure. Thanks. – Byte56 Jun 19 '13 at 0:23