Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
В методе трапеций не требуется, чтобы граф был триангулирован; на самом деле позднее мы увидим, что не требуется даже прямолинейности его ребер. Однако на некоторое время допустим, что имеется ППЛГ G. Множество вершин V графа G упорядочено по возрастанию их ординат, а множество его ребер Е упорядочено в соответствии со следующим отношением (частичного порядка) «-ф>:
Определение 2.6. Даны два ребра ех и е2 из Е; запись ei<(e2 (читается «ei левее е2») обозначает, что существует горизонталь, пересекающая оба ребра, и точка ее пересечения с е\ будет левее соответствующей точки на е2. (Позднее (в примечании 1, с. 87) мы обсудим, как алгоритмически получить это упорядочение.)
Основной механизм, строящий структуру данных поиска, обрабатывает по одной трапеции и стремится разбить ее на мак-
2.2. Задачи локализации точки
симально возможное число более мелких трапеций Это делается путем разрезания трапеции R на «нижний» и «верхний» слои R\ и #2 горизонталью, проходящей через ту вершину ППЛГ, чья ордината является медианой множества ординат вершин внутри R. Каждый из этих слоев R{ и R2, хотя и является гео-
Рис. 2.20. Трапеция R (а), разбитая на трапеции R3, Rt, /?5, Rs и R7, как показано на (Ь).
метрической трапецией, удовлетворяет не всем условиям определения 2.5, поскольку некоторые ребра ППЛГ могут пересекать одновременно обе его горизонтальные стороны; такие ребра назовем накрывающими. Теперь каждое ребро, накрывающее один из слоев1), определяет его последующий разрез.
Проделываются следующие операции. После определения медианы у = г/med трапеции R (рис. 2.20) цепочка ребер ППЛГ, пересекающих R, просматривается слева направо и разделяется на две цепочки, относящиеся к слоям Ri и R2 соответственно.
') Никакое ребро не может накрывать и Ru и R2, иначе оно накрывало бы трапецию R, что противоречит определению.
Гл. 2. Геометрический поиск
Всякий раз, когда встречается накрывающее ребро, оно становится правой боковой границей новой трапеции, которая может обрабатываться независимо. Если внутренность трапеции пуста (ребра ППЛГ не пересекают ее), то ее обработка тривиальна.
Структура данных поиска, соответствующая трапеции с рис. 2.20, изображена на рис. 2.21. Каждой трапеции R соответствует дерево двоичного поиска T(R), каждый узел которого
TIR):
T(R4) Т(/?5)
Рис. 2.21. Структура данных поиска, соответствующая трапеции с рис. 2.20.
связан с линейной проверкой. Удобно различать узлы двух типов: V-узлы, если соответствующая проверка проводится относительно горизонтали, и О-узлы, если эта проверка ведется относительно прямой, несущей ребро ППЛГ. Очевидно, что корень T(R) всегда будет V-узлом. Заметим, что любому V-узлу соответствует единственная вершина ППЛГ, а именно такая вершина, ордината которой является медианой множества ординат вершин ППЛГ в данной трапеции. Поскольку две крайние вершины ППЛГ не участвуют в разбиении трапеции, то число V-уз-лов в дереве поиска будет равно N — 2.
Более формально, процедура-функция ТРАПЕЦИЯ, строящая дерево поиска, получает на входе: Е — цепочку ребер ППЛГ, V — последовательность вершин внутри R, упорядоченную по возрастанию их ординат, и у—интервал / трапеции R. В процедуре используются вспомогательные операции, такие как «поиск медианы» и «балансировка», которые будут описаны позже; Е\, Е2, U\ и U2— рабочие списки этого алгоритма.
1 function ТРАПЕЦИЯ(?,У,/)
2 begin \\{V = 0) then return Л (* лист дерева поиска *)
3 else begin е, := Е2 := К, := V2:=U:=0;
4 Уты:= медиана множества ординат V;
5 /,:=[тт(/),г/те(1]; /2:=fymed, тах(/)];
6 repeat е<=Е;
7 for «= 1,2 do
2.2. Задачи локализации точки
8 begin if(е имеет конец р
внутри Rt) then
9 begin Ei<=e;
10 Vt:=Vt[){p) end;
11 if(e накрывает RJ
или (e = A) then
12 begin Ut<= ТРАПЕ-
ЦИЯ(Я,,У,,/,);
13 lt(e Ф Л)
then Ut<=e;
14 ?,:=K,:=0 end
end
15 until e = A;
16 новый(ш); (* создание нового V-узла w, корня T(R) *)
17 Y[w]:— ymed\ (* дискриминация узла w *)
18 ЛДЕРЕВО[ш] := БАЛАНС^);
19 ПДЕРЕВОИ := БАЛАНСА);
(* функция БАЛАНС принимает на входе чередующуюся последовательность из деревьев и ребер и организует их в сбалансированное дерево *)
20 return ДЕРЕВОМ end
end.
В этом алгоритме выделяются три основных действия:
1) определение медианы множества ординат вершин в R;
2) разбиение нижнего и верхнего слоев на трапеции и получение для каждого слоя Ri (i = 1, 2) цепочки Ui, состоящей из ребер и деревьев (в нашем примере U2 = T(R3)eiT(Ri)e3T(R5), a (/i = T(Rs)e2T(R7)). На это уходит большая часть всей работы, и делается она в цикле repeat в строках 6—15;
3) балансировка двух цепочек U\ и U2 (строки 18 и 19). Первое действие можно выполнить в принципе за время
0(| V\) с помощью классического алгоритма поиска медианы. Однако существует более простой и прямой путь. Вершины трапеции располагаются в массиве по возрастанию ординат. (Медиану этого массива можно найти за одно обращение.) Модификация процедуры ТРАПЕЦИЯ происходит следующим образом. Последовательность ребер просматривается дважды. При первом проходе каждая вершина просто помечается именем той трапеции, к которой она отнесена, непосредственно используя эти пометки, строится массив вершин для каждой порождаемой
