Jump to content
  • Advertisement
Sign in to follow this  
PJani

[2D]testing if vector is between two vectors

This topic is 2526 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hy, I have one problem. I am trying to test if vector is between two vectors ( these two vectors are defined with tree points in CCW order. [p0, p1, p2] ). I would like not to use any trigonomic functions for the sake of performance.

[attachment=5414:vectors.PNG]

Share this post


Link to post
Share on other sites
Advertisement

Hy, I have one problem. I am trying to test if vector is between two vectors ( these two vectors are defined with tree points in CCW order. [p0, p1, p2] ). I would like not to use any trigonomic functions for the sake of performance.

[attachment=5414:vectors.PNG]

I think something like that will do:

  1. Say you have 3rd point P3 (i.e. the vector you test is P1P3)
  2. Determine, at which side of P1P0 point P2 lies. Let's call it P2_pos (L or R)
  3. Determine at which sides of P1P0 and P1P2 point P3 lies. Let's call it P3_pos (LL, LR, RR or RL)
  4. Now P1P3 is between P1P0 and P1P2 if either:
  5. P2_pos = R AND P3_pos = RL
  6. P2_pos = L AND P3_pos != LR

Share this post


Link to post
Share on other sites
The perpendicular dot product of two vectors can be used to determine if a vector lies at the left or at the right of another vector. Since the magnitude of a vector is always positive the sign of the perp dot product is indeed the sign of the sine of the angle between the two vectors. The third vector will lies between the two vectors if the sign of the two perp dot products with the two vectors will have different signs:

t1 = perp_dot(v3, P1 - P0)
t2 = perp_dot(v3, P2 - P0)
if (t1*t2 < 0) {
// ... the third vector is between the other two
}


Share this post


Link to post
Share on other sites

The perpendicular dot product of two vectors can be used to determine if a vector lies at the left or at the right of another vector. Since the magnitude of a vector is always positive the sign of the perp dot product is indeed the sign of the sine of the angle between the two vectors. The third vector will lies between the two vectors if the sign of the two perp dot products with the two vectors will have different signs:

t1 = perp_dot(v3, P1 - P0)
t2 = perp_dot(v3, P2 - P0)
if (t1*t2 < 0) {
// ... the third vector is between the other two
}


I think the simple perp dot test only determines, whether given vector is between two lines (not two vectors). I.e. if (t1*t2 < 0) then v3 is either between V1 and v2 or between -v1 and -v2. Thus extra test is needed.

Also the actual angle (i.e with direction - CW or CCW) between v1 and v2 has to be taken into account (look at the lower row of example cases), so something like my test 5 & 6 still should be done.

Share this post


Link to post
Share on other sites
I think I have probably misunderstood the problem. In fact, I'm not sure what the OP means by "if vector is between two vectors" looking at the images. But you are right, my test considers lines and not vectors and an additional constraint is required to give the correct answer. Moreover I have considered the wrong vectors since the vectors (P0P1 and P0P2 instead of P1P0 and P1P2). So, how do you suggest to determine if a vector is on the left or on the right of another vector?

Share this post


Link to post
Share on other sites

I think I have probably misunderstood the problem. In fact, I'm not sure what the OP means by "if vector is between two vectors" looking at the images. But you are right, my test considers lines and not vectors and an additional constraint is required to give the correct answer. Moreover I have considered the wrong vectors since the vectors (P0P1 and P0P2 instead of P1P0 and P1P2). So, how do you suggest to determine if a vector is on the left or on the right of another vector?

I am determing side this way



// >0 ... left
// <0 ... right
public static float side(Vec2 a, Vec2 b, Vec2 c){
return ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x));


}


i am using third vector as point when checking for side

Share this post


Link to post
Share on other sites
That's the perp dot product of (b - a) and (c - a). I have looked to the image again and it now makes sense. I concluded that what Lauris Kaplinski described is basically the algorithm to use. We can probably change the condition to something like (P3_POS == RL) || (P2_POS == L && P3_POS != LR), but I can't see any other optimizations.

Share this post


Link to post
Share on other sites
Actually what i am doing is...convex decomposition , i have 2d polygon build with verticles in CCW order. For every verticle i need to find "visible" verticles...i check visiblity by intersections and if "visiblity vector" is between previous and next points.







Share this post


Link to post
Share on other sites
So are you basically trying to determine if that's an ear to clip and your vertexes are always in CCW order? In your image the vertexes wasn't always in CCW order (the vertexes in the bottom row are in CW order, do they represents an hole?).

Share this post


Link to post
Share on other sites
Actually they represent the concave corner.

i solved this problem using perpDot for checking sides like this:


public static boolean liesBetween(Vec2 P0, Vec2 P1, Vec2 P2, Vec2 P3)
{
Vec2 P3P1 = P3.sub(P1);
Vec2 P2P1 = P2.sub(P1);
Vec2 P0P1 = P0.sub(P1);

float p2s = Misc.side(P0P1, P2P1);
float p3as = Misc.side(P0P1, P3P1);
float p3bs = Misc.side(P2P1, P3P1);

return ((p2s > 0 && p3as > 0 && p3bs < 0) || p2s < 0 && (p3as > 0 || p3bs < 0));
}



I use atan2 for comparing angles but it kills performance when looking for best angle. I was thinking of using perpDot for checking the magnitude/scale of angle, but the problem here is that the vectors must be normalised.





Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!