Algorithm to check if two boxes overlap

Efficiently Detecting Overlapping Rectangles (Boxes)

Learn the fundamental algorithms and practical implementations for determining if two rectangular boxes intersect in 2D space, a common problem in game development, UI design, and collision detection.

Detecting whether two rectangular boxes overlap is a surprisingly common problem in various fields, from game development for collision detection to UI layout management and geographic information systems. While seemingly simple, a robust and efficient algorithm is crucial, especially when dealing with many objects. This article will explore the core logic behind 2D box overlap detection, focusing on axis-aligned bounding boxes (AABBs), and provide practical code examples.

Understanding Axis-Aligned Bounding Boxes (AABBs)

An Axis-Aligned Bounding Box (AABB) is a rectangle whose sides are parallel to the coordinate axes (x and y). This simplification makes overlap detection much easier than with arbitrarily rotated rectangles. We typically define an AABB by its minimum and maximum coordinates along each axis. For example, a box can be defined by (minX, minY) and (maxX, maxY) or by its (x, y) origin, width, and height.

flowchart LR
    subgraph Box A
        A_minX[A.minX] --> A_maxX[A.maxX]
        A_minY[A.minY] --> A_maxY[A.maxY]
    end
    subgraph Box B
        B_minX[B.minX] --> B_maxX[B.maxX]
        B_minY[B.minY] --> B_maxY[B.maxY]
    end
    A_minX -- x-axis range --> A_maxX
    A_minY -- y-axis range --> A_maxY
    B_minX -- x-axis range --> B_maxX
    B_minY -- y-axis range --> B_maxY
    style A_minX fill:#f9f,stroke:#333,stroke-width:2px
    style A_maxX fill:#f9f,stroke:#333,stroke-width:2px
    style A_minY fill:#f9f,stroke:#333,stroke-width:2px
    style A_maxY fill:#f9f,stroke:#333,stroke-width:2px
    style B_minX fill:#bbf,stroke:#333,stroke-width:2px
    style B_maxX fill:#bbf,stroke:#333,stroke-width:2px
    style B_minY fill:#bbf,stroke:#333,stroke-width:2px
    style B_maxY fill:#bbf,stroke:#333,stroke-width:2px

Representation of two Axis-Aligned Bounding Boxes (AABBs) by their min/max coordinates.

The Non-Overlapping Condition (Separating Axis Theorem)

The most intuitive way to check for overlap is often to check for non-overlap. Two AABBs do not overlap if there is a gap between them along either the X-axis or the Y-axis. This is a simplified application of the Separating Axis Theorem (SAT) for AABBs.

Specifically, two boxes, Box A and Box B, do not overlap if:

1. Box A's right edge is to the left of Box B's left edge (A.maxX < B.minX)
2. Box B's right edge is to the left of Box A's left edge (B.maxX < A.minX)
3. Box A's bottom edge is above Box B's top edge (A.maxY < B.minY) - assuming Y increases upwards
4. Box B's bottom edge is above Box A's top edge (B.maxY < A.minY) - assuming Y increases upwards

If any of these conditions are true, the boxes do not overlap. Therefore, if none of these conditions are true, the boxes must overlap.

The Overlapping Condition (Direct Check)

Conversely, we can directly check for overlap. Two boxes overlap if and only if their X-intervals overlap AND their Y-intervals overlap. This means:

1. Box A's left edge is to the left of Box B's right edge (A.minX < B.maxX)
2. Box A's right edge is to the right of Box B's left edge (A.maxX > B.minX)
3. Box A's bottom edge is below Box B's top edge (A.minY < B.maxY)
4. Box A's top edge is above Box B's bottom edge (A.maxY > B.minY)

All four of these conditions must be true for an overlap to occur. This is often more straightforward to implement than negating the non-overlap conditions.

flowchart TD
    start[Start]
    start --> checkXOverlap{Is A.minX < B.maxX AND A.maxX > B.minX?}
    checkXOverlap -- No --> noOverlap[No Overlap]
    checkXOverlap -- Yes --> checkYOverlap{Is A.minY < B.maxY AND A.maxY > B.minY?}
    checkYOverlap -- No --> noOverlap
    checkYOverlap -- Yes --> overlap[Overlap Detected]
    noOverlap --> end[End]
    overlap --> end

