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

Ответ 1

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

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

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

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

Поддерживать текущее частичное пересечение D в сбалансированном двоичном дереве в порядке CCW.

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

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

Ответ 2

Аннотация

Используйте либо алгоритм сортировки в соответствии с наименьшим значением 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-tree) являются одним из лучших способов хранения геопространственных данных и могут быть полезны в Эта проблема. Просто сохраните свои прямоугольники в R-дереве, и вы можете определить пересечения с простой сложностью O(n log n). (n поиск, log n время для каждого).

Ответ 3

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

Ответ 4

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

Ответ 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.

Ответ 6

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