Jump to content
  • Advertisement
Sign in to follow this  
FFMG

Point inside rect, what is wrong with my logic?

This topic is 3324 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

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


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

Share this post


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

Share this post


Link to post
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 this post


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

Share this post


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

Share this post


Link to post
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;

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!