Intersection over Union (IoU)

You want to compute how much two axis-aligned rectangles overlap, expressed as a ratio between 0 and 1 called Intersection over Union (IoU). This is a pure geometry / implementation exercise with constant-time operations.

---

1. Background Knowledge

In object detection, a model predicts bounding boxes for objects in an image, and these predictions are compared against ground-truth boxes. The most common accuracy metric is Intersection over Union (IoU), which measures how much the predicted box overlaps with the ground-truth box relative to their total combined area.

Each bounding box is typically represented as $[x_1, y_1, x_2, y_2]$, where:

• $(x_1, y_1)$ is the top-left corner,
• $(x_2, y_2)$ is the bottom-right corner,
• and the box is axis-aligned (its edges are parallel to the image axes).

The IoU between two boxes $A$ and $B$ is:

$$IoU = \frac{Area_{intersection}}{Area_{union}} = \frac{Area_{intersection}}{Area_A + Area_B - Area_{intersection}}$$

If boxes do not overlap, $Area_{intersection} = 0$ and so $IoU = 0$. If they match exactly, intersection = union and $IoU = 1$.

---

2. Algorithm / Approach

The key pattern is:

1. Treat overlap in x and y dimensions independently.
2. Compute a 1D overlap length along x and along y using max/min.
3. Multiply these to get the intersection area (or 0 if no overlap).
4. Compute each box’s area.
5. Compute union using the inclusion–exclusion formula.
6. Return intersection / union.

This is a standard geometry / interval-overlap problem in 2D, framed as two 1D overlaps (x and y).

---

3. Step-by-Step Strategy

1. Unpack coordinates For box A: $(x1_A, y1_A, x2_A, y2_A)$ For box B: $(x1_B, y1_B, x2_B, y2_B)$

2. Compute intersection rectangle coordinates

• $x1_{inter} = \max(x1_A, x1_B)$
• $y1_{inter} = \max(y1_A, y1_B)$
• $x2_{inter} = \min(x2_A, x2_B)$
• $y2_{inter} = \min(y2_A, y2_B)$

3. Compute intersection width and height

inter_w = x2_inter - x1_inter
inter_h = y2_inter - y1_inter

• If inter_w <= 0 or inter_h <= 0, then no overlap: intersection area = 0.

4. Intersection area

inter_area = max(inter_w, 0) * max(inter_h, 0)

5. Individual box areas

area_A = max(x2_A - x1_A, 0) * max(y2_A - y1_A, 0)
area_B = max(x2_B - x1_B, 0) * max(y2_B - y1_B, 0)

6. Union area

union_area = area_A + area_B - inter_area

7. Compute IoU

• If union_area == 0 (degenerate boxes), define IoU as 0 (or handle specially).

iou = inter_area / union_area if union_area > 0 else 0.0

---

4. Common Pitfalls

• Not checking for non-overlap: Directly multiplying negative inter_w or inter_h gives a negative “area.” Always clamp with max(..., 0) or explicitly check with if inter_w <= 0 or inter_h <= 0.

• Coordinate convention confusion: The problem states that $(x_1, y_1)$ is top-left and $(x_2, y_2)$ is bottom-right. Make sure you do not assume center-width-height form or bottom-left origin.

• Degenerate boxes: When $x_1 = x_2$ or $y_1 = y_2$, area is zero. Decide what IoU should be if both boxes have zero area and overlap at a point; for coding problems, usually return 0 to avoid division by zero.

• Integer division: In some languages, dividing integers yields integer results. Cast to float to avoid IoU being truncated to 0 or 1.

• Wrong formula for union: Union is not simply area_A + area_B. You must subtract the intersection once: union = area_A + area_B - intersection.

---

5. Time & Space Complexity

• Time complexity: All operations are constant-time arithmetic; no loops or recursion. O(1).

• Space complexity: Only a fixed number of variables are used. O(1) extra space.

This is essentially a small, careful implementation of interval intersection plus an area calculation.