Задача строится поверх двух одномерных поисков наложения диапазонов.
Исходный массив мало полезен, надо привести к массивам только-координат, по два X и по два Y на прямоугольник. Пусть они всегда будут по возрастанию, X начала всегда меньше X конца прямоугольника.
На примере X. Два прямоугольника дали следующие иксы: [3,7], [5,9]
. Эти значения надо как-то слить в один массив и отсортировать по возрастанию координаты, при этом сохранив их назначение – кто начало, а кто конец какого-то прямоугольника. Можно их привести к объектам типа:
[
{ x:3, io: 1, rect_id: 0 },
{ x:7, io:-1, rect_id: 0 },
{ x:5, io: 1, rect_id: 1 },
{ x:9, io:-1, rect_id: 1 },
]
и отсортировать по свойству x
.
Далее останется двигаться от меньшего к большему и считать текущую сумму io
. Пока нет пересечений, будет 0
или 1
. Как только начнется пересечение, появится значение >1
. Это означает, что проекция прямоугольника, которому принадлежит текущая точка, на ось X накладывается с проекцией прямоугольника, которому принадлежит точка предыдущая.
Так найдутся пары (или компании побольше) кандидатов на пересечения по осям X и Y. И останется найти общие среди них.