Учитывая множество горизонтальных и вертикальных линий, как найти все прямоугольники, которые имеют какой-либо суб-прямоугольник внутри них?

Question

У меня есть много горизонтальных и вертикальных линий, которые составляют прямоугольник, такой как в этом примере.

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

Прямоугольники, которые я ищу, должны быть пустыми. У меня есть список начальных и конечных точек каждой строки, например (a, b) - (c, d). Я хочу в результате получить список прямоугольников (x, y, w, h) или эквивалент.

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

Answer 1

Все ли ваши линии параллельны оси x или y? Или все ваши линии параллельны или перпендикулярны?

Из примера, который вы дали, я предполагаю, что все ваши линии параллельны оси x или y. В этом случае ваши строки будут [(a, b), (a, d)] или [(a, b), (c, b)].

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

Вторая задача - обнаружить прямоугольники. Для каждой пары углов вы можете проверить, образуют ли они прямоугольники.

Третья задача - найти, имеет ли прямоугольник какие-либо прямоугольники внутри себя.

Для первой задачи вам необходимо разделить строки на два набора: вертикальные и горизонтальные. После этого сортировки один из наборов. Ex. Сортируйте вертикальные линии в соответствии с их координатами оси x. Затем вы можете взять все горизонтальные линии и выполнить двоичный поиск, чтобы найти все пересекающиеся точки.

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

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

Answer 2

Я думаю, что другое представление поможет вам решить вашу проблему. В качестве примера рассмотрим большой прямоугольник (без блока на конце). Существует четыре уникальные координаты x и y, сортировка и индексирование. Графически это будет выглядеть следующим образом:

Если угол прямоугольника на координатной (x_i, y_j) положить его в матрицу следующим образом:

__|_1__2__3__4_ 
1 | x x 0 x 
2 | x x 0 0 
3 | 0 x x x 
4 | x x x x 

Теперь по определению, прямоугольник в вещественное пространство - это прямоугольник на координатах матрицы. Например, есть прямоугольник в (3,2) (3,4) (4,4), (4,3), но он не является «базовым» прямоугольником, так как он содержит под прямоугольник (3,3) (3,4), (4,4), (4,3). Рекурсивный алгоритм легко увидеть здесь, и для добавления скорости используйте memoization для предотвращения повторных вычислений.

Answer 3

A sweep-line algorithm ...

структуры, необходимые:

• V = Набор вертикальных линий, сортируется по й-координатам.

• H = набор всех начальных и конечных точек горизонтальных линий (и каждая точка содержит ссылку на линию) и отсортирована по координате x.

• CH = An (первоначально пустой) отсортированный (по y-координате) набор текущий горизонтальные линии.

• CR = A отсортировано (по координате y) текущий прямоугольники. Эти прямоугольники будут иметь левую, верхнюю и нижнюю координаты, но еще не правильную координату. Обратите внимание, что в этом наборе не будет перекрытия.

Алгоритм:

Одновременно процесс V и Н слева направо.

Когда начинается старт горизонтальной линии, добавьте строку в CH.

Всякий раз, когда встречается конец горизонтальной линии, удалите это из CH.

Всякий раз, когда вертикальная линия встречается:

• Удалить из CR все прямоугольники, которые перекрываются с линией. Для всех удаленных прямоугольников, если они полностью содержатся в строке, сравните его размер с лучшим прямоугольником до сих пор и сохраните его, если лучше.

• Процесса каждый элемент в СНЕ итеративно между нижней точкой и верхней точкой линии следующим образом:

  • Добавить прямоугольник CR с последней обрабатываемой точкой, как дно, текущей точкой в ​​качестве верхних и координата y вертикальной линии как левая.

Done.

Примечание:

Когда координата х горизонтальных начальных точек или конечных точек или вертикальных линий равны следующий порядок должен поддерживаться:

x of horizontal start < x of vertical line < x of horizontal finish 

В противном случае вы пропустите прямоугольники.

Answer 4

На эти вопросы в значительной степени отвечают некоторые стандартные алгоритмы Computational Geometry. Я могу придумать алгоритм vertical sweep line для этой конкретной проблемы.

Предполагая, что прямоугольник представлен парой точек (p1, p2), где p1 - верхний левый угол, а p2 - нижний правый угол. А точка имеет два атрибута (к ним можно обращаться как p.x и p.y).

Вот алгоритм.

1. Сортировать все пары точек - O(n log n)
2. Инициализировать список под названием sweep line status. Это будет содержать все прямоугольники, которые встречаются до сих пор, это alive. Также инициализируйте другой список под названием event queue, который содержит предстоящие события. Это event queue в настоящее время содержит стартовые точки всех реккалов.
3. Обработать события, начиная с первого элемента в event queue.
   • Если событие является start point, затем добавить этот прямоугольник sweep line status (в отсортированном порядке у-координата) (в O(log n) времени) и добавить его правый нижний пункт в event queue в соответствующем положении (отсортированный по точкам) (снова в O(log n) раз). Когда вы добавляете его в sweep line status, вам просто нужно проверить, находится ли этот пункт в прямоугольнике, который находится прямо над ним в sweep line status. Если он лежит внутри, это не ваш прямоугольник, иначе добавьте его в список требуемых прямоугольников.
   • Если событие является конечной точкой, просто удалите прямоугольник корреляции с sweep line status.

время (для п прямоугольников) Запуск:

• Сортировка занимает O(n log n).
• Количество событий = 2 * п = O(n)
• Каждое событие занимает O(log n) время (для вставки в event queue, а также sweep line status. Таким образом, общая сумма O(n log n).

Поэтому O(n log n).

Для более подробную информацию см. в Bentley–Ottmann algorithm.Это просто простая модификация.

EDIT:

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