Пояснительная записка (1234703), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

В настоящее время существует очень большое количество алгоритмов построения триангуляции Делоне. Ниже приведена классификация только основных из них:

– итеративные алгоритмы:

а) простой итеративный алгоритм:

1) итеративный алгоритм «удаляй и строй».

а) итеративные алгоритмы с индексированием поиска треугольников:

1) итеративный алгоритм с индексированием треугольников R-деревом;

2) итеративный алгоритм с индексированием центров треугольников 2-d-деревом;

3) итеративный алгоритм с индексированием центров треугольников квадродеревом.

а) итеративные алгоритмы с кэшированием поиска треугольников:

1) итеративный алгоритм со статическим кэшированием поиска;

2) итеративный алгоритм с динамическим кэшированием поиска.

а) итеративные алгоритмы с измененным порядком добавления точек:

1) итеративный полосовой алгоритм;

2) итеративный квадратный алгоритм;

3) итеративный алгоритм с послойным сгущением;

4) итеративный алгоритм с сортировкой вдоль кривой, заполняющей плоскость;

5) итеративный алгоритм с сортировкой по z-коду.

– алгоритмы слияния:

а) алгоритм «разделяй и властвуй»;

б) рекурсивный алгоритм с разрезанием по диаметру;

в) полосовые алгоритмы слияния:

1) алгоритм выпуклого полосового слияния;

2) алгоритм невыпуклого полосового слияния.

– алгоритм прямого построения:

а) пошаговый алгоритм;

б) пошаговые алгоритмы с ускорением поиска соседей Делоне:

1) пошаговый алгоритм с 2-d-деревом поиска;

2) клеточный пошаговый алгоритм.

– двухпроходные алгоритмы:

а) двухпроходные алгоритмы слияния:

1) алгоритм «разделяй и властвуй»;

2) рекурсивный алгоритм с разрезанием по диаметру;

3) алгоритм выпуклого полосового слияния;

4) алгоритм невыпуклого полосового слияния.

а) модифицированный иерархический алгоритм;

б) линейный алгоритм;

в) веерный алгоритм;

г) алгоритм рекурсивного расщепления;

д) ленточный алгоритм.

Из всех вышеперечисленных алгоритмов рассмотрим следующие: простой итеративный алгоритм, итеративный алгоритм «удаляй и строй», алгоритм слияния «разделяй и властвуй» пошаговый алгоритм прямого построения, двухпроходной алгоритм слияния и двухпроходной алгоритм рекурсивного расщепления.

1.2.1 Итеративные алгоритмы построения триангуляции Делоне

Все итеративные алгоритмы имеют в своей основе очень простую идею последовательного добавления точек в частично построенную триангуляцию, т.е. подразумевается добавление точек по одной, с её перестроением на каждом шаге [20]. Такой алгоритм выглядит следующим образом:

– на первых трех исходных точках строится один треугольник;

– очередная n-я точка добавляется в уже построенную структуру триангуляции следующим образом. Вначале находится треугольник, построенный ранее, в который попадает очередная точка. Либо, если точка не попадает внутрь триангуляции, находится треугольник на границе триангуляции, ближайший к очередной точке;

– если точка попала на ранее вставленный узел триангуляция – точка отбрасывается, иначе точка вставляется в триангуляцию в виде нового узла. При этом, если точка попала на какое-либо ребро, то оно разбивается на два новых, а оба смежных с ребром треугольника также делятся на два меньших. Если же точка попала внутрь треугольника, он разбивается на три новых;

– проводятся локальные проверки вновь полученных треугольников на соответствие условию Делоне и выполняются необходимые перестроения;

– в цикле до n выполняются шаги 3-5.

Сложность в реализации [21] данного алгоритма заключается в трудоемкости поиска треугольника, в который на очередном шаге добавляется точка, трудоемкости построения новых треугольников, а также трудоемкости соответствующих перестроений структуры триангуляции в результате неудовлетворительных проверок пар соседних треугольников.

