Research and Application of Rectangle Overlap Detection Algorithm Based on Separating Axis Theorem

Introduction and Problem Background

In computer graphics, game development, and user interface design, rectangle overlap detection is a fundamental and important problem. When we need to determine whether two axis-aligned rectangles have overlapping regions in 2D space, efficient detection algorithms become particularly crucial. This paper proposes a concise and efficient rectangle overlap detection method based on the separating axis theorem.

Algorithm Principle Analysis

The separating axis theorem states: for two convex polygons, if there exists a line (separating axis) that can completely separate the two polygons, then the polygons do not intersect. For axis-aligned rectangles, we only need to check four possible separating axes: the lines containing the four edges of the two rectangles.

Specifically, the condition for two rectangles not overlapping can be expressed as one of the following four cases:

• Rectangle A is completely to the right of rectangle B
• Rectangle A is completely to the left of rectangle B
• Rectangle A is completely above rectangle B
• Rectangle A is completely below rectangle B

According to De Morgan's laws, we can transform the overlap condition into:

NOT (A is right of B OR A is left of B OR A is above B OR A is below B)

Equivalent to:

A is not right of B AND A is not left of B AND A is not above B AND A is not below B

Coordinate System and Boundary Definition

In the standard Cartesian coordinate system, we typically define rectangles as follows:

• Left boundary (Left/X1): The leftmost x-coordinate of the rectangle
• Right boundary (Right/X2): The rightmost x-coordinate of the rectangle
• Top boundary (Top/Y1): The topmost y-coordinate of the rectangle
• Bottom boundary (Bottom/Y2): The bottommost y-coordinate of the rectangle

It's important to note that different systems may use different coordinate directions. In most computer graphics systems, the y-axis typically increases from top to bottom, which is opposite to the standard mathematical coordinate system. When implementing the algorithm, comparison conditions need to be adjusted according to the actual coordinate system.

Core Algorithm Implementation

Based on the above analysis, we can derive the core logic for rectangle overlap detection. Here is a complete C++ implementation:

#include <iostream>
#include <vector>

struct Rectangle {
    double left, right, top, bottom;
    
    Rectangle(double l, double r, double t, double b) 
        : left(l), right(r), top(t), bottom(b) {}
};

bool checkOverlap(const Rectangle& rectA, const Rectangle& rectB) {
    // Check horizontal overlap
    bool overlapX = (rectA.left < rectB.right) && (rectA.right > rectB.left);
    
    // Check vertical overlap
    bool overlapY = (rectA.top > rectB.bottom) && (rectA.bottom < rectB.top);
    
    // Rectangles overlap if both directions overlap
    return overlapX && overlapY;
}

// Implementation for standard mathematical coordinate system
bool checkOverlapMath(const Rectangle& rectA, const Rectangle& rectB) {
    // In standard mathematical coordinates, y-axis increases from bottom to top
    bool overlapX = (rectA.left < rectB.right) && (rectA.right > rectB.left);
    bool overlapY = (rectA.bottom < rectB.top) && (rectA.top > rectB.bottom);
    
    return overlapX && overlapY;
}

int main() {
    // Test cases
    Rectangle rect1(0, 10, 10, 0);  // Top-left(0,10), Bottom-right(10,0)
    Rectangle rect2(5, 15, 5, 0);   // Top-left(5,5), Bottom-right(15,0)
    
    if (checkOverlap(rect1, rect2)) {
        std::cout << "Rectangles overlap" << std::endl;
    } else {
        std::cout << "Rectangles do not overlap" << std::endl;
    }
    
    return 0;
}

Algorithm Complexity and Performance Analysis

The time complexity of this algorithm is O(1), as it only requires a fixed number of comparison operations. The space complexity is also O(1), requiring only storage for the rectangle boundary coordinates. This makes the algorithm particularly suitable for real-time systems, such as game engines and interactive applications.

Boundary Case Handling

In practical applications, we may need to consider some special boundary cases:

// Handle boundary inclusion cases
bool checkOverlapInclusive(const Rectangle& rectA, const Rectangle& rectB) {
    // Use <= and >= to include boundary contact cases
    bool overlapX = (rectA.left <= rectB.right) && (rectA.right >= rectB.left);
    bool overlapY = (rectA.top >= rectB.bottom) && (rectA.bottom <= rectB.top);
    
    return overlapX && overlapY;
}

// Handle complete containment cases
bool isContained(const Rectangle& container, const Rectangle& contained) {
    return (contained.left >= container.left) &&
           (contained.right <= container.right) &&
           (contained.top <= container.top) &&
           (contained.bottom >= container.bottom);
}

Practical Application Scenarios

Rectangle overlap detection has wide applications in numerous fields:

• Game Development: Collision detection, click detection
• User Interface: Window management, control layout
• Computer Vision: Object detection, region extraction
• Geographic Information Systems: Regional queries, spatial indexing

Extensions and Optimizations

For more complex scenarios, we can consider the following extensions:

// Multiple rectangle overlap detection
bool checkMultipleOverlap(const std::vector<Rectangle>& rectangles) {
    for (size_t i = 0; i < rectangles.size(); ++i) {
        for (size_t j = i + 1; j < rectangles.size(); ++j) {
            if (checkOverlap(rectangles[i], rectangles[j])) {
                return true;
            }
        }
    }
    return false;
}

// Compute overlap area
Rectangle computeOverlapArea(const Rectangle& rectA, const Rectangle& rectB) {
    if (!checkOverlap(rectA, rectB)) {
        return Rectangle(0, 0, 0, 0); // No overlap
    }
    
    double overlapLeft = std::max(rectA.left, rectB.left);
    double overlapRight = std::min(rectA.right, rectB.right);
    double overlapTop = std::min(rectA.top, rectB.top);
    double overlapBottom = std::max(rectA.bottom, rectB.bottom);
    
    return Rectangle(overlapLeft, overlapRight, overlapTop, overlapBottom);
}

Conclusion

This paper provides a detailed introduction to the rectangle overlap detection algorithm based on the separating axis theorem. Through rigorous mathematical derivation and complete code implementation, it demonstrates the efficiency and practicality of this algorithm. The algorithm not only has low time complexity but is also easy to understand and implement, making it a classic method for solving 2D spatial geometry problems. In practical applications, developers need to make appropriate adjustments and extensions based on specific coordinate systems and business requirements.