Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
каждого из этих множеств дважды прошитый двусвязный список следующим образом: каждой точке р сопоставим узел, содержащий информацию (из(р), и4(р)); кроме того, имеется два указателя СЛЕДЗ и СЛЕД4, описывающие упорядочение по осям и3 и «4 соответственно. Связи в обратном направлении устанавливаются двумя дополнительными указателями ПРЕДЗ и ПРЕД4. Временно пренебрежем затратами на построение дважды прошитых списков.
Обозначим через НАЧ31 и НАЧ32 указатели на начальные (первые) элементы по координате и3 в списках Sn и S22 соответственно. Предлагаемый алгоритм имеет общую форму плоского заметания, точками событий которого являются координаты иг точек множества 5ц U S22, а статус заметающей прямой представлен списком 3?'. Этот список содержит упорядоченную по возрастанию координаты и4 последовательность точек из Sn (а именно и4-координаты тех точек из Sn, чьи координаты по оси из не превосходят текущего значения в процессе заметания). Временно будем использовать обозначения СЛЕД.!? и HA4J? для прямого и начального указателей в списке SB, хотя,
>DZ
Гл. 8. Геометрия прямоугольников
как будет показано ниже, СЛЕД.!? можно заменить на СЛЕД4. Предлагается следующий алгоритм:
procedure ОБЪЕДИНЕНИЕ
1 begin /,:=НАЧ31; /2:=НАЧ32;
2 while (/2 Ф A) do
3 begin И(«3[/|КнзШ) then
4 begin вставить u4[/,] в S?
с сохранением упорядоченности;
5 /, := СЛЕДЗ[/,]; end
6 else begin / := НАЧ2*;
7 while (/ Ф A) and (u4[/2] > ut[l]) do
8 begin печать (/2,/);
9 / := СЛЕДЭД]; end;
10 /2:=СЛЕДЗ[/2];
end
end
end.
Такой алгоритм, очевидно, по структуре относится к типу алгоритмов слияния. В строке 3 производится проверка возможности продвижения по Sn или по 522. В первом случае надо вставить ut[ji] в 3? (строка 4). Во втором случае (строки 6—9) надо просмотреть список j?, начиная с самого малого из его элементов, и определить при этом все такие точки, над которыми доминирует pj2\ эта часть алгоритма работает последовательно и затребует времени, пропорционального числу выданных на печать пар (/2, /).
Самая важная часть процедуры находится в строке 4: «Вставить и4[/] в 3? с сохранением упорядоченности». Действительно, на первый взгляд кажется, что на это понадобятся затраты времени, пропорциональные |Sn|2, поскольку каждая вставка может потребовать полного обхода S; однако более совершенная структура данных для 3? — перестраиваемое дерево (т. е. дерево, сбалансированное по высоте или по весу) — сократила бы затраты общего времени до 0(|5И |log|5n |). Вместе с тем существует один интересный способ организации решения данной задачи, такой, что его суммарные затраты времени равны 0(|5ц|). Наша цель состоит в том, чтобы создать расписание вставок в список 2? элементов из ы4-списка для 5ц. Обращаясь к рис. 8.35, реализуем эту цель следующим образом. Ясно, что координату по оси ы4 крайнего справа элемента Su, т. е. р$, надо вставить в список 3? (т. е. в упорядоченную по координате и4 последовательность точек, лежащих слева от р8) между «4[3] и и4[5]. Но а4[3] — это не что иное, как ПРЕД4[8]; еле-
8.8. Пересечения прямоугольников
449
довательно, ПРЕД4[8] и указывает ту позицию, в которой надо вставить и4[8] в 9?. Теперь, удалив р8 из ц4-списка и повторяя процедуру для остатка этого списка, получим позицию для вставки нового элемента и4[7]. Сканируя подобным образом
(а) (Ъ)
Рис. 8.35. Пример множества Sn = {ри ..., р8} и соответствующего ему дважды прошитого списка. Приведены связи для указателей СЛЕДЗ и СЛЕД4.
«з-список в порядке убывания, получаем расписание вставок всех элементов из и4-списка; формальной записью этой идеи является следующий алгоритм:
begin /:= ПОСЛЕДНИЙ ЭЛЕМЕНТ («3-списка); while (ПРЕДЗИ ф НАЧЗ) do
begin СЛЕД4[ПРЕД4[/]]:=СЛЕД4[/]; ПРЕД4[СЛЕД4[/]] := ПРЕД4[/]; /:=ПРЕДЗ[/]
end
end.
Пример. Для множества 5И, изображенного на рис. 8.35(a), на рис. 8.35(b) показана начальная конфигурация ы3- и г;4-спи-сков. Начальная конфигурация массива ПРЕД4 такова:
J: 123456 7 8
ПРЕД4: |7|5|4|l|s|2 | НАЧ | 3 |
15 Зак. 1075
450
Гл. 8. Геометрия прямоугольников
Эволюция этого массива в процессе сканирования компактно изображена в следующей таблице (корректируемые элементы обведены кружками): Таблица 1
После
_______.....„ j: 1 г 3 4 S Б 7 8 сканирования
Рт Ре PS Pi Рз
Р2
Следовательно, окончательная конфигурация массива ПРЕД4 полностью определяет расписание вставок в список 3 (который становится и4-списком после окончания сканирования), и строку 4 процедуры ОБЪЕДИНЕНИЕ можно выполнить за константное время. Это доказывает тот факт, что вся процедура ОБЪЕДИНЕНИЕ затрачивает |Sn| + |S22| времени плюс еще столько времени, каково число найденных пар доминирований точек. Имея теперь в своем распоряжении процедуру ОБЪЕДИНЕНИЕ, мы можем заняться организацией всей процедуры ДОМИНИРОВАНИЯ.
Сначала займемся структурой данных. После сортировки множества 5 по каждой из четырех координат получаем четырежды прошитый список (ЧПС). Как и в упомянутом ранее дважды прошитом списке, здесь все связи будут двусторонними, а указатели СЛЕД/ и ПРЕД/ будут использоваться для ы;-списка. Очевидно, что построение ЧПС для 5 потребует O(NlogN) времени. ЧПС весьма естественно подходит для реализации за линейное время операций по разбиению множеств, определяемых на шагах Д1 и С1 в ранее изложенных алгоритмах. Действительно, предположим, что надо разбить S на пару (Si, S2) и пометить элементы Si. Тогда, если пройти по ЧПС с помощью любого выбранного указателя СЛЕД; при i=l, 2, 3, 4, то список, соответствующий этому указателю, можно разбить на два списка, которые соответствуют двум подмножествам разбиения: Si и S2. Аналогично, если заданы Si и S2, то можно слить два соответствующих им списка, используя «естественное слияние» [Knuth (1973)], за линейное время.