При построении нового треугольника возможны две ситуации: добавляемая точка либо попадает внутрь триангуляции, либо она находится вне ее. В первом случае строятся новые треугольники, и число выполняемых алгоритмом действий фиксировано. Во втором необходимо построение дополнительных внешних к текущей триангуляции треугольников.

1.2.1.1 Простой итеративный алгоритм

В данном алгоритме поиск очередного треугольника осуществляется следующим образом: берется случайный треугольник, который уже принадлежит триангуляции, и последовательными переходами по связанным треугольникам ищется искомый треугольник. При этом в самом худшем случае приходится пересекать все треугольники в триангуляции, поэтому трудоемкость данного поиска составляет . Однако, в среднем для равномерного распределения необходимо совершить только операций перехода [22]. Таким образом, трудоемкость простейшего итеративного алгоритма составляет в худшем случае , а в среднем случае – [23, 24].

На практике обычно используются следующие способы поиска треугольника по заданной точке внутри него и по некоторому исходному треугольнику (рисунок 12):

– проводится прямая через некоторую точку внутри исходного треугольника и целевую точку, а затем необходимо идти вдоль этой прямой к цели [23]. При этом необходимо корректно обработать те ситуации, в которых на пути могут встретиться узлы и коллинеарные ребра;

– начиная от исходной точки, и заканчивая целевой, необходимо последовательно проводить прямую через центр каждого треугольника, соответствующему стороне, которую пересекает построенная прямая [24] (рисунок 13);

– двигаясь пошагово, на каждом шаге переходить через такое ребро текущего треугольника, что целевая точка и вершина текущего треугольника, противолежащая выбираемому пересекаемому ребру, лежат по разные стороны от прямой, определяемой данным ребром [25, 26] (рисунок 14). Такой способ обеспечивает более длинный путь, но он проще алгоритмически, и потому он быстрее.

Рисунок 12 – Локализация треугольника вдоль прямой	Рисунок 13 – Локализация треугольника через ближайшее к цели ребро
Рисунок 14 – Локализация треугольника через разделяющее ребро

Для правильной работы данного алгоритма поиска существенным является то, что в триангуляции выполняется условие Делоне. Если условие нарушено, то иногда возможно зацикливание алгоритма.

1.2.1.2 Итеративный алгоритм «Удаляй и строй»

В отличии от предыдущего алгоритма, в итеративном алгоритме «Удаляй и строй» не выполняется никаких перестроений. Вместо этого, при каждом добавлении нового узла удаляются все треугольники, у которых внутрь описанных окружностей попадает новый узел. При этом на месте удаленных треугольников образуется шестиугольник, каждый угол которого соединяется с добавленным узлом [29] (рисунок 15).

Рисунок 15 – Процесс добавления нового узла в алгоритме «Удаляй и строй

Данный алгоритм строит сразу все необходимые треугольники в отличие от обычного итеративного алгоритма, где при вставке одного узла возможны многократные перестроения одного и того же треугольника. Однако здесь на первый план выходит процедура выделения контура удаленного многоугольника, от эффективности работы которого зависит общая скорость алгоритма. В целом в зависимости от используемой структуры данных этот алгоритм может тратить времени меньше, чем алгоритм с перестроением, и наоборот. Оценка трудоемкости данного алгоритма совпадает с оценками для простого итеративного алгоритма.

1.2.2 Алгоритм слияния «Разделяй и властвуй»

Концептуально все алгоритмы слияния предполагают следующий порядок действий:

– разбиение исходного множества точек на несколько подмножеств;

– построение триангуляции отдельно для каждого подмножества;

– объединение (слияние) нескольких триангулированных подмножеств в одну единую триангуляцию.

В данном алгоритме [23, 27] множество точек разбивается на две более менее равные части с помощью вертикальных и горизонтальных линий (рисунок 16).

Рисунок 16 – Разбиение множества исходных точек

Алгоритм рекурсивно применяется к подчастям, а затем производится слияние полученных подтриангуляций. Рекурсия продолжается до тех пор, пока все множество точек не разобьется на достаточно маленькие части, которые можно легко протриангулировать каким-либо другим простым способом. На практике рекурсия используется до тех пор, пока в каждом подмножестве не останется по три-четыре точки [27].

