Jump to content
  • Advertisement

Archived

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

Blue*Omega

Collision between rectangles

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

Just getting different opinions... What''s do you think is the fastest way to detect if two rectangles are ovelapping? I already have a method (which I won''t post her for fear of being laughed off the message board) but would like to see what else you guys have got. Just so you all know, i''m using the standard RECT class: typedef struct { int top, left, bottom, right; } RECT Thanx! ^_^ ----------------------------- Vash the Stampede "Love & Peace!"

Share this post


Link to post
Share on other sites
Advertisement
2d, but I guess it doesn''t really matter. It might be nice to know a couple of 3d methods. But yes, if you look at the RECT struct it only has top/right-bottom/left. In order to be 3d you would need a front/back as well.

-----------------------------

Vash the Stampede

"Love & Peace!"

Share this post


Link to post
Share on other sites
I think you just have to "project" the y and x direction intervals to the one ray and check their intersection. ..if both directions have an intersection the the collide. Nothing faster doesn''t exist or at least I think so.

Dave007
dave007@volny.cz

Share this post


Link to post
Share on other sites
I guess if you pretend each rectangle has two diagonals from corner to corner and test for intersection. This won''t work if one of the rectangles is also rotated.

hmm...

so say rectangle one is ((1,1) - (100,100));

so, the equation of the diagonal is y = MX + B

M is the slope, or Y2- Y1
------
X2 -X1

in this case, would be 1.
B is 1 (the offset from zero)
so the equation is Y = X + 1

rectangle two is (100,100) - (1,1)

in this case, Y = -X + 101

To test intersection, the equation is:

X + 1 = -X + 101

which simplifies to:

X = -X + 100
2X = 100
X = 50

Doublechecking:

Y = (50) + 1 = 51
Y = -(50) + 101 = 51

So yes, they do intersect, and they intersect exactly halfway through (X = 50).

Dunno how well any of this translates to computer programming, but just a idea I had

BTW you would need two diagonals for each rectangle, and you would have to perform two tests.

Share this post


Link to post
Share on other sites
Are you counting when one rectangle is completely inside another?

Superpig
- saving pigs from untimely fates
- sleeps in a ham-mock at www.thebinaryrefinery.cjb.net

Share this post


Link to post
Share on other sites
rectangle collision detection is female dog to say the least. if yoru rects can rotate, you have a major problem to contend with since most tutorials dont deal with that aspect. my algo handles it quite well though may not be optimal.

first off you will use two version of the bound box, rotated and unrotated. (this was done in an overhead shooter similar to subspace but withoutt he shooting part and ships could collide and not get destroyed so it was kinda like bumber ships)

this algo assumes:
1. that the unrotated version will match an unrotated sprite which makes sense.
2. that points are in 2d space, you could though adapt for 3d space (quite easily actually) once you understand the algo and the concpet behind it.

definations:
sprite1 is the sprite checking for collide
sprire2 is the sprite being checked with (i did it in a class fucntion)
all sprites store their own angle varible which represenst the anbgle at which they are rotated (obviously)
this technique makes more sense if you understand what is being done, which is basically converting coordinate space like in 3d camera transformations.

rotbox1: rotated bound box for sprite1
rotbox2: rotated bound box for sprite2
nonbox1: non rotated bound box for sprite1
nonbox2: non rotated bound box for sprite2
the algo:

1. find the non rotated version of the bounding box of sprite1
2. rotate the rotbox2 with the negeative angle that sprite1 is rotated (converts sprite2box into sprite1 coordinate space)
3. if any of the rotbox2 points are in the nonbox1, you got collision. (simple point in rect check)
4. now the reverse, get nonbox2.
5. rotate rotbox1 using the reverse angle of sprite2
6. if any or rotbox1 points are in nonbox2 then you got collision (simple point in rect check)


this works in the following cases:
1. both sprites are rotated
2. only one sprite is rotated
3. one sprite is totally inside the other sprite
4. actually all cases

i WILL NOT post code regarding this. the algorithm is pretty easy to code and should pose very little resistence. i will however clarify the algo if you need me to, since some of my expliaination may be fuzzy.



Edited by - a person on December 9, 2001 11:57:46 PM

Share this post


Link to post
Share on other sites
The way I do it is check to see if any vertex of one rectangle is inside the other one. Not too robust, but has worked great for me so far If your rectangles are rotating, then its not so easy of course

Share this post


Link to post
Share on other sites
Okay, this is just spun out of thought, but it seems the simplest approach to me (for rotated rects, as was mentioned previously, the passed-in rects can either be the bounding box before rotation (based on the situation, close enough might work) or a new bounding box that is computed based on rotated-box coordinates.

//(assume: typedef struct RECT {int right; int left; int top; int bottom; };

bool Collision2D(RECT box1, RECT box2)
{

bool horizontal = true;
bool vertical = true;

if (box1.right > box2.left) horizontal = !horizontal;
if (box1.left < box2.right) horizontal = !horizontal;
if (box1.bottom > box2.top) vertical = !vertical;
if (box1.top < box2.bottom) vertical = !vertical;

if (horizontal && vertical) return true;

return false;

} // end Collision2D

This will work for overlapping rectangles as well as rectangles that are one inside the other. Not bad for the first thing that came to mind, I guess.

"Man is the only animal that laughs and weeps; for he is the only animal that is struck with the difference between what things are and what they ought to be."
        --William Hazlitt

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!