Алгоритм определения пересечения прямоугольников

#алгоритм

Исходные данные: прямоугольники, заданные в виде массива элементов из x, y, w, h.
Требуется определить, есть ли пересечения хотя бы двух прямоугольников.

Текущая реализация - в лоб, циклом проходим все прямоугольники кроме последнего,
и для каждого вложенным циклом проверяем пересечение с последующими. При первом пересечении
оба цикла прерываются.

Есть ли более эффективный способ? 

Касательно моего случая кол-во прямоугольников: >10000, среда выполнения: javascript
в браузере.
    

Ответы

Ответ 1

Задача строится поверх двух одномерных поисков наложения диапазонов.

Исходный массив мало полезен, надо привести к массивам только-координат, по два 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.
И останется найти общие среди них.