Область объединения прямоугольников с использованием сегментированных деревьев

Question

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

Решение, которому я следую, здесь: http://tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/

Часть, которую я не понимаю:

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

• каждому узлу соответствует интервал y, представляющий собой объединение элементарных интервалов y по всем индексам вдиапазон узла.
• если значение узла равно нулю, оценка является суммой баллов потомков (или 0, если узел является листом).
• , если значение узлаположительно, оценка равна длине y-интервала, соответствующего узлу.

Как этого добиться в O (n log n)?

Моя идея состояла в том, чтобы создать дерево сегментов и обновлять значение каждого диапазона, как и когда мы сталкиваемся с диапазоном (диапазон y как высота прямоугольника) во время подметания линии.И затем для каждого интервала (два последовательных элемента в отсортированном массиве x, кратные Δx общей длине диапазона y, активного в этом интервале, путем просмотра суммы всех элементов в дереве сегментов)

Это все равно приведет нас к наличию элементов max (y) - min (y) в базе дерева сегментов.

Следовательно, я не уверен, как это O (n log n) - где n - этоколичество прямоугольников.

Буду очень признателен за любую помощь здесь.

Спасибо!

Answer 1

Давайте рассмотрим простой случай:

В соответствии с вашим пониманием вы создадите дерево сегментов с 11 - 1 = 10 узлами в основании, что-то вроде этого:

Обратите внимание, у нас есть только 9 узлов в базе, потому что первый узел для интервала [1,2], следующий для интервала [2,3] ии так далее

И когда вы вводите какой-либо прямоугольник, вы обновляете его диапазон на основе его координат y, поэтому после встречи с первым из них при x = 0 дерево вашего сегмента будет выглядеть так:

Нам также потребуется использовать то, что называется ленивым распространением, для обновления активных интервалов в дереве, чтобы все активные интервалы вносили 1 в сумму.

Таким образом, сложность вашего текущего подхода - это что-то вроде O (K log K), где K = max (y) -min (y)

. Мы можем легко уменьшить это значение до O (n log n), где n - числопрямоугольники.

Обратите внимание, что существуют только важные координаты y, поэтому в этом примередостаточно 1,3,6,11

Также обратите внимание, что таких координат не более 2 * n

Так что мы можем сопоставить все координаты некоторым целым числам, чтобы они лучше подходили для дерева сегментов.

Это называется сжатием координат, это можно сделать примерно так:

1. Сохранить все координаты y в массиве
2. отсортировать массив и удалить дубликаты
3. используйте map или hashMap, чтобы отобразить исходные координаты в их положение в отсортированном массиве

Так что в нашем примере это будет:

1. [1,3,6,11]
2. нет дубликатов для удаления, так что массив все еще [1,3,6,11]
3. mp[1]=1, mp[3]=2, mp[6]=3, mp[11]=4

Так что теперь алгоритм остается прежним, но мы можем использовать дерево сегментов с не более чем 2 * n узлами вэто база.

Также нам нужно было бы немного изменить наше дерево сегментов, вместо того, чтобы сохранять, какие координаты y включены или выключены, теперь мы будем сохранять, какие интервалы координат y включены / выключены

Так что мы будемиметь узлы для интервалов [y0, y1], [y1, y2], ... для всех уникальных отсортированных значений y.

Также все узлы будут вносить y [i] -y [i-1] всумма (если они находятся в диапазоне и активны) вместо одного.

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

Answer 2

Как нам добиться этого в O (n log n)?

Рассмотрим для каждого прямоугольника, вы собираетесь обновить диапазон [x, y] в двоичном дереве сегментов. По сути, что происходит, вы

• поиск х в качестве левой границы в дереве (время log (N))
• поиск y в качестве правой границы в дереве (время log (N))

Предположим, что узел, который вы нашли для x, это [x, a], и у него есть родительский узел [z, a], а у этого родительского узла есть родной брат [a, b]. Очевидно, что если y не находится под [a, b], охватывается весь диапазон [a, b], поэтому вы увеличиваете этот узел вместо всех отдельных узлов сегмента в поддереве [a, b].

В результате процесс поиска / обновления выглядит следующим образом.

• Если родительский узел [a, c] имеет двух дочерних элементов [a, b], [b, c] и левая граница x находится в [a, b], решить, следует ли увеличивать значение в узле [b , с] (в зависимости от того, больше ли у с)
• Если родительский узел [a, c] имеет двух дочерних элементов [a, b], [b, c] и правая граница y находится в [b, c], решить, следует ли увеличивать значение в узле [a , б] (в зависимости от того, х меньше а)

По сути, прежде чем погрузиться в один узел, решите, обновлять его или нет.

Число узлов, которые вы решаете, обновлять или нет, - это log (N) (для x) + log (N) (для y).