Sign in to follow this  
Matthew Shockley

[Java] Rectangle Collision

Recommended Posts

What is the best way to find if two rectangles are colliding if one of them is always axis-aligned and the other is rotated? Both classes have a size and position vector and the rotated rectangle has an angle property. I don't want to implement physics on these rectangles, just to see if they are colliding.

Share this post


Link to post
Share on other sites
Short answer: Separating axis test. (In general it's the SAT for oriented rectangles/boxes that you want, although the test can be optimized for the case where one of the rectangles is axis-aligned.)

Share this post


Link to post
Share on other sites
What you need to do is first of all test to see if the vertices of any rectangle are inside the other. If they are, theres a collision.
Next you need to test if the boxes overlap. You could have a situation where the boxes overlap in a sort of plus sign shape, where no vertices of either rectangle are inside the other. To test for this, test for each edge of each box overlapping the edges of the other box.

In plain english, what you do is:
1.Check to see if vertices of 1st rectangle are inside 2nd. If they are, the rectangles collide and your test is done
2.Repeat 1 with rectangles swapped
3.Check all edges of 1st rectangle with those of 2nd, if they intercept then theres a collision, test done
4. Repeat 3 with rectangles swapped
5.If get here, no collision

Now translate it into maths and program it!

[quote name='jyk' timestamp='1307058161' post='4818906']
Short answer: Separating axis test. (In general it's the SAT for oriented rectangles/boxes that you want, although the test can be optimized for the case where one of the rectangles is axis-aligned.)
[/quote]

Share this post


Link to post
Share on other sites
Small correction. Dont actually need step 4, its equivalent to step 3!

[quote name='Paul65' timestamp='1307073173' post='4818938']
What you need to do is first of all test to see if the vertices of any rectangle are inside the other. If they are, theres a collision.
Next you need to test if the boxes overlap. You could have a situation where the boxes overlap in a sort of plus sign shape, where no vertices of either rectangle are inside the other. To test for this, test for each edge of each box overlapping the edges of the other box.

In plain english, what you do is:
1.Check to see if vertices of 1st rectangle are inside 2nd. If they are, the rectangles collide and your test is done
2.Repeat 1 with rectangles swapped
3.Check all edges of 1st rectangle with those of 2nd, if they intercept then theres a collision, test done
4. Repeat 3 with rectangles swapped
5.If get here, no collision

Now translate it into maths and program it!

[quote name='jyk' timestamp='1307058161' post='4818906']
Short answer: Separating axis test. (In general it's the SAT for oriented rectangles/boxes that you want, although the test can be optimized for the case where one of the rectangles is axis-aligned.)
[/quote]
[/quote]

Share this post


Link to post
Share on other sites
[quote name='Paul65' timestamp='1307073173' post='4818938']
What you need to do is first of all test to see if the vertices of any rectangle are inside the other. If they are, theres a collision.
Next you need to test if the boxes overlap. You could have a situation where the boxes overlap in a sort of plus sign shape, where no vertices of either rectangle are inside the other. To test for this, test for each edge of each box overlapping the edges of the other box.

In plain english, what you do is:
1.Check to see if vertices of 1st rectangle are inside 2nd. If they are, the rectangles collide and your test is done
2.Repeat 1 with rectangles swapped
3.Check all edges of 1st rectangle with those of 2nd, if they intercept then theres a collision, test done
4. Repeat 3 with rectangles swapped
5.If get here, no collision[/quote]
Actually, none of that is necessary. For boxes in 2-d there's no need to perform per-feature tests (e.g. point containment and segment intersection), and in fact a test implemented in that way will likely be less efficient than the alternative.

The separating axis test will catch all cases, and doesn't require any per-feature tests. (Rather, the presence or absence of intersection is determined by a series of simple 1-d projections.)

Share this post


Link to post
Share on other sites
Yes, maybe your way is simpler, was just reading about it on wikipedia [url="http://en.wikipedia.org/wiki/Separating_axis_theorem"]Separating Axis therorem[/url] Also saw another thread about this on [url="http://www.gamedev.net/topic/111327-separating-axis-test/"]Gamedev[/url]
[quote name='jyk' timestamp='1307073609' post='4818942']
[quote name='Paul65' timestamp='1307073173' post='4818938']
What you need to do is first of all test to see if the vertices of any rectangle are inside the other. If they are, theres a collision.
Next you need to test if the boxes overlap. You could have a situation where the boxes overlap in a sort of plus sign shape, where no vertices of either rectangle are inside the other. To test for this, test for each edge of each box overlapping the edges of the other box.

In plain english, what you do is:
1.Check to see if vertices of 1st rectangle are inside 2nd. If they are, the rectangles collide and your test is done
2.Repeat 1 with rectangles swapped
3.Check all edges of 1st rectangle with those of 2nd, if they intercept then theres a collision, test done
4. Repeat 3 with rectangles swapped
5.If get here, no collision[/quote]
Actually, none of that is necessary. For boxes in 2-d there's no need to perform per-feature tests (e.g. point containment and segment intersection), and in fact a test implemented in that way will likely be less efficient than the alternative.

The separating axis test will catch all cases, and doesn't require any per-feature tests. (Rather, the presence or absence of intersection is determined by a series of simple 1-d projections.)
[/quote]

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