Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
') То есть согласованность, взаимозависимость. — Прим. перев.
410
Гл. 8. Геометрия прямоугольников
сз
21~7-квадрат
СВ
21~'-ква.драт
ЮЗ 2'''-квадрат
ЮВ 2е''-квадрат
трех измерений Ван Леювеном и Вудом [Van Leeuwen, Wood (1981)], которые предложили использовать в качестве структуры данных «квадродерево» [Finkel, Bentley (1974)]. Квад-родерево можно считать двумерным обобщением дерева отрезков, но весьма курьезно, что оно было предложено раньше, чем эта более простая структура. Сейчас мы кратко опишем его организацию.
Квадродерево — это способ организации ортогональной сетки, состоящей из N ХМ ячеек, определенных (JV+1) горизонтальными и (Af-f-l) вертикальными прямыми. (Дерево отрезков — это соответственно способ организации N смежных интервалов.) Для простоты изложения предположим, что N = М = 2*. Квадродерево Г —это дерево со степенями исхода, кратными четырем, у которого с каждым узлом связан участок сетки размером 2l X 2* (именуемый 2,!-квад-ратом) (;=0, 1, k). 2*-квад-рат, связанный с заданным узлом v из Т (при />0), разбивается на четыре 2г-'-квадрата вертикальным и горизонтальным делениями пополам (рис. 8.9); каждый из этих четырех квадратов (именуемых СЗ, СВ, ЮВ и ЮЗ квадратами) связывается с одним из четырех потомков узла v. Данное построение начинается со связывания всей сетки с корнем Т, а заканчивается тогда, когда процесс четвертования дает 2°-квадраты (листья Т). Поскольку Т обладает N2 листьями, то его построение занимает 0(N2) времени и использует 0(N2) памяти.
Теперь мы рассмотрим вопрос о хранении прямоугольника/? в квадродереве. Исходная сетка образована 2N абсциссами и 2N ординатами сторон заданных N прямоугольников, и квадродерево Т строится на этой сетке. Каждый узел v из Т обладает одним целочисленным параметром C[v], который вначале равен 0 (такое квадродерево называется скелетным). Прямоугольник R вносит 1 в C[v] тогда и только тогда, когда (1) R содержит квадрат, относящийся к о, и (2) ни один из предков v в Т не обладает таким же свойством. Очевидно, что таким образом определяется однозначный способ разбиения R на квадраты, каждый из которых связан с одним узлом v. В то время как в дереве отрезков каждый отрезок разбит на не более чем
Рис. 8.9. Пример разбиения плоской сетки, осуществляемого одним из узлов квадродерева, который соответствует 2'-квадрату.
8.4. Мера и периметр объединения прямоугольников 411
О (log//) интервалов, для квадродерева можно относительно просто показать1), что один прямоугольник разбивается на не более чем 0(N) квадратов. Поэтому процедуры вставки и удаления в квадродереве, а также определение меры объединения (площади) можно реализовать каждую за O(N) операций. Отсюда следует, что последовательная корректировка сечений
ЯкЛад t периметр
их абсциссе X[i-l}~~~*'
Рис. 8.10. Иллюстрация к вычислению суммарной длины вертикальных сторон.
при пространственном заметании занимает O(N) времени, а поскольку существует 2N сечений, то решение задачи определения меры объединения в трехмерном пространстве займет в сумме 0(N2) времени. Именно данный метод —а не двумерный, основанный на дереве отрезков, — можно использовать в качестве базиса индукции и доказать следующий результат:
Теорема 8.2. Меру объединения N изотетичных гиперпрямоугольников при d ^ 3 измерениях можно вычислить за время 0(№~1).
Хотя кажется, что улучшить этот результат будет весьма трудно, нет никаких данных о его возможной оптимальности.
Замечание. Приведенный алгоритм вычисления меры объединения прямоугольников можно модифицировать для решения следующей задачи.
') Доказательство можно найти в статье [Van Leeuwen, Wood (1981)].
412
Гл. 8. Геометрия прямоугольников
Задача 0.3 (ПЕРИМЕТР ОБЪЕДИНЕНИЯ ПРЯМОУГОЛЬНИКОВ). Дано объединение F, состоящее из N изотетичных прямоугольников. Найти периметр F, т. е. длину его границы.
Метод решения основан на следующем наблюдении. Предположим, что на /-и итерации некий прямоугольник вставляется в дерево отрезков или удаляется из него (мы условились говорить, что прямоугольник вставляется или удаляется, если заметающая прямая касается его левой или правой стороны соответственно). Обращаясь к рис. 8.10, напомним, что т,- обозначает суммарную длину вертикального сечения непосредственно слева от X[i] (см. строку 6 алгоритма МЕРА-ОБЪЕДИНЕНИЯ-ПРЯМОУГОЛЬНИКОВ). Суммарная длина вертикальных кусков границы F на сечении X[i—1] равна разности длин вертикальных сечений F непосредственно слева и справа от X[i—1]. В то время как первая из этих длин равна m,--i по определению, вторая равна пи, поскольку сечение неизменно на всем интервале [X[i—1],^[/]]. Поэтому искомая суммарная длина равна |т,- — m,_i|'). Кроме того, необходимо учесть вклад горизонтальных граничных сторон, расположенных внутри вертикальной полосы. В интервале [X[i—I], A" [t] ] этот вклад, очевидно, равен (X[i] — X[i — 1] )Х ш, где целое число а,- равно количеству горизонтальных сторон границы F внутри рассматриваемой вертикальной полосы. Параметр а;, по сути, весьма похож на mi. Действительно, введем для каждого узла v в дереве отрезков три новых специальных параметра, один четный целый параметр a [v] и два двоичных параметра ЛКРЫ и ПКР [у]2). Обозначая через J текущее вертикальное сечение F (3 — набор не связанных между собой интервалов), определяем эти параметры следующим образом:
