• Advertisement
Sign in to follow this  

[Java] Rectangle Collision

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

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


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
Small correction. Dont actually need step 4, its equivalent to step 3!


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

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

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 Separating Axis therorem Also saw another thread about this on Gamedev

[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

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
Sign in to follow this  

  • Advertisement