Создайте непрерывную матрицу прямоугольников из множества прямоугольников

Question

У меня есть набор объектов (каждый объект содержит прямоугольник и назначенное ему значение), которое хранится в векторном контейнере. Смотрите рисунок ниже:

Мне нужно создать матрицу рисования горизонтальных и вертикальных линий в каждой у/х нижнем левом углу (LL)/верхнем правом углу (UR) координат, как показано ниже:

И Мне нужно присвоить значение = 0 каждому новому пустому прямоугольнику и другим прямоугольникам, которые находятся внутри начальных прямоугольников, мне нужно назначить их старые значения.
Я реализовал это с помощью некоторого наивного алгоритма, но он работает слишком медленно, когда у меня огромное количество прямоугольников. Мой алгоритм в основном делает следующее:
- Сохраняет все прямоугольники в контейнере карты. Каждый элемент карты содержит набор прямоугольников с одинаковой координатой LL Y, и они сортируются по координате LL X, то есть ключ является координатой LL Y.
- Сохраняет все координаты X/Y в установленных контейнерах.
- Итерации над контейнерами координат Y/X и для каждого нового прямоугольника обнаруживают, существует ли он на карте или нет, если существует - присваивает ему существующее значение, в противном случае - присваивает значение 0. I.e, для каждого нового прямоугольника он ищет свою координату LL Y на карте, если такой Y существует, затем выполняет поиск по соответствующему значению (набор прямоугольников), в противном случае - выполняет поиск по целой карте.

Есть ли эффективный алгоритм для получения нужных результатов?

Answer 1

Для п прямоугольников это может быть легко решена в O (N^3) время (или просто O (N^2) время, если не более ограниченное число прямоугольников пересекаются), глядя на эту проблему другим способом , Это должно быть достаточно для обработки до нескольких тысяч прямоугольников за несколько секунд.

Кроме того, если к проблеме добавлены некоторые другие ограничения, последняя временная граница является оптимальной: то есть существуют входы, состоящие из n непересекающихся прямоугольников, для которых O (n^2) меньше прямоугольников сетки (что, конечно, требует O (n^2) времени). Примером такого ввода является n ширина-1 прямоугольников, все имеющие равную нижнюю координату y и имеющие высоты 1, 2, ..., n.

Сетка оценки размера

Прежде всего, обратите внимание, что может быть не более 2n строк по вертикали, а не более 2n горизонтальных линий, так как каждый входной прямоугольник вводит максимум 2 из каждого вида (это может ввести меньше, если одна или обе вертикальные линии также являются реброми для некоторого уже рассмотренного прямоугольника, а также для горизонтальных линий). Таким образом, в сетке, определяемой этими линиями, может быть не более (2 * n - 1)^2 = O (n^2).

Сетки клетки координатной система

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

алгоритм

Для каждого входного прямоугольника, имеющего координаты LL (x1, y1) и UR (x2, y2), мы определяем горизонтальные и вертикальные интервалы, которые он занимает в новой системе координат сетки, а затем просто повторяют через каждую клетку (i, j), принадлежащую этой прямоугольной области (т. е. каждую ячейку сетки (i, j) такую, что для GridX (x1) < = i < toGridX (x2) и toGridY (y1) < = j < toGridY (y2)) с вложенным циклом for, записывая в хэш-таблицу, что идентификатор (цвет?) для ячейки в (i, j) должен быть цветом текущего входного прямоугольника. Входные прямоугольники должны обрабатываться с уменьшением z-порядка (неявно, по крайней мере, кажется, что такой порядок из вашего примера), так что для любой ячейки, охватываемой более чем одним входным прямоугольником, хеш-таблица завершит запись любых «ближайших», цвет прямоугольника есть. Наконец, итерация через хэш-таблицу, преобразование каждой координатной пары сетки (i, j) обратно в координаты LL и UR прямоугольника входного пространства, соответствующего этой ячейке сетки, и вывод этого прямоугольника с указанным идентификатором по значению для этого хэш-ключа.

Предварительная обработка

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