Decision flow for checking 2D AABB overlap using the direct overlap conditions.

Implementation Details and Code Examples

Let's define a simple Box structure or class that holds the necessary coordinates. We'll use minX, minY, maxX, maxY for clarity. If you have x, y, width, height, you can derive these: minX = x, minY = y, maxX = x + width, maxY = y + height.

JavaScript

class Box { constructor(minX, minY, maxX, maxY) { this.minX = minX; this.minY = minY; this.maxX = maxX; this.maxY = maxY; } }

function checkOverlap(boxA, boxB) { // Check if there is no overlap if (boxA.maxX < boxB.minX || // A is to the left of B boxA.minX > boxB.maxX || // A is to the right of B boxA.maxY < boxB.minY || // A is below B (assuming Y increases upwards) boxA.minY > boxB.maxY) { // A is above B (assuming Y increases upwards) return false; // No overlap } return true; // Overlap }

// Example Usage: const box1 = new Box(0, 0, 10, 10); // x:0-10, y:0-10 const box2 = new Box(5, 5, 15, 15); // x:5-15, y:5-15 (overlaps) const box3 = new Box(11, 11, 20, 20); // x:11-20, y:11-20 (no overlap)

console.log('Box1 and Box2 overlap:', checkOverlap(box1, box2)); // true console.log('Box1 and Box3 overlap:', checkOverlap(box1, box3)); // false console.log('Box2 and Box3 overlap:', checkOverlap(box2, box3)); // false

Python

class Box: def init(self, min_x, min_y, max_x, max_y): self.min_x = min_x self.min_y = min_y self.max_x = max_x self.max_y = max_y

def check_overlap(box_a, box_b): # Check if there is no overlap if (box_a.max_x < box_b.min_x or # A is to the left of B box_a.min_x > box_b.max_x or # A is to the right of B box_a.max_y < box_b.min_y or # A is below B (assuming Y increases upwards) box_a.min_y > box_b.max_y): # A is above B (assuming Y increases upwards) return False # No overlap return True # Overlap

Example Usage:

box1 = Box(0, 0, 10, 10) # x:0-10, y:0-10 box2 = Box(5, 5, 15, 15) # x:5-15, y:5-15 (overlaps) box3 = Box(11, 11, 20, 20) # x:11-20, y:11-20 (no overlap)

print(f'Box1 and Box2 overlap: {check_overlap(box1, box2)}') # True print(f'Box1 and Box3 overlap: {check_overlap(box1, box3)}') # False print(f'Box2 and Box3 overlap: {check_overlap(box2, box3)}') # False

C#

public class Box { public float MinX { get; set; } public float MinY { get; set; } public float MaxX { get; set; } public float MaxY { get; set; }

public Box(float minX, float minY, float maxX, float maxY)
{
    MinX = minX;
    MinY = minY;
    MaxX = maxX;
    MaxY = maxY;
}

}

public class OverlapChecker { public static bool CheckOverlap(Box boxA, Box boxB) { // Check if there is no overlap if (boxA.MaxX < boxB.MinX || // A is to the left of B boxA.MinX > boxB.MaxX || // A is to the right of B boxA.MaxY < boxB.MinY || // A is below B (assuming Y increases upwards) boxA.MinY > boxB.MaxY) // A is above B (assuming Y increases upwards) { return false; // No overlap } return true; // Overlap }

public static void Main(string[] args)
{
    Box box1 = new Box(0, 0, 10, 10); // x:0-10, y:0-10
    Box box2 = new Box(5, 5, 15, 15); // x:5-15, y:5-15 (overlaps)
    Box box3 = new Box(11, 11, 20, 20); // x:11-20, y:11-20 (no overlap)

    System.Console.WriteLine($"Box1 and Box2 overlap: {CheckOverlap(box1, box2)}"); // True
    System.Console.WriteLine($"Box1 and Box3 overlap: {CheckOverlap(box1, box3)}"); // False
    System.Console.WriteLine($"Box2 and Box3 overlap: {CheckOverlap(box2, box3)}"); // False
}

}