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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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