Учитывая любой углу (х, у) некоторые входной прямоугольника, сетки х координатные, соответствующий х, toGridX (х), это просто позиция ранга х в отсортированном списке всех отчетливого x положения вертикальных краев, которые присутствуют во входных прямоугольниках. Аналогично, toGridY (y) является только ранговой позицией y в отсортированном списке всех различных y позиций горизонтальных ребер, которые присутствуют среди входных прямоугольников. В другом направлении для любой координаты сетки (i, j) соответствующая координата x входного пространства из GridX (i) является просто i-м наименьшим координатом x (игнорируя дубликаты) любой вертикали краю между входными прямоугольниками и аналогично для параметра GridY (j). Все они могут быть вычислены следующим образом (все индексы массива начинаются с 0, и я только показать, как сделать это при х со-ords; у со-ords похожи):

1. Для каждого прямоугольника я на входе с координатами LL (x1, y1) и (x2, y2):
   • Добавить массив из двух элементов [x1, i] в список массивов VERT.
   • Добавить двухэлементный массив [x2, i] в список массивов VERT.
2. Сортировка списка VERT в порядке возрастания по первому элементу.
3. Объединить элементы в VERT, имеющие одинаковые координаты x. В частности:
   1. Комплект J = 0.
   2. Для г от 1 до п-1:
      • Если VERT [I] [0] == VERT [J] [0], а затем добавить VERT [ i] [1] в VERT [j] (тем самым формируя массив длиной 3 или более в позиции j), в противном случае установите j = j + 1 и перезапишите VERT [j] с помощью двухэлементного массива VERT [i].
   3. Удалить VERT [j + 1] и все последующие элементы из VERT.

4. К этому времени, для любого г, VERT [I] представляет собой массив, который содержит (в его втором и последующих позициях) идентификаторы каждого входного прямоугольника, который использует, или как его левый или правый край, то i-левая большая вертикальная линия, используемая любым входным прямоугольником, или, другими словами, вертикальная линия ранга-i. Теперь мы "инвертирует" это:

   • Для я от 0 до N-1:
     • Для J от 1 до длины (VERT [I]) - 1:
       • Набор toGridX [ VERT [i] [j]] = i.
5. Для я от 0 до длины (VERT) -1:
   • Набор fromGridX [I] = VERT [I] [0].

время

Как ранее установлено Бег, существуют в большинстве ячеек сетки O (N^2). Каждый из n входных прямоугольников может занимать не более всех этих ячеек, каждый из которых посещается один раз на входной прямоугольник, для временной границы O (n^3). Обратите внимание, что это предельно пессимистическая временная привязка, и, например, если ни один (или ни один, кроме ограниченного числа) ваших прямоугольников не перекрывается, тогда он падает до O (n^2), поскольку никакая ячейка сетки никогда не будет посещаться более одного раза.

Answer 2

Я подозреваю, что поиск и итерации не достаточно быстры. Такие вещи, как «иначе он ищет всю карту», ​​указывают на то, что вы делаете очень тяжелые вычисления.

Что я думаю, вам нужно использовать 2d datastructure. Дерево k-d или BSP будет работать, но проще всего понять и реализовать будет квадровое дерево.

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

Чтобы отметить прямоугольник с некоторым значением, вы начинаете с корня и рекурсивно:

• Если входной прямоугольник охватывает прямоугольник узла вы установите значение для этого узла, пометить его как единая и обратно.
• Если прямоугольник ввода и прямоугольник узла не касаются только возврата.
• Если узел отмечен как единый, скопируйте значение его дочерним элементам и отметьте узел неравномерным.
• Рекурсивно призывайте к 4 детям (возможно, вам придется их создавать).
• На обратном пути проверьте, имеют ли 4 ребенка одинаковое значение и все они обозначены как однородные, и, если это так, отметьте узел как однородный и установите то же значение, что и дети.

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

Вы можете найти более подробное объяснение и некоторые полезные изображения на wikipedia.

Answer 3

Предполагая, что вы знаете, высшие и наиболее нижняя y и левая и правые наиболее x, расширить четыре вектора, принадлежащие каждый прямоугольник к соответствующим максам и мин x и y баллов. Храните набор расширенных вертикальных векторов и набор расширенных горизонтальных. Всякий раз, когда добавляется расширенный вектор, он обязательно пересекается с каждым вектором в перпендикулярном списке - пересечения являются координатами ячейки матрицы.

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

В целом, этот метод представляется O(n * log m), где n - это число координат ячейки в результирующей матрице, а m - количество исходных прямоугольников.