Allegro.cc Forums » Programming Questions » Collision with rotated rectangles.

 Collision with rotated rectangles.
 Chris Katko Member #1,881 January 2002 Is there an easy way to do collision detection with two rotated rectangles?I keep finding articles on "bounding box around a rotated rectangle" and that's not what I want. I don't want a gigantic box around a rectangle when it's rotated by 45-degree. I just want to check whether two rotated rectangles are colliding.Think GTA 1 with cars rotating around.{"name":"latest","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/e\/5efbcada3e8e2467d5d7a2920075bf7a.png","w":800,"h":600,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/e\/5efbcada3e8e2467d5d7a2920075bf7a"} -----sig:“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs"Political Correctness is fascism disguised as manners" --George Carlin
 anto80 Member #3,230 February 2003 In this case I'm using 2 inner rectangles.One of them with larger width, and the other with larger height. These 2 stay inside the original rotated rectangle.Thats not a very accurate solution but it's fast.Another slower way would be to calculate distances between the 2 center points, with sqrt. And compare it to rectangle size.More accurate but not the top of the accuracy either. ___________Currently working on his action/puzzle game CIPHER PUSHER : Blocks/Vortexes/Seafood! Facebook - Twitter - webpage
 Rodolfo Lam Member #16,045 August 2015 You could use instead circles for collision detection. You would test if the radius of each circle intercept. The borders of the rectangles will not trigger collisions, but its also fast
 l j Member #10,584 January 2009 http://www.metanetsoftware.com/technique/tutorialA.htmlEverything you need and more as far as I can tell.Well at least the basic math you need, all examples include AABBs but the technique works for non aligned boxes as well.
Johan Halmén
Member #1,550
September 2001

Is one point inside a triangle?
Shouldn't be hard to find out.
Are any of three points inside of a triangle?
Three times more work, but equally easy.
Are two triangles colliding?
Doubles the work of previous step, but equally easy.

So how would I do the first step?
Find center point of one triangle, it is always inside the triangle.
Take one vertex of the other triangle. Check if it's on same side of one side as the center point. Repeat for all three sides.

P is the middle point that you know is inside the triangle. X is a vertex of another triangle. Form the vectors AB, AX and AP. Check the cross products ABxAX and ABxAP. If the results are vectors pointing in the same directions, X and P are on the same side of the line AB[1]. Of course, X could still be outside the triangle, far to the left. But just repeat with the two other sides of the triangle.

## References

1. If the resulting vectors point in opposite directions, X and P are on opposite sides of AB. Since your triangle and P and X are all in one plane, everything is just in an xy world and the vectors only have i and j components. But you need the z dimension and its k vector component for the cross product. And the sign of this k component tells you if your resulting vectors point in the same direction. Same sign => X and P are on same side of AB. Not same sign => X and P are on opposite sides of AB.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

 Polybios Member #12,293 October 2010 Don't know whether this would work, but I'd start with checking on which side of the edges of rectangle R the 4 vertices of rectangle S are (i.e. "inside / outside" side). One check for vertex V against edge CD (of rectangle ABCD) would be:Take the "normal" of an edge which is another edge in the rectangle case: (A-C) pointing "inside". Check the sign of the dot product of (A-C) dot (V-C). If it's positive, V lies on the "inside" side of CD. I don't know if you could infer collision status from the 16 results. You can safely stop if all 4 vertices are on the "outside" side of one edge, though. And you can stop as soon as you have found a vertex that is on the inside side of all edges. So this would require about 32 vector subtractions and 16 dot products. Edit: Actually, it might well be that you need to check with the rectangles reversed, too. So it would take 32 dot products in the worst case. But you could probably exclude some of the cases. Oh well. I'd just follow the link Aaron provided.
 Johan Halmén Member #1,550 September 2001 So why did I think triangles, when the OP was about rectangles? You can't just check if one vertex is inside the other rectangle. All vertices can be outside and still the rectangles collide. Just put them across each other. How about checking two line segments AB and CD and check where the lines cross. Be it point P. Is P inside the line segment AB? Is it inside CD? If both are true, there's a collision. You have to check 4 sides against 4 sides. Checking 2 sides, you find the crossing point. Then you check the point against both sides. Well, that would be at least 32 calculations of some kind. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.
 Chris Katko Member #1,881 January 2002 Perhaps this is more complex than necessary, but last night I was thinking (which I think others have suggested): - Convert all points to axis-aligned with rectangle A - For the four points in rectangle B, check if any are inside rectangle A.Johan Halmén said: All vertices can be outside and still the rectangles collide. How? Unless we're talking about very large/small rectangles--one rectangle completely inside the other? My knowledge of geometry, linear algebra, and trig is very stale (years!) and I never learned as much as I wish I would have. So I've seen some articles but I think I need to be "walked through" solutions a little more than usual on this topic. -----sig:“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs"Political Correctness is fascism disguised as manners" --George Carlin
 jmasterx Member #11,410 October 2009 I attempted this a few years ago on android https://github.com/jmasterx/BloodshedAndMayhemI used OrientedBoundingBox collision detection. You might find something useful in it.https://github.com/jmasterx/BloodshedAndMayhem/blob/master/src/com/jkgames/gta/OBB2D.javaI first check if the bounding boxes intersect, if they do, and the angles are not 0, do the expensive SAT test. Agui GUI API -> https://github.com/jmasterx/Agui Agui 0.2 Release Thread -> https://www.allegro.cc/forums/thread/612830
 Polybios Member #12,293 October 2010 Chris Katko said:How? Unless we're talking about very large/small rectangles--one rectangle completely inside the other? Think of a cross...Johan Halmén said: You can't just check if one vertex is inside the other rectangle. My approach would have been to calculate 16 bits indicating whether the four points of R are on the "inside" or "outside" side of the edges of S and then deal with the 65536 cases. Which, by the way, wouldn't be enough. You would have gotten the "cross" case right, though, I think. "Projecting" / the SAT test is the way to go, I guess. It's more or less a similar, but more elegant approach that reduces complexity: For every edge involved, take its normal as projection axis and project all the vertices onto it. Take the min/max of both rectangle's vertices projections and check for overlap. If there's one axis where the projections don't overlap, there's no collision. So with 2 rectangles, there's 4 different normals and 8 vertices to project for each, which leads to 32 calculations in the worst case.
 Chris Katko Member #1,881 January 2002 Polybios said: Think of a cross... That's interesting. I wonder how "effective" I could be by merely adding a fifth point in the center, or even a "rectangle" but with points at half-widths along each line.8 or 9 points, and smaller "vehicles" won't need those extra points.I wonder how effective, and fast it would be compared to other algorithms. Game mechanics-wise, I'm pretty sure it would be fine. -----sig:“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs"Political Correctness is fascism disguised as manners" --George Carlin
 Mark Oates Member #1,146 March 2001 SAT is the right way to do this. I like jmasterx's idea of using a bigger bbox first before going in for the SAT. --Streaming KrampusHack 2020 LIVE on Twitch - (status: ⭕️ OFFLINE) - https://twitch.tv/markoates)AllegroFlare • allegro.cc markdown • Allegro logo
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads