How do I test if an AABB and concave polygon intersect?

Question

The player's collider is an axis-aligned bounding box in my 2D platformer, but the environment can be different shapes. I already have collision-detection that prevents the player from going through colliders, but I don't have anything for getting the player out of concave polygons if he ends up inside one by for example flipping the collider when changing direction from/to left/right.

SAT doesn't work on concave polygons, so I need an algorithm that can tell me if an AABB and any polygon intersects and give me the minimum translation vector to push the shapes apart. (The velocity of the objects will not need to be considered).

BTW the game is written in C# with the MonoGame framework if that's of any relevance.

Answer 1

If your game starts with the player AABB completely outside of the concave polygon, then I would solve an easier problem:

Test the edges (line segments) of the polygon against the AABB. If you have an intersection, just push out the AABB so it is on the correct side of the linesegment.

Your polygon is probably counter-clockwise, so you know which part of the edge is "inside" and which part of the edge is "outside."

Beware this can cause "tunnelling" if your AABB moves too fast and goes from completely outside the polygon to completely inside the polygon within a single simulation step.

To do edge-versus-AABB in 2D, you can use the Cohen-Sutherland algorithm.

Answer 2

Intersecting a polygon P with a box/rectangle R is the essence of clipping, so you could use a clipping algorithm. There are several, e.g., the Cohen-Sutherland algorithm. A box R and a polygon P intersect if (and only if), when you clip P to the box R, the result is not empty, i.e., some parts of P are inside R.