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

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

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

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

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

Общее количество выполняемых перестроения в алгоритме невыпуклого слияния составляет около 35% от общего числа треугольников в конечной триангуляции, в алгоритме выпуклого слияния – 70%, в алгоритме «Разделяй и властвуй» – 90%, а в простом итеративном алгоритме – 140%. Именно поэтому наиболее хорошо для двухпроходной стратегии подходит алгоритм невыпуклого слияния. В алгоритмах «Разделяй и властвуй», выпуклого слияния и рекурсивном с разрезанием по диаметру на промежуточных этапах строится некоторое количество длинных узких треугольников, которые обычно затем перестраиваются. Пример применения двухпроходной стратегии к алгоритму выпуклого полосового слияния приведен на рисунке 19.

Рисунок 19 – Двухпроходной алгоритм выпуклого полосового слияния

В [24] показывается, что двухэтапные полосовые алгоритмы и алгоритм «Разделяй и властвуй» работают в среднем на 10-15% быстрее оригинальных алгоритмов (таблица 1). Это объясняется некоторым упрощением логики их работы.

Таблица 1 – Сравнение одно- и двухпроходных алгоритмов слияния

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

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

Перед началом работы алгоритма вычисляется выпуклая оболочка всех исходных точек. На каждом шаге рекурсии для заданного множества точек и их оболочки выполняется деления всех точек на две части. Для этого на оболочке находятся противоположные точки и , делящие многоугольник оболочки примерно пополам. Затем находятся все точки среди заданных, не попадающие на оболочку и находящиеся от прямой не более чем на заданном расстоянии , т.е. попадающие в некоторый коридор расщепления (рисунок 20).

Рисунок 20 – Выбор направления и коридора

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

Затем точки , и последовательно соединяются в ломаную, которая разбивает исходное множество точек на две части. Разделяющая ломаная при этом попадает в оба множества (рисунок 21).

Рисунок 21 – Первый шаг расщепления

Кроме того, так как оболочка невыпуклая, то необходимо исключить случаи возможного пересечения построенной ломаной с оболочкой. Если полученные множества не являются треугольниками, то к ним опять рекурсивно применяется данный алгоритм (рисунок 22).

Рисунок 22 – Второй шаг расщепления

После построения триангуляций отдельных частей выполняется их соединение вдоль разделяющей ломаной (рисунок 23, 24).

Рисунок 23 – Построение триангуляции	Рисунок 24 – Перестроение триангуляции

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

2 ОПИСАНИЕ АЛГОРИТМА ДВУМЕРНОЙ ТРИАНГУЛЯЦИИ

При создании плоской вычислительной сетки, возникли три основных вопроса:

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

– как расположить узлы на каждой линии уровня;

– как соединить узлы двух соседних линий уровня.

2.1 Алгоритм расположения линий уровня

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

Однако на этом этапе возникает очень важный вопрос, как будут располагаться линии уровня в заданной области. Очевидно, если мы зададим область условно сто сантиметров и количество линий уровня равное десяти, то по принципу степенной сетки, располагаться они будут следующим образом (таблица 2).

Таблица 2 – Расположение 10 линий уровня

Исследуемая область	Количество линий уровня	Расстояние от каждой линии уровня до центра
		1	2	3	4	5	6	7	8	9	10
100	10	1	4	9	16	25	36	49	64	81	100

И выглядеть такое расположение будет следующим образом (рисунок 25).

Рисунок 25 – Расположение 10 линий уровня

Необходимо выяснить, как должна вести себя сетка, если добавить еще одну линию уровня, или напротив убрать одну линию. Самым простым решением могло бы стать следующее: если взять исследуемую область в 100 сантиметров, то при добавлении одной линии уровня, согласно степенной сетке, добавить ее на расстояние 121 сантиметр от центра. Если же необходимо убрать одну линию уровня, то достаточно просто не обрисовывать последнюю линию, таким образом, последней линией уровня станет девятая линия, и располагаться она будет на расстоянии 81 сантиметр от центра. Однако это в корне неверное решение, так как независимо от количества линий уровня сетка должна строиться строго в заданной пользователем области.

Еще раз рассмотрим случай, когда исследуемая область равно 100 сантиметров, и количество линий уровня равно десяти (таблица 1). Так как расстояние от каждой последующей линией уровня до центра равно соответственно и т.д., то возьмем за основу отношение расстояния между последующей линией уровня и центром к расстоянию между текущей линией уровня и центром. То есть, отношение расстояния между второй линией уровня и центром к расстоянию между первой линией и центром будет равно 4:1, отношение расстояния между третьей линией уровня и центром к расстоянию между второй линией уровня и центром будет равно 9:4 и т.д.

Таким образом, при исследуемой области 100 сантиметров и двух линиях уровня, первая и вторя линии уровня будут располагаться на расстоянии 25 и 100 сантиметров соответственно от центра. Если исследуемая область будет 200 сантиметров, и на ней будут также две линии уровня, то располагаться они будут на расстоянии 50 и 200 сантиметров от центра и т.д. В таблице 3 приведены расстояния от каждой линии уровня до центра для одиннадцати линий уровня

Таблица 3 – Расположение различного количества линий уровня

Исходя из результатов таблицы 3, алгоритм, по которому располагаются линии уровня будет следующим:

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

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