Пересечение N прямоугольников

Question

Я ищу алгоритм для решения этой проблемы:

Учитывая N прямоугольников на декартовой координате, выясните, является ли пересечение этих прямоугольников пустым или нет. Каждый прямоугольник может лежать в любом направлении (не обязательно, чтобы его края были параллельны Ox и Oy)

Есть ли у вас какие-либо предложения по решению этой проблемы? :) Я могу подумать о тестировании пересечения каждой пары прямоугольников. Тем не менее, это O (N * N) и довольно медленно: (

Answer 1

Аннотация

Либо используйте алгоритм сортировки по наименьшему значению 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-Trees

R-деревья (пространственное обобщение B-деревьев ) являются одним из лучших способов хранения геопространственных данных и могут быть полезны в этой задаче. Просто сохраните ваши прямоугольники в R-дереве, и вы сможете находить пересечения с простой O(n log n) сложностью. (n поисков, log n время для каждого).

Answer 2

Наблюдение 1: с учетом многоугольника A и прямоугольника B пересечение A ∩ B можно вычислить путем 4 пересечений с полуплоскостями, соответствующими каждому ребру B.

Замечание 2: разрезание полуплоскостииз выпуклого многоугольника дает вам выпуклый многоугольник.Первый прямоугольник представляет собой выпуклый многоугольник.Эта операция увеличивает число вершин не более чем на 1.

Замечание 3: расстояние со знаком вершин выпуклого многоугольника до прямой является унимодальной функцией.

Вот эскизалгоритма:

Сохранение текущего частичного пересечения D в сбалансированном двоичном дереве в порядке CCW.

При вырезании полуплоскости, определяемой линией L, найдите два ребра в Dэто пересекается с L. Это можно сделать в логарифмическом времени с помощью некоторого умного двоичного или троичного поиска, использующего унимодальность расстояния со знаком до L. (Это часть, которую я точно не помню.) Удалите все вершины с одной стороныL из D и вставьте точки пересечения в D.

Повторите для всех ребер L всех прямоугольников.

Answer 3

Это похоже на хорошее применение меры Клее. По сути, если вы прочитаете http://en.wikipedia.org/wiki/Klee%27s_measure_problem, то во время выполнения лучших алгоритмов будут установлены нижние границы для прямолинейных пересечений в точке O (n log n).

Answer 4

Я думаю, вы должны использовать что-то вроде алгоритма линии развертки : поиск пересечений является одним из его применений.Также посмотрите на ответы на эти вопросы

Answer 5

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

• построить набор S, который содержит все границы вместе с прямоугольником, к которому они принадлежат;вы получаете набор кортежей в форме ((x_start, y_start), (x_end, y_end), r_n), где r_n - это, конечно, идентификатор соответствующего прямоугольника
• , теперь используйте алгоритм строчной линии, чтобы найтипересечения этих линий

Линия развертки останавливается на каждой x-координате в S, то есть на всех начальных значениях и всех конечных значениях.Для каждой новой начальной координаты поместите соответствующую строку во временный набор I. Для каждой новой конечной координаты удалите соответствующую строку из I.

Помимо добавления новых строк в I, вы можете проверить каждую новуюлиния, пересекает ли она одну из линий, находящихся в настоящее время в I. Если они это делают, соответствующие прямоугольники тоже.

Подробное объяснение этого алгоритма можно найти здесь .

Время выполнения: O (n * log (n) + c * log (n)), где c - количество точек пересечения линий в I.

Answer 6

Выберите наименьший прямоугольник из набора (или любой прямоугольник) и обведите каждую точку в нем.Если одна из его точек также существует во всех других прямоугольниках, пересечение не является пустым.Если все точки свободны от ALL других прямоугольников, пересечение будет пустым.