Introduction

The right rectangle-overlap algorithm depends on how many rectangles you have. For two axis-aligned rectangles, a few comparisons are enough. For many rectangles, you usually move to a sweep-line or spatial-index approach so you do not compare every pair blindly.

The Fast Test for Two Rectangles

Assume two axis-aligned rectangles, each represented by left, bottom, right, and top edges. They overlap in area if and only if they overlap on both the x-axis and the y-axis.

In other words, rectangles a and b overlap when:

• 'a.left < b.right and a.right > b.left'
• 'a.bottom < b.top and a.top > b.bottom'

That gives an O(1) test for one pair.

1from dataclasses import dataclass
2
3@dataclass
4class Rect:
5    left: float
6    bottom: float
7    right: float
8    top: float
9
10
11def overlaps(a: Rect, b: Rect) -> bool:
12    return (
13        a.left < b.right and
14        a.right > b.left and
15        a.bottom < b.top and
16        a.top > b.bottom
17    )
18
19
20r1 = Rect(0, 0, 4, 4)
21r2 = Rect(2, 1, 5, 3)
22print(overlaps(r1, r2))  # True

This is the standard axis-aligned bounding box, or AABB, overlap test. It is simple and extremely fast.

If You Need the Overlapping Area

Sometimes you do not only need to know whether an overlap exists. You also want the overlap rectangle or its area.

1def overlap_area(a: Rect, b: Rect) -> float:
2    width = max(0.0, min(a.right, b.right) - max(a.left, b.left))
3    height = max(0.0, min(a.top, b.top) - max(a.bottom, b.bottom))
4    return width * height
5
6
7print(overlap_area(r1, r2))  # 4.0

Clamping with max(0.0, ...) is important. Without it, non-overlapping rectangles can produce negative widths or heights.

What Changes When You Have Many Rectangles

If you have n rectangles and compare every pair, the obvious algorithm takes O(n^2) time. That is fine for small inputs and often too slow for large scenes or geometry workloads.

For many rectangles, a common improvement is the sweep-line algorithm:

1. sort rectangle start and end events by x-coordinate
2. sweep from left to right
3. maintain an active set of rectangles whose x-range currently intersects the sweep line
4. within the active set, detect y-overlaps efficiently

The sweep-line idea reduces unnecessary comparisons because rectangles that are far apart on the x-axis never need a full overlap check.

A Sweep-Line Mental Model

Imagine a vertical line moving left to right across the plane. When the line reaches a rectangle's left edge, that rectangle becomes active. When the line passes the right edge, it becomes inactive.

At each step, you only compare the newly active rectangle against rectangles already active, because only those can currently overlap it.

In a fully optimized version, the active set is maintained with an interval tree or balanced structure keyed by y-range. That gives much better scaling than brute force for large datasets.

Spatial Indexing Is Another Practical Option

In many real systems, especially games and GIS pipelines, the best answer is not a pure sweep line. It may be a spatial index such as:

• uniform grid
• quadtree
• R-tree

These structures narrow the candidate rectangles before you run the exact AABB overlap test. The final exact test is still simple; the index just reduces how many pairs reach that test.

Which Algorithm Should You Use

A practical rule of thumb is:

• two rectangles: direct AABB comparisons
• a few hundred rectangles: brute force may still be acceptable
• many rectangles or repeated queries: sweep line or spatial indexing

Efficiency is not only about asymptotic complexity. It is also about how often the query runs and how the data is distributed.

Common Pitfalls

The biggest mistake is not defining whether touching edges count as overlap. If a.right == b.left, some applications call that overlap and others do not. Your comparison operators must match the definition you actually need.

Another mistake is using an O(n^2) all-pairs scan for very large rectangle sets when the workload clearly needs a sweep-line or spatial-index approach.

People also forget that the simple AABB formulas assume axis-aligned rectangles. Once rectangles can rotate, the overlap test becomes more complicated.

Finally, if you need the overlap area, do not reuse a boolean-only overlap test and guess the geometry afterward. Compute the intersection width and height explicitly.

Summary

• For one pair of axis-aligned rectangles, overlap detection is an O(1) comparison problem.
• Compute overlap area with clamped intersection width and height.
• For many rectangles, brute force becomes O(n^2) and often too slow.
• Sweep-line and spatial-index methods reduce unnecessary comparisons.
• Be explicit about whether edge-touching counts as overlap in your problem definition.