Я ищу алгоритм для решения этой проблемы:
Учитывая N прямоугольников в декартовой координате, выясните, является ли пересечение этих прямоугольников пустым или нет. Каждый прямоугольник может лежать в любом направлении (не обязательно иметь ребра, параллельные Ox и Oy)
Есть ли у вас предложение решить эту проблему?:) Я могу подумать о проверке пересечения каждой пары прямоугольников. Однако он O (N * N) и довольно медленный: (
Наблюдение 1: если задан многоугольник A и прямоугольник B, пересечение A ∩ B может быть вычислено 4 пересечением с полуплоскостями, соответствующими каждому ребру B.
Наблюдение 2: разрезание полуплоскости из выпуклого многоугольника дает вам выпуклый многоугольник. Первый прямоугольник является выпуклым многоугольником. Эта операция увеличивает количество вершин не более чем на 1.
Наблюдение 3: знаковое расстояние вершин выпуклого многоугольника до прямой является унимодальной функцией.
Вот эскиз алгоритма:
Поддерживать текущее частичное пересечение D в сбалансированном двоичном дереве в порядке CCW.
При разрезании полуплоскости, определенной линией L, найдите два ребра в D, которые пересекают L. Это можно сделать в логарифмическом времени через некоторый умный двоичный или тройственный поиск, использующий унимодальность знакового расстояния до L. ( Это та часть, которую я точно не помню.) Удалите все вершины с одной стороны L из D и вставьте точки пересечения в D.
Повторите для всех ребер L всех прямоугольников.
Используйте либо алгоритм сортировки в соответствии с наименьшим значением X прямоугольника, либо сохраните ваши прямоугольники в R-дереве и выполните поиск.
Обозначим low_x() - наименьшее (слева) значение X прямоугольника, а high_x() - наивысшее (самое правое) значение X прямоугольника.
Алгоритм:
Sort the rectangles according to low_x(). # O(n log n)
For each rectangle in sorted array: # O(n)
Finds its highest X point. # O(1)
Compare it with all rectangles whose low_x() is smaller # O(log n)
than this.high(x)
Это должно работать на O(n log n) на равномерно распределенных прямоугольниках.
В худшем случае будет O(n^2), например, если прямоугольники не пересекаются, а одно над другим. В этом случае обобщите алгоритм на low_y() и high_y() тоже.
R-деревья (пространственное обобщение B-tree) являются одним из лучших способов хранения геопространственных данных и могут быть полезны в Эта проблема. Просто сохраните свои прямоугольники в R-дереве, и вы можете определить пересечения с простой сложностью O(n log n). (n поиск, log n время для каждого).
Это похоже на хорошее применение меры Клее. В принципе, если вы читаете http://en.wikipedia.org/wiki/Klee%27s_measure_problem, то на время выполнения лучших алгоритмов, которые могут быть найдены для прямолинейных пересечений в O (n log п).
Я думаю, вы должны использовать что-то вроде алгоритм развертки строк: поиск пересечений является одним из его приложений. Кроме того, посмотрите на ответы на эти вопросы
Поскольку прямоугольники не должны быть параллельны оси, легче преобразовать проблему в уже разрешенный: вычислить пересечения границ прямоугольников.
Линия развертки останавливается при каждой x-координате в S, то есть все начальные значения и все конечные значения. Для каждой новой начальной координаты поместите соответствующую строку во временное множество I. Для каждой новой конечной координаты удалите соответствующую строку из I.
Кроме добавления новых строк в I, вы можете проверить каждую новую строку, пересекается ли она с одной из строк, находящихся в настоящее время в I. Если они это сделают, соответствующие прямоугольники тоже.
Вы можете найти подробное объяснение этого алгоритма здесь.
Время выполнения: O (n * log (n) + c * log (n)), где c - число точек пересечения прямых в I.
Выберите наименьший прямоугольник из набора (или любого прямоугольника) и перейдите через каждую точку внутри него. Если один из них указывает также и во всех других прямоугольниках, пересечение не пусто. Если все точки свободны от ВСЕХ других прямоугольников, пересечение пусто.