• 12
• 14
• 13
• 10
• 11

Point inside rect, what is wrong with my logic?

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

Recommended Posts

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

Share on other sites
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.

Share on other sites
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

Share on other sites
Your code does not even read pt, so it couldn't possibly work !

Share on other sites
Quote:
 Original post by SriLumpaYour 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

Share on other sites
Quote:
 Original post by alvaroWhy 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

Share on other sites
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

}

Share on other sites
Quote:
 Original post by shultaysI tried to explaining in my previous post, here is a code exampleVector pt //point to testVector p1, p2, p3, p4 //corners of rectangle//Vector v1 = p2 - p1; //find edge vectorsVector 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

Share on other sites
Quote:
 Original post by shultaysto find if a point inside of a rectangle (for example a b c d) you first find 4 vectors for each sideb-ac-bd-ca-dif 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 pointdot(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.

Share on other sites
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;