Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
') Точнее сказать, вверх ориентировано ребро, соответствующее данной тройке.— Прим. перев.
418
Г л. 8. Геометрия прямоугольников
СТАТУС [v] =
Сосредоточим теперь внимание на эффективной реализации первого этапа алгоритма, т. е. на построении множества V вертикальных ребер контура. Как и следует ожидать, предлагаемый метод является плоским заметанием, опирающимся на дерево отрезков Т. Напоминая об общей схеме, введенной в разд. 8.3, укажем, что специальным узловым параметром, используемым в этом приложении, является СТАТУС [у], дающий грубую классификацию меры 3(][B[v], E[v]]. А именно СТАТУС может принимать одно из следующих значений:
полон, если C[v]>0; неполон, если C[v] = О, но С [и] > 0, где
и —- один из потомков и; пуст, если С[и] = 0 для любого и
в поддереве с корнем в v.
Согласно этому определению, текущее сечение 3 является объединением всех отрезков [В [v], E[v] ] для всех узлов дерева отрезков, чей СТАТУС полон.
Для заданного отрезка s = (х; Ь, е) (вертикальной стороны прямоугольника) множество s (] 3 показано на рис. 8.14; sf]3 является последовательностью промежутков между смежными элементами 3 в интервале [Ь, е]. Сторона s, помещенная в дерево отрезков, разбита на О (log Л') фрагментов хорошо известным способом.
Было бы удобно иметь 5 (] 3 в форме объединения вкладов от каждого из фрагментов. (Напомним, что каждый такой фрагмент соответствует узлу v дерева Т, для которого b s?[ ^ В [v] < E[v] ^ е.) Легко убедиться, что вклад узла v в s П 3 (вклад (и)), соответствующий одному из фрагментов s, задается так:
если СТАТУС[у] полон или СТАТУСМ полон для какого-нибудь предка v в Т; [B[v], E[v]], если СТАТУСМ пуст; вклад (ЛСЫН [о]) II вклад (ПСЫН[о]), если СТАТУС[у] неполон.
Отсюда следует, что поиск в поддереве с корнем v нужно проводить, только если СТАТУС [у] неполон. Позже мы вернемся к реализации этого поиска.
Предположим временно, что последовательность (вклад (v), где v соответствует фрагменту s) уже получена; для того чтобы
вклад (t>)= _ [B[v], E[v]]{]3-
8.5. Контур объединения прямоугольников
419
каждое контурное ребро получалось как единый элемент, смежные интервалы необходимо объединить. Эта ситуация показана на рис. 8.15. Там отрезок s = (х; Ь, е) разбит деревом Т на пять фрагментов, каждый из которых соответствует одному
I Отрезок в
Рис. 8.14. Пример множества интервалов эПУ- (Заметим, что s является горизонтальным отрезком.)
из узлов Т. Каждый из таких узлов порождает, вообще говоря, набор интервалов из а (~| 2f. Любые два смежных интервала, которые порождены разными узлами дерева отрезков, должны быть объединены. Для реализации этого интервалы из вклад(v) помещаются в СТЕК, что соответствует проходу снизу вверх
Отрезок s
Рис. 8.15. Объединение смежных интервалов, производимое при s П 3. (Вновь s изображается как горизонтальный отрезок.)
по плоской фигуре. На вершине СТЕКА всегда будет располагаться верхний конец последнего из вставленных интервалов. Если нижний конец следующего интервала, который должен быть добавлен к СТЕКУ, совпадает с вершиной СТЕКА, то последняя удаляется из СТЕКА прежде, чем верхний конец следующего отрезка будет добавлен к нему, реализуя тем самым желаемое объединение.
Теперь можно описать поиск промежутков в 3 на отрезке s=(x;b,e). В оригинальной работе Липски и Препараты использовалась стандартная структура данных и подпрограмма
420 Гл. 8. Геометрия прямоугольников
ВКЛАД (Ь,е; корень (Т)), которая вычисляет множество [Ь, е]{] [\2t на общей для них абсциссе.
procedure КОНТУР-ОБЪЕДИНЕНИЯ-
ПРЯМОУГОЛЬНИКОВ') begin X[l : 2/V] := упорядоченная последовательность абсцисс
вертикальных сторон; (* см. комментарий после
процедуры *)
•5^:=0; (* ^ — множество вертикальных ребер*) построить и инициализировать дерево отрезков Т, состоящее из ординат сторон прямоугольников; for i := 1 until 2N do
if (X[i] — абсцисса левой стороны) then
begin л^:= ВКЛАДА,e,; корень (T))\\sf>\ ВСТАВИТЬ^,-, e,-; корень(Г))
end
else begin УДАЛИТЬ (б,,*?,; корень(Г));
j^:= ВКЛАДА,e,; корень(Г)) U ^
Стоит подчеркнуть, что корректировка множества вертикальных ребер должна предшествовать вставке левой стороны, однако удаление правой стороны должно идти перед ней. Отсюда вытекает, что если какие-нибудь правая и левая стороны обладают одинаковой абсциссой, то обработка левой стороны должна предшествовать обработке правой стороны; поэтому этап сортировки в предыдущем алгоритме должен выполняться с учетом данного условия.
Осталось обсудить еще два момента. Первый связан с корректировкой специальных параметров (в данном случае СТАТУС [о]) в процедурах ВСТАВИТЬ и УДАЛИТЬ, второй —это подпрограмма ВКЛАД.
Что касается первого момента, то предлагается следующая процедура, которая, очевидно, выполняется за константное время в расчете на один просмотренный узел: procedure КОРРЕКТИРОВАТЬ(и) begin if(G>]>0) then СТАТУС[и] := полон
else if (ЛСЫН[у] = А) then СТАТУС[и] := пуст (* V — лист *) else 1Г(СТАТУС[ЛСЫН[у]] =
