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]
[2D]testing if vector is between two vectors
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:
- Say you have 3rd point P3 (i.e. the vector you test is P1P3)
- Determine, at which side of P1P0 point P2 lies. Let's call it P2_pos (L or R)
- Determine at which sides of P1P0 and P1P2 point P3 lies. Let's call it P3_pos (LL, LR, RR or RL)
- Now P1P3 is between P1P0 and P1P2 if either:
- P2_pos = R AND P3_pos = RL
- P2_pos = L AND P3_pos != LR
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
}
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.
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?
Author
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
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.
Author
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.
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?).
Author
Actually they represent the concave corner.
i solved this problem using perpDot for checking sides like this:
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
