6

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

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

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

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

7
  • нужно ли определить, какие именно прямоугольники пересеклись, или достаточно проверки наличия / отсутствия пересечения?
    – Sergiks
    6 авг 2016 в 6:23
  • @Sergiks только факт наличия пересечения хотя бы двух 6 авг 2016 в 6:35
  • еще определитесь с краевым условием: если у двух прямоугольников только одна общая угловая точка – они пересекаются?
    – Sergiks
    6 авг 2016 в 7:14
  • @Sergiks пересекаются, или может я упустил что-то, в каких ситуациях их можно принимать как не пересекающиеся? 6 авг 2016 в 7:19
  • 1
    related: Collision detection (part 2): Box intersection
    – jfs
    6 авг 2016 в 13:38

1 ответ 1

6

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

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

1
  • 1
    Уточняю. По сути это метод вертикальной декомпозиции, но только его начальные шаги. Дальше надо бы использовать какое-нибудь дерево или ещё раз сортировку чтобы быстро проверять пересечения в группах. Но этот метод обычно решает значительно более сложную задачу - поиск общей площади. Для исходной задачи можно использовать алгоритм заметающей прямой e-maxx.ru/algo/intersecting_segments при этом, т.к. все линии параллельны осям, алгоритм можно СУЩЕСТВЕННО упростить. А можно не упрощать, а просто скопировать реализацию. Сложности n log n должно хватить, хотя можно до n дожать вроде бы.
    – pavel
    6 авг 2016 в 7:31

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.