Если допустить, что число точек в триангуляции всегда будет больше пяти, то все множество точек всегда можно разбить на элементарные части по три или по четыре точки. Докажем это утверждение:

,

где – количество точек в триангуляции, – число областей, на которое можно разбить . Поясним данную формулу.

Пусть = 6. В этом случае область разбивается на две части, строго по три точки в каждой. Если добавить одну точку, в этом случае область разбивается также на две части, но в одной из частей будет три точки, а в другой. При добавлении восьмой точки, область разбивается на две части по четыре точки. Когда добавится девятая точка, область разобьется уже на три части, вновь по 3 точки в каждой, и так далее.

Пошагово алгоритм «Разделяй и властвуй» выглядит следующим образом:

– если количество точек равно трем, строится триангуляция из одного треугольника;

– иначе, если количество точек больше четырех, но меньше восьми, строится триангуляция из двух или трех треугольников;

– иначе, если количество точек равно восьми, разить множества точек на две части по четыре точки, рекурсивно применить алгоритм, затем склеить полученные триангуляции;

– иначе, если количество точек меньше двенадцати, разбить множества точек на две части по три и точки, рекурсивно применить алгоритм и склеить триангуляции;

– иначе (число точек больше двенадцати) разбить множество точек на две части и , если количество точек четно или же на и , если число точек нечетно, далее рекурсивно применить алгоритм и склеить триангуляции.

Элементарные множества из трех или четырех элементов легко триангулируются, можно элементарно перебрать множество всех вариантов (рисунок 17).

Рисунок 17 – Возможные варианты триангуляции множеств из трех и четырех точек

Трудоемкость данного алгоритма составляет как в худшем, так и в среднем случаях.

1.2.3 Алгоритм прямого построения Пошаговый алгоритм

Во всех рассмотренных выше алгоритмах на разных этапах построения триангуляции могут быть получены треугольники, которые в дальнейшем будут перестроены в связи с невыполнением условия Делоне. Основная идея алгоритмов прямого построения заключается в том, чтобы строить только такие треугольники, которые удовлетворяют условию Делоне в конечной триангуляции, а поэтому не должны перестраиваться.

Пошаговый алгоритм [29], известный также как алгоритм прямого перебора или же метод активных ребер, концептуально похож на алгоритм слияния триангуляций «Удаляй и строй». В данном алгоритме вначале выбирается некоторая базовая прямая АВ, начиная от которой будут строиться все последующие треугольники (рисунок 18). Базовая прямая берется как один из отрезков многоугольника выпуклой оболочки всех исходных точек триангуляции.

Рисунок 18 – Выбор очередной точки для включения в триангуляцию

Далее для базовой линии необходимо найти так называемого «соседа Делоне», то есть узел, который вместе с концами данной базовой линии в триангуляции Делоне является вершинами одного треугольника. Процесс поиска можно представить в виде роста «пузырька» от базовой линии, пока не встретится какой-нибудь узел [30]. «Пузырек» – это окружность, которая проходит через точки А и В, и центр которой находится на срединном перпендикуляре к базовой линии.

В пошаговом алгоритме для поиска «соседа Делоне» нужно выбрать среди всех точек триангуляции такую, что будет максимальным. В примере на рисунке 18 будет выбрана точка . Найденный «сосед Делоне» соединяется отрезками с концами базовой линии, тем самым образуя треугольник . Новые ребра и построенного треугольника обозначаются как новые базовые прямые, и процесс поиска треугольников продолжается.

Трудоемкость пошагового алгоритма составляет в среднем и в худшем случаях. Из-за столь большой трудоемкости на практике такой алгоритм почти не применяется.

1.2.4 Двухпроходные алгоритмы построения триангуляции Делоне

При построении триангуляции Делоне итеративными алгоритмами и алгоритмами слияния для каждого нового треугольника должно быть проверено условие Делоне. Если оно не выполняется, то должны последовать перестроения треугольников и новая серия проверок. На практике именно проверки на условие Делоне занимают большую часть времени.

Характеристики

Список файлов ВКР