Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Рис. 2.18. Заданная триангуляция (а) и та же триангуляция внутри охватывающего ее треугольника (Ь).
(1983)] — может стать практичным алгоритмом; он описан в данном разделе. Второй метод [Edelsbrunner, Guibas, Stolfi (1985)] является дальнейшим улучшением метода цепей и будет кратко описан в разд. 2.4.
Метод «детализации триангуляции» принадлежит Киркпат-рику. Предполагается, что ЛА-вершинный ППЛГ является триангуляцией (см разд. 1.3.1); в том случае, если он не триангуляция, его можно преобразовать в нее за время 0((jVlogyV) с помощью простого алгоритма, который будет описан в разд. 6.2.2. Напомним, что триангуляция на множестве вершин V на плоскости есть ППЛГ с максимальным числом ребер, не превышающим 31 V] — 6 (по формуле Эйлера) Кроме того, по причинам, которые скоро станут ясными, триангуляцию удобно окружить треугольной границей путем построения охватывающего ее треугольника и триангулирования области между этими двумя объектами (рис. 2.18). С учетом этого замечания все триангуляции будут считаться обладающими границей с тремя вершинами и ровно с 3| V\— 6 ребрами.
Пусть задана jV-вершинная триангуляция G, и предположим, что строится последовательность триангуляции Su S2, .. ., Sh(nf), Si = G, a St получается из S;-i по следующим правилам:
(Ь)
Гл. 2. Геометрический поиск
Шаг (1). Удалим некоторое множество независимых (т. е. несмежных) неграничных вершин S»-i и инцидентные им ребра. (От выбора этого множества, который будет описан ниже, самым непосредственным образом зависит эффективность алгоритма.)
Шаг (2). Вновь триангулируем многоугольники, образовавшиеся в результате удаления вершин и ребер.
Таким образом, Sh{N) не имеет внутренних вершин (т. е. состоит из одного треугольника).
Заметим, что все триангуляции 5Ь S2, . . ., SnW имеют одну общую границу, поскольку на шаге (1) мы удаляем только внутренние вершины. Треугольники, главные объекты этого метода, будем обозначать буквой R, снабжая ее индексами. Треугольник Rj может появляться во многих триангуляциях, однако условимся, что Я/ принадлежит триангуляции 5,-(обозначая #/e*S,-), если Rj создан на шаге (2) при построении St.
Теперь построим структуру данных Т для поиска; узлам этой структуры соответствуют треугольники. (Для краткости узел часто будет называться «треугольник Rj» вместо «узел, представляющий треугольник Я/».) Структура Т, топологию которой представляет направленный ациклический граф, определяется следующим образом: от треугольника Rk к треугольнику Rj проводится дуга, если при построении 5,- после S,--i мы имеем:
1) Rj удаляется из S,_i на шаге (1);
2) Rk создается в 5; на шаге (2);
3) я/п я» 0.
Очевидно, что треугольники из S\ не имеют исходящих дуг в Т, и только они обладают этим свойством.
Для ясности удобно изобразить Т в рассмотренном виде, т. е. помещая его узлы в горизонтальные строки, каждая из которых соответствует какой-нибудь триангуляции. Последовательность триангуляции показана на рис. 2.19(a); кружком обведены вершины, которые удалены на данном шаге. Соответствующая структура Т показана на рис. 2.19(b).
После построения Т легко понять, как происходит локализация точки. Элементарной операцией является «принадлежность треугольнику», которая, очевидно, выполняется за время 0(1). Начальный шаг состоит в локализации пробной точки z относительно Sh(jv). Затем идем вниз по пути в Г и неизбежно остановимся в одном из треугольников, принадлежащих Si. Построение данного пути происходит следующим образом: если достигнут какой-то узел на этом пути (т. е. z локализована в соот-
2.2. Задачи локализации точки
77
ветствующем ему треугольнике), то проверяется принадлежность точки z всем потомкам этого узла; поскольку z принадлежит ровно одному из потомков, то в путь добавляется еще одна дуга. Этот поиск можно также рассматривать как последовательную локализацию z в триангуляциях Sh(n), Skw-u • • •, Si. То, что Si-i является результатом детализации 5,-, объясняет наименование самого метода.
Более строго, предположим, что все потомки узла и из Т собраны в список Г (и), и пусть ТРЕУГОЛЬНИК(о) обозначает треугольник, отнесенный к узлу v. Теперь мы получили следующий поисковый алгоритм:
procedure ЛОКАЛИЗАЦИЯ-ТОЧКИ begin if (г ф. ТРЕУГОЛЬНИК (корень)) then печать "z лежит в бесконечной области" else begin v := корень;
while (T(v) Ф 0) do
for каждый u e T(v) do if (геТРЕУГОЛЬНИК(и)) then v:=u; печать v
end
end.
Как упоминалось ранее, от выбора множества вершин триангуляции, которые будут удалены при построении Si по 5,_ь
78
Гл. 2. Геометрический поиск
существенно зависит эффективность метода. Предположим, что можно выбрать это множество так, чтобы выполнялись следующие свойства (здесь через А/,- обозначено число вершин в Si):
Свойство 1. Nt — a.iNi-1, где оы ^ а < 1 для I — 2, . . ., h(N).
Свойство 2. Каждый треугольник Rj е пересекается не более чем с Н треугольниками из Si-\, и наоборот.
Свойство 1 немедленно влечет за собой следствие, что h(N) ^ [\og\/aN~\ == О (log N), поскольку при переходе от S,--i к Si удаляется по меньшей мере фиксированная доля вершин: Из свойств 1 и 2, вместе взятых, следует, что память для / равна O(N). Действительно, заметим, что эта память используется для хранения узлов и указателей на их потомков. Из теоремы Эйлера о плоских графах следует, что 5,- содержит Fi <с 2Ni треугольников. Число узлов Т, представляющих треугольники из Si, не превосходит Ft (только те треугольники, которые действительно «принадлежат» 5„ появляются на соответствующем ярусе Т). Отсюда следует, что общее число узлов в Т меньше, чем
