Background
I'm looking to do this programmatically in Java, but if desired you can post solutions in C/C++ or plain English instructions if you're not a programmer, but I would appreciate an explanation as to why your code/instructions solves the problem of detecting a collision for my own understanding.
The reason I'm interested in a such a form of collision detection is because I figure it would help to simplify detecting whether a character (essentially a non-axis aligned rectangular prism) and an axis-aligned rectangular prism have collided. As I may need to do this calculation quite a bit depending on the size and density of the rectangular prisms needed, I would like to find a more optimal solution than simply checking if any of the line segments of the character's "box" collide with any of the line segments of the rectangular prism's "box". It would be preferable as well to have a way of "deflecting" the character after collision in such a way that I can reset the character so it is no longer colliding with the object, but I can ask this in another question if necessary.
Definition of Key Terms
Let me explicitly define what I want here to ensure clarity.
I define a collision as meeting any of the following conditions:
- The outline of the non-axis aligned rectangle intersects with the outline of the axis-aligned rectangle at at least one point.
- Either rectangle is inside of the other.
I define AABB (axis-aligned bounding box) to be the following:
- A standard rectangle with two sides parallel to the x-axis and two sides parallel to the y-axis.
I define non-AABB to be the following:
- A standard rectangle that has either 2 or no sides parallel to the x-axis and has either 2 or no sides parallel to the y-axis. Also, if the figure is rotated, its theta begins at the x-axis and the figure goes counter-clockwise as theta grows towards positive infinity.
Definition of Variables
(x, y) - the leftmost corner of the AABB figure
(x1, y1) the leftmost corner of the non-AABB figure
w - the width of the AABB figure
h - the height of the AABB figure
w1 - the width of the non-AABB figure
h1 - the height of the non-AABB figure
theta - rotation in degrees of the non-AABB figure
There are three different conditions that need to be tested for. If at least one is true, then a $collision$ by your definition can be said to have occurred.
1) At least one vertex of the non-AABB is within the the boundaries of the AABB: easy to identify.
2) At least one vertex of the AABB is within the the boundaries of the non-AABB: easy to identify.
3) No vertices of either lie within the boundaries of the other, but there is still an overlap - think of two rectangles at right angles to each other making a cross shape: I think this is hard to identify.
I'll start with how you can identify condition 1.
Let the vertices of the non-AABB be $(x_i,y_i)$ for $i \in \{1,2,3,4\}$
$(x_1,y_1)$ is given.
$(x_2,y_2)= (x_1-h_1 \sin \theta,y_1+h_1 \cos \theta)$
$(x_3,y_3)= (x_1-h_1 \sin \theta+w_1 \cos \theta,y_1+h_1 \cos \theta+w_1 \sin \theta)$
$(x_4,y_4)= (x_1+w_1 \cos \theta,y_1+w_1 \sin \theta)$
A vertex $(x_i,y_i)$ lies within the boundary of the AABB if $x\leq x_i \leq x+w$ and $y\leq y_i \leq y+h$.
Test if $\left(x_i-x\right)\left(x_i-x-w\right)\leq 0$ and $\left(y_i-y\right)\left(y_i-y-h\right)\leq 0$
Condition 2 is essentially the same. Rotating the whole system clockwise by $\theta$ makes the AABB into a non-AABB and vice versa.
The vertices of the AABB that is now a non-AABB are:
$(x'_1,y'_1)=\left(x \cos \theta +y\sin \theta, y \cos \theta - x \sin \theta \right)$
$(x'_2,y'_2)=\left(x \cos \theta +y\sin \theta, (y+h) \cos \theta - x \sin \theta \right)$
$(x'_3,y'_3)=\left((x+w) \cos \theta +y\sin \theta, (y+h) \cos \theta - x \sin \theta \right)$
$(x'_4,y'_4)=\left((x+w) \cos \theta +y\sin \theta, y \cos \theta - x \sin \theta \right)$
A vertex $(x'_i,y'_i)$ lies within the boundary of the non-AABB that is now an AABB if $x_1 \cos\theta -y_1\sin\theta\leq x'_i \leq x_1 \cos\theta -y_1\sin\theta+w_1$ and $y_1 \cos\theta +x_1\sin\theta\leq y'_i \leq y_1 \cos\theta +x_1\sin\theta+h_1$.
Test if $\left(x'_i-x_1 \cos\theta +y_1\sin\theta\right)\left(x'_i-x_1 \cos\theta +y_1\sin\theta-w_1\right)\leq 0$ and $\left(y'_i-y_1 \cos\theta -x_1\sin\theta\right)\left(y'_i-y_1 \cos\theta -x_1\sin\theta-h_1\right)\leq 0$