Finding if two rectangles overlap in JavaScript
Given the top-left and bottom-right coordinates of two rectangles, determine if they overlap or not. That is, determine if any part of one rectangle overlaps with any part of the other.
The grid has position (0, 0) at the top left. X increases rightwards and Y
increases downwards. This is common in 2D grids in video games.
0,0 ─ x → │ y ↓
You get coordinates for the rectangles as tuples of x and y, e.g. (2, 5).
Some diagrams to visualise (not to scale):
tl1(1,1)
┌─────────────┐
│ │
│ tl2(2,2) │
│ ┌─────────┼────────┐
│ │ │ │
└───┼─────────┘ │
│ br1(3,3) │
│ │
└──────────────────┘
br2(4,4)
tl1(5,1)
┌─────────────┐
│ │
tl2(2,2) │ │
┌──────────────────┐ │ │
│ │ └─────────────┘
│ │ br1(7,3)
│ │
│ │
└──────────────────┘
br2(4,4)
tl1(1,1)
┌─────────────┐
│ │
│ │ tl2(6,2)
│ │ ┌──────────────────┐
│ │ │ │
└─────────────┘ │ │
br1(3,3) │ │
│ │
└──────────────────┘
br2(8,4)
The function signature in TypeScript would be:
type point = [number, number];
type rectanglesOverlap = (
topLeft1: point,
bottomRight1: point,
topLeft2: point,
bottomRight2: point
) => boolean
Brute force method
There is a direct brute force method to solving this. You iterate on one rectangle gathering all the points, then iterate on the other, returning true if any point also exists in the other.
function* iteratePoints(topLeft, bottomRight) {
for (let x = topLeft[0]; x <= bottomRight[0]; x++) {
for (let y = topLeft[1]; y <= bottomRight[1]; y++) {
yield [x, y];
}
}
}
function rectanglesOverlap(topLeft1, bottomRight1, topLeft2, bottomRight2) {
const rectangle1Points = {};
for (let point1 of iteratePoints(topLeft1, bottomRight1)) {
rectangle1Points[`${point1[0]},${point1[1]}`] = true;
}
for (let point2 of iteratePoints(topLeft2, bottomRight2)) {
if (rectangle1Points[`${point2[0]},${point2[1]}`] === true) {
return true;
}
}
return false;
}
This works but is O(mn) with m and n being the number of points in each
rectangle.
Negative edge check method
There is a simpler and faster method to determine if two rectangles overlap. The key idea is to check if they don’t overlap, which is easier. If they don’t not overlap, then they overlap.
The rectangles don’t overlap if any of these are true:
- One left edge is to the right of the other right edge.
- One top edge is below the other bottom edge.
function rectanglesOverlap(topLeft1, bottomRight1, topLeft2, bottomRight2) {
if (topLeft1[0] > bottomRight2[0] || topLeft2[0] > bottomRight1[0]) {
return false;
}
if (topLeft1[1] > bottomRight2[1] || topLeft2[1] > bottomRight1[1]) {
return false;
}
return true;
}
This is now O(1).
By the way, you can hire me as a freelance JavaScript developer for your project.