# 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 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;

##### 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.

<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

##### 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 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

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 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 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 rectangleif((p.x >= v1.x && p.x <= v2.x) && (p.y >= v1.y && p.y <= v2.y))return(true);elsereturn(false);

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

##### Share on other sites
The rectangle is rotated.
Fuck, I'm spending too much time here....

##### Share on other sites
Quote:
 Original post by szecsThe rectangle is rotated.Fuck, I'm spending too much time here....

Well, yeah, that would be a good reason...

##### Share on other sites
Quote:
 Original post by szecsNo. 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 on other sites
Quote:
 Original post by maspeirHow 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 rectangleif((p.x >= v1.x && p.x <= v2.x) && (p.y >= v1.y && p.y <= v2.y))return(true);elsereturn(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 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...

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628283
• Total Posts
2981823

• 10
• 10
• 11
• 17
• 15