Point inside rect, what is wrong with my logic?
Author
Hi,
I have a 2D rectangle and I want to calculate if a point is inside that rectangle.
Vector pt = .. // the point I want to test for.
Vector v = .. // a corner of the rectangle.
Vector v1 = .. // another corner where v -> v1 is a side of the rectangle.
Vector v2 = .. // another corner where v -> v2 is another side of the rectangle.
double d1 = DotProduct(v,v1);
double d2 = DotProduct(v,v2);
if( 0<= d1 && d1 <= DotProduct(v1,v1) && 0<= d2 && d2 <= DotProduct(v2,v2))
{
// is inside.
}
// not inside
...
// the DotProduct(... ) function
double DotProduct( const Vector& v1, const Vector& v2 )
{
return (v1.x_ * v2.x_) + (v1.y_ * v2.y_);
}
This does not seem to work in some cases.
What could be wrong?
Many thanks
FFMG
Why do you think that code should work? It's not even close... Perhaps you can try to explain the logic behind your code, and we can try to fix it.
Taking the dot product of two positions (DotProduct(v,v1)) is not a well-defined operation, in the sense that the result depends on your choice of origin.
`0<=d1' means "the angle formed by v, the origin and v1 is acute", which doesn't even tell you anything about where pt is, so you can't decide that pt is not in the rectangle if this is not true.
Taking the dot product of two positions (DotProduct(v,v1)) is not a well-defined operation, in the sense that the result depends on your choice of origin.
`0<=d1' means "the angle formed by v, the origin and v1 is acute", which doesn't even tell you anything about where pt is, so you can't decide that pt is not in the rectangle if this is not true.
to find if a point inside of a rectangle (for example a b c d) you first find 4 vectors for each side
b-a
c-b
d-c
a-d
if point is on the same side of all these vectors, it is inside. to find this, you can use dot product all these vectors from the a vector from the second point to our test point
dot(b-a, n-a)
dot(c-b, n-b)
dot(d-c, n-c)
dot(a-d, n-d)
if all these dot products are negative or positive (it depends on you rotate cw or ccw) your point is inside the rectangle.
this works for all kind of shapes, triangles rectangle etc as long as it is a convex polygon
b-a
c-b
d-c
a-d
if point is on the same side of all these vectors, it is inside. to find this, you can use dot product all these vectors from the a vector from the second point to our test point
dot(b-a, n-a)
dot(c-b, n-b)
dot(d-c, n-c)
dot(a-d, n-d)
if all these dot products are negative or positive (it depends on you rotate cw or ccw) your point is inside the rectangle.
this works for all kind of shapes, triangles rectangle etc as long as it is a convex polygon
Author
Quote:Original post by SriLumpa
Your code does not even read pt, so it couldn't possibly work !
Sorry, it was a typo,
Vector crn = .. // a corner of the rectangle.
Vector v = pt - crn;
FFMG
Author
Quote:Original post by alvaro
Why do you think that code should work? It's not even close... Perhaps you can try to explain the logic behind your code, and we can try to fix it.
Taking the dot product of two positions (DotProduct(v,v1)) is not a well-defined operation, in the sense that the result depends on your choice of origin.
`0<=d1' means "the angle formed by v, the origin and v1 is acute", which doesn't even tell you anything about where pt is, so you can't decide that pt is not in the rectangle if this is not true.
Ok, so the formula is wrong.
This makes sense as it does not work for me, oddly it does work sometimes, I am not a mathematician so obviously I made some mistakes, (kind of the reason why I am here).
I would like to be able to calculate/tell if a point is inside a rectangle, (a 2D one).
As my code is not even close, would you have some code I could use?
Thanks
FFMG
I tried to explaining in my previous post, here is a code example
Vector pt //point to test
Vector p1, p2, p3, p4 //corners of rectangle
//
Vector v1 = p2 - p1; //find edge vectors
Vector v2 = p3 - p2;
Vector v3 = p4 - p3;
Vector v3 = p1 - p4;
float f1 = dot(v1, pt-p1);
float f2 = dot(v2, pt-p2);
float f3 = dot(v3, pt-p3);
float f4 = dot(v4, pt-p4);
if( (f1 < 0 && f2 < 0 && f3 < 0 && f4 < 0) || (f1 > 0 && f2 > 0 && f3 > 0 && f4 > 0) ){ //if all dot products are negative or positive
//inside
}else{
//outside
}
Vector pt //point to test
Vector p1, p2, p3, p4 //corners of rectangle
//
Vector v1 = p2 - p1; //find edge vectors
Vector v2 = p3 - p2;
Vector v3 = p4 - p3;
Vector v3 = p1 - p4;
float f1 = dot(v1, pt-p1);
float f2 = dot(v2, pt-p2);
float f3 = dot(v3, pt-p3);
float f4 = dot(v4, pt-p4);
if( (f1 < 0 && f2 < 0 && f3 < 0 && f4 < 0) || (f1 > 0 && f2 > 0 && f3 > 0 && f4 > 0) ){ //if all dot products are negative or positive
//inside
}else{
//outside
}
Author
Quote:Original post by shultays
I tried to explaining in my previous post, here is a code example
Vector pt //point to test
Vector p1, p2, p3, p4 //corners of rectangle
//
Vector v1 = p2 - p1; //find edge vectors
Vector v2 = p3 - p2;
Vector v3 = p4 - p3;
Vector v3 = p1 - p4;
float f1 = dot(v1, pt-p1);
float f2 = dot(v2, pt-p2);
float f3 = dot(v3, pt-p3);
float f4 = dot(v4, pt-p4);
if( (f1 < 0 && f2 < 0 && f3 < 0 && f4 < 0) || (f1 > 0 && f2 > 0 && f3 > 0 && f4 > 0) ){ //if all dot products are negative or positive
//inside
}else{
//outside
}
This works great, thanks a lot!
FFMG
Quote:Original post by shultays
to find if a point inside of a rectangle (for example a b c d) you first find 4 vectors for each side
b-a
c-b
d-c
a-d
if point is on the same side of all these vectors, it is inside. to find this, you can use dot product all these vectors from the a vector from the second point to our test point
dot(b-a, n-a)
dot(c-b, n-b)
dot(d-c, n-c)
dot(a-d, n-d)
if all these dot products are negative or positive (it depends on you rotate cw or ccw) your point is inside the rectangle.
this works for all kind of shapes, triangles rectangle etc as long as it is a convex polygon
This works only with rectangles. Try it on a triangle and you will see, it's not working. But it is the simplest method for rects anyway.
Quote:This works only with rectangles. Try it on a triangle and you will see, it's not working.Based on his description of the algorithm, I'm guessing shultays meant to use the perp-dot product rather than the dot product. (Unless I'm missing something, if you substitute perp-dot for dot in the pseudocode that he posted, it will indeed work for any convex polygon, including triangles.)
Quote:But it is the simplest method for rects anyway.I think it can get a bit simpler, e.g.:
vector2 diff = p - center;return abs(dot(diff, axis1)) <= extent1 && abs(dot(diff, axis2)) <= extent2;This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
