Sign in to follow this  
FFMG

Point inside rect, what is wrong with my logic?

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
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
Quote:
Original post by szecs
Quote:
Original post by shultays

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.


He wanted an algorithm for rectangles. Algorithm will work for any number of sides, as long as it is a convex polygon (since triangles are always convex, it will work)

here is an example what does it do.

Image Hosted by ImageShack.us<br/>

you check the angle between a-b and a-n vectors, if it is positive n is on the correct side of a-b.

after that you do the same process for all other edges b-c and b-n, and c-a and c-n. if all angles are positive point is inside of the triangle

you can increase the edges and it should work

edit: forgot to add image

Share this post


Link to post
Share on other sites
No. It means it is on the correct side of the line, that's perpendicular to a-b, but not a-b itself. So all points will pass the test, which are in a bigger triangle what's sides are perpendicular to the sides of the original triangle.

Your statement works with cross products, not dot products.
In your drawing, if n is on the opposite side of a-b, it can have the same dot product with the a-b (just mirror n to a-b)
So you probably mixed dot and cross products.

Share this post


Link to post
Share on other sites
Quote:
Original post by shultays
Quote:
Original post by szecs
Quote:
Original post by shultays

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.


He wanted an algorithm for rectangles. Algorithm will work for any number of sides, as long as it is a convex polygon (since triangles are always convex, it will work)

here is an example what does it do.

*** image clipped ***

you check the angle between a-b and a-n vectors, if it is positive n is on the correct side of a-b.

after that you do the same process for all other edges b-c and b-n, and c-a and c-n. if all angles are positive point is inside of the triangle

you can increase the edges and it should work

edit: forgot to add image
Have you actually tested your algorithm, as described in your original post? I'm unable to see how it would work with respect to general convex polygons.

The idea of testing the signed angle is reasonable, but that isn't what your pseudocode does. (It's probably also worth noting that it's not necessary to compute the angle itself when performing the test.)

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
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;


I didn't noticed that, yes of course it works with perp-dot, but not with simple dot, although I didn't know that term before, it's in 2D only I suggest. It seems like the 2D version of cross product, but it's just a guess...

EDIT: I see, perp-dot exists in 3D too, but in 2D, it is the same as 2D cross product (v=a1*b2-a2*b1), if anybody interested....

[Edited by - szecs on September 13, 2009 12:54:03 PM]

Share this post


Link to post
Share on other sites
How is calculating the dot product several times easier or faster than this:


//v1 is the top left of the rectangle
//v2 is the bottom right of the rectangle
if((p.x >= v1.x && p.x <= v2.x) && (p.y >= v1.y && p.y <= v2.y))
return(true);
else
return(false);


This will work for any 2D rectangle and 2D point.

Share this post


Link to post
Share on other sites
Quote:
Original post by szecs
No. It means it is on the correct side of the line, that's perpendicular to a-b, but not a-b itself. So all points will pass the test, which are in a bigger triangle what's sides are perpendicular to the sides of the original triangle.

Your statement works with cross products, not dot products.
In your drawing, if n is on the opposite side of a-b, it can have the same dot product with the a-b (just mirror n to a-b)
So you probably mixed dot and cross products.


oh, I feel like an idiot. I meant cross product =(

Share this post


Link to post
Share on other sites
Quote:
Original post by maspeir
How is calculating the dot product several times easier or faster than this:


//v1 is the top left of the rectangle
//v2 is the bottom right of the rectangle
if((p.x >= v1.x && p.x <= v2.x) && (p.y >= v1.y && p.y <= v2.y))
return(true);
else
return(false);


This will work for any 2D rectangle and 2D point.


I was thinking the exact same thing. Was wondering what was with all the dot products and what not. Thought they were aiming to kill kittens with a trebuchet trebushe catapult.

Didn't know the rectangle was being rotated. But, it makes sense now.

Share this post


Link to post
Share on other sites
I'm too old school. A rectangle for me is always aligned to the screen, otherwise it is a polygon. My old (pre-OS X, like OS 4 and up) Mac programming background coming to the surface...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this