Given the topleft and bottomright 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.
You get coordinates for the rectangles as tuples of x and y, e.g. [2,5] .
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) .
View post:
Finding if two rectangles overlap in JavaScript
