Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Hippokrates

Rects

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

How can I check if 2 rects that look like this do intersect or something like that:
struct Point {
float x, y, z;
};

struct Rect {
Point UpperLeft;
Point UpperRight;
Point LowerLeft;
Point LowerRight;
};
 
I do need to know if an least one point of one of them is contained within the other or if the intersect someway.

Share this post


Link to post
Share on other sites
Advertisement
Here''s a suggestion: First try to fiqure out the 1-dimensional case (if 2 ''horizontal lines'' intersect). Then try fiquring out the 2-dimensional case for rectangles. It''ll probably be easier to start that way.

I wonder why your point-struct has z-member even though you''re in 2 dimensions. Also, rectangle should only consist of 2 corners (the opposite ones) to keep it simple (alternatively you could use 1 point and width and height).

E.g

struct Point {
float x, y;
};

struct Rect {
Point UpperLeft;
Point LowerRight;
};

Share this post


Link to post
Share on other sites
Who said I was in 2 Dimensions? If I were in 2 Dimensions I would not have this problem ;-).
I am in 3 dimensions all right.
A rect can be oriented in space, can`t it ?

Share this post


Link to post
Share on other sites
Ok, seems like I misunderstood. As if that was something new

Well, a pretty straightforward (but maybe slow) way to test the intersection:

You have vectors that create the rectangle (only 3 is needed)

  struct Rect {
Vector upperLeft, width, height;
}

Ok.. Then for the rectangle b you test if any of it's bounding lines intersect rectangle a:

    
bool rect2rectCollision(Rect &a, Rect &b) {
return (ray2RectCollision(a, b.upperLeft, width) ||
ray2RectCollision(a, b.upperLeft, height) ||
ray2RectCollision(a, b.upperLeft+width, height) ||
ray2RectCollision(a, b.upperLeft+height, width));
}

ray2RectCollision() takes these arguments:
1.rectangle (Rect &a)
2.where the ray begins (Vector &begin)
3.what direction the ray points at (Vector &dir). The ray's end is at begin+"where it points"

For ray2RectCollision(Rect &a, Vector &begin, Vector &dir)
you need to solve this equation (solvable variables are k, x and y, but you only need x and y):

begin + k * dir == a.upperLeft + x * a.width + y * a.height

And if 0<=x<=1 and 0<=y<=1, then return true, otherwise false. I solved that equation in Mathematica, but it's too long for me to write down here and you can do it yourself too

[edited by - civguy on September 13, 2002 10:48:31 AM]

Share this post


Link to post
Share on other sites
Ay, this is a lot of math.
But what do you mean by " solve this equation: begin + k * dir == a.upperLeft + x * a.width + y * a.height" ?
I do of course know how to solve equations (as long as you keep em simple like 5x = 10 ).
But to what shall I solve this?

Share this post


Link to post
Share on other sites
Do you know how to solve multiple equations?

{x * 2 = 2 * y + 1
{x + y = 3

There you can first solve x in the first equation:
x = y + 1/2
and then replace the x in the latter equation with that one:
(y + 1/2) + y = 3
And solve y. Then you can replace the y in the first equation with the number, and you have solved both x and y

Well,

begin + k * dir == a.upperLeft + x * a.width + y * a.height

is nothing but three equations, written as one . I''ll write it fully here:

{ begin.x + k * dir.x == a.upperLeft.x + x * a.width.x + y * a.height.x
{ begin.y + k * dir.y == a.upperLeft.y + x * a.width.y + y * a.height.y
{ begin.z + k * dir.z == a.upperLeft.z + x * a.width.z + y * a.height.z

Yup.. that''s 3 equations, where you need to solve 3 unknown variables, k, x and y (everythin else is known). You could start by solving ''k'' from the first equation, then replace the ''k'' value in the last two equations with the ''k'' you got in the first equation. Then solve x and put it''s solution in the last equation. And so on. Spend your night doing that and have a nice youth

Share this post


Link to post
Share on other sites
Whoops, I just realized something!
'k' must be 0<=k<=1 too. So the function ray2RectCollision() would be something like this:

    
bool ray2RectCollision(Rect &a, Vector &begin, Vector &dir) {
//solve k, x and y here :)


return (0<=k && k<=1 && 0<=x && x<=1 && 0<=y && y<=1);
}

Or if you want to optimize for speed

          
bool ray2RectCollision(Rect &a, Vector &begin, Vector &dir) {
//solve k here

if (k<0 || k>1) return false;
//solve x here

if (x<0 || x>1) return false;
//solve y here

return (0<=y && y<=1);
}

edit: perhaps with bool return type instead of void

[edited by - civguy on September 14, 2002 7:54:28 PM]

Share this post


Link to post
Share on other sites

  • 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!