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

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

– заданная исследуемая область делится на величину , где n – количество линий уровня. То есть при заданной области в сто сантиметров и одной линии уровня, область делится на единицу, при двух линиях уровня область делится на 4, при трех линиях – на 9 и т.д.;

– величина, которая получается в результате деления исследуемой области на – это расстояние от центра до первой линии уровня, эта величина записывается в отдельную неизменяемую переменную, назовем ее m.

– расстояние от центра до всех последующих линий уровня является результатом умножения величины m на , где t = 2...n.

Реализовав данный алгоритм, можно перейти к решению следующего основного вопроса.

2.2 Алгоритм расположения узлов на линиях уровня

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

Рисунок 26 – Расположение узлов на линиях уровня

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

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

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

2.3 Алгоритм соединения узлов

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

– выбираются два соседних узла на предыдущей линии уровня;

– между этими узлами проводится биссектриса до текущей линии уровня, получаем точку пересечения биссектрисы и текущей линии уровня;

– полученная точка сравнивается со всеми узлами, расположенными на текущей линии;

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

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

Алгоритм выполняется для каждой пары двух соседних узлов на предыдущей линии уровня. Результат выполнения данного алгоритма представлен ниже (рисунок 27).

Рисунок 27 – Результат выполнения алгоритма

Однако, как можно заметить, в этом алгоритме есть одно упущение: некоторые узлы не соединяются. Это происходит из-за того, что не существует двух таких соседних узлов на предыдущей линии, для которых расстояние между узлом текущей линии и биссектрисой было бы минимальным. Чтобы исправить это упущение, необходимо добавить условие, что если с узлом на текущей линии уровня не происходило взаимодействия, то этот узел соединяется с ближайшим узлом на предыдущей линии. Результат завершенного алгоритма представлен на рисунке 28.

Рисунок 28 – Результат работы завершенного алгоритма

3 РЕАЛИЗАЦИЯ АЛГОРИТМА ДВУМЕРНОЙ ТРИАНГУЛЯЦИИ

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

3.1 Описание используемых переменных

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

double x = 0;

double xPrevious = 0;

double pi = acos(-1.0);

double length = ui->lineEdit->text().toDouble();

double arc1 = ui->lineEdit_2->text().toDouble();

double count = ui->lineEdit_3->text().toInt();

double arc = -arc1*pi/180;

double angle = 0;

double n = 1;

double m = 0;

double power = 0;

double t = 1;

double step = 0;

QVector <double> previous;

QVector <double> mathPrevious;

QVector <double> halfPrevious;

QVector <double> current;

Рассмотрим отдельно каждую переменную:

– x – это расстояние от текущей линии уровня до центра исследуемой области;

– xPrevious – расстояние от предыдущей линии уровня до центра исследуемой области;

– pi ­ число , значению pi присвоен арккосинус минус единицы, потому что арккосинус минус единицы и есть число ;

– length – радиус исследуемой области. Данной переменной присвоено значение, которое введет пользователь;

– arc1 – угол (в градусной мере) исследуемой области. Данной переменной присвоено значение, которое введет пользователь;

– count – количество линий уровня. Данной переменной присвоено значение, которое введет пользователь;

– arc – угол (в радианной мере) исследуемой области. Дело в том, что компьютер работает только с радианными величинами. Так как пользователь вводит угол в градусах, их необходимо перевести в радианы. В последующем будет использоваться именно эта переменная;

– angle – угол, зависящий от шага, на расстоянии которого будут располагаться друг от друга узлы на линии уровня;

– n, m, power, t – второстепенные переменные для реализации алгоритма построения линий уровня;

– step – расстояние между двумя соседними линиями уровня;

– previous – вектор для хранения значений углов, на которых располагаются узлы, для предыдущей линии уровня;

– mathPrevious – вектор для вычисления значений углов для предыдущей линии уровня;

– halfPrevious – вектор для хранения значений углов биссектрис между двумя соседними парами предыдущей линии уровня;

– current – вектор для хранения значений углов для текущей линии уровня.

3.2 Реализация алгоритма расположения линий уровня

Ниже приведен код, согласно которому происходит расстановка линий уровня, также происходит высчитывание угла и шага:

power = pow(count, 2);

m = length/power;

xPrevious = x;

x = m*n;

t++;

n = pow(t, 2);

step = (x - m*pow(t - 2, 2));

angle = acos((2*pow(x, 2) - pow(step, 2))/(2*pow(x, 2)));

Согласно алгоритму, описанному во второй главе, сначала высчитывается переменная power, которая равна количеству линий уровня, возведенному в квадрат. Далее радиус исследуемой области делится на полученную величину. Далее находится x и высчитывается шаг.

Чтобы найти переменную angle использовалась теорема косинусов. Теорема косинусов звучит следующим образом [33]: для плоского треугольника, у которого стороны a, b, c и угол , который противолежит стороне a, справедливо высказывание: квадрат стороны треугольника равняется сумме квадратов двух других сторон минус удвоенное произведение этих сторон на косинус угла между ними:

.

Рассмотрим рисунок 29.

Рисунок 29 – Нахождение стороны a

Здесь b=c=x, и необходимо найти угол . Поэтому согласно теореме косинусов, чтобы найти этот угол необходимо найти арккосинус угла , что и происходит в последней строке кода.

Чтобы удостовериться в том, что код действительно работает, проверим чему будут равны значения переменных, при радиусе исследуемой области 100 и 200 и при двух линиях уровня (таблица 4):

Таблица 4 – Значения переменных

3.3 Вычисление значений углов

Вычисление значений углов и добавление узлов описано во втором цикле. Код цикла приведен ниже:

for(double h = 0; h > arc; h -= angle){

if (h == arc) break;

if(fabs(angle) >= fabs(arc)){

angle = fabs(arc);

current.push_back(h);

current.push_back(arc);

mathPrevious.push_back(arc/2);

}

else if(fabs(angle) <= fabs(arc) && fabs(arc) <= fabs(2*angle)){

if(nn == 0){

angle = fabs(arc/2);

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

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