# 2D Object Intersection

Hi there!

I’m Rob, and welcome to my section of the XG hive mind! I wanted somewhere to store and talk about solved / partially solved issues that crop up during development. Hopefully it’ll be semi-blog style, and not just the outpouring of this poor crazed programmers ravaged mind! Lets get into it!

## The Problem

Ok, so here at XG we’re currently working on some procedural content ideas. I’ve been looking to place object in 2D space, and not have them intersect.

Each object has a bounding volume/box and to make life easy is Axis Aligned (AABB), each object can be any size.

Now it’s a simple test to see if two AABB hit each other:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class AABB { Vector2 Min; Vector2 Max; Vector2 Size; bool IsHit(AABB In) { if (In.Min.x > Max.x) return (false); // In is to the Right (+x) if (In.Max.x < Min.x) return (false); // In is to the Left (-x) if (In.Min.y > Max.y) return (false); // In is Above (+y) if (In.Max.y < Min.y) return (false); // In is Below (-y) return(true); } } |

#### Diag 1: Edges of Box for testing

As you can see we Test all 4 Edges to see if they are outside the bounds of the box, but what this does not tell us is what sides/edges where hit! This is important for us to be able to separate intersecting objects. The possible intersections are as follows:

#### Diag 2: Test Cases 1-4

I tried a few options to see which edges were hit, but in the end the best option seemed to be to test which corner was inside the box and extrapolate the result from there.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Test if Point is inside box bool IsHit(Vector2 In) { if (In.x > Max.x) return (false); if (In.x < Min.x) return (false); if (In.y > Max.y) return (false); if (In.y < Min.y) return (false); return(true); } int DirectionHit(AABB In) { int CornersHit = 0; // Bit Flag int EdgeHit = 0; // Bit Flag if (IsHit(In.Min)) CornersHit |= 1; // Lower Left if (IsHit(In.Min + In.Size.x)) CornersHit |= 2; // Lower Right if (IsHit(In.Max)) CornersHit |= 4; // Upper Right if (IsHit(In.Min + In.Size.y)) CornersHit |= 8; // Upper Left if ((CornersHit & 0x03) == 0x03) EdgeHit |= 1; // Lower if ((CornersHit & 0x06) == 0x06) EdgeHit |= 2; // Right if ((CornersHit & 0x0C) == 0x0C) EdgeHit |= 4; // Upper if ((CornersHit & 0x09) == 0x09) EdgeHit |= 8; // Left return (EdgeHit); } |

## Things to Note

First, the Objects need to be tested A.DirectionHit(B) and B.DirectionHit(A) to Satisfy test 3.

Second, this code will fail the fourth test. This is because none of the points are ever inside the a box, but the edges pass through.

## Conclusions?

Once we can find these intersection by testing, we can then solve them. Solving is fairly simple and just a matter of moving the Object based on which edge is hit. The complexity grows has the number of objects increase too, but that’s another problem entirely!

Looking back at what I said right at the start, I think we’ll categorize this post under option 2!