ПетрГУ | О кафедре | Проекты по разработке ПО | Достижения | Исследования | НФИ
Сотрудники | Студенты | Выпускники | Учебный процесс | Курсовые работы
Архив новостей | Контактная информация | Поиск
| Требование | M1.1 | M1.2 | M1.3 | M1.4 | M1.5 | M1.6 | M2 | M2.1 | M2.2 | M2.3 | M2.4 | M3 | M3.1 | M3.2 | M4.1 | M5.1 | M5.2 | M5.3 | M5.4 |
| Т1 | x | x | x | x | x | - | - | x | - | - | x | x | - | - | - | - | - | - | x |
| T2 | x | x | x | x | - | - | x | x | - | x | x | x | - | - | x | - | x | - | x |
| T3 | x | x | x | x | - | - | - | x | x | x | x | x | x | - | x | - | - | x | x |
| T4 | - | - | - | - | - | x | - | - | - | x | x | x | - | - | x | - | - | - | x |
| T5 | - | - | - | - | - | - | - | - | - | - | - | - | - | x | - | x | - | - | - |
В начале работает подсистема обработки ошибок. Она осуществляет проверку всех ошибок, а также запуск всех остальных подсистем. В случае возникновения ошибок, подсистема выдаст соответствующее сообщение.
Затем работает подсистема ввода и сохранения результатов. Пользователь выбирает тип ввода координат (ввод из файла или задавать их мышью), после чего вводит координаты. Для этого используются модули ввода данных.
В случае если данные введены из файла, начинает работу подсистема обработки ошибок. Данная подсистема отслеживает, правильно ли заданы начальные данные (координаты) в файле. После этого, либо выдаётся сообщение об ошибке (в случае обнаружения ошибки) и пользователю предлагается повторить попытку ввода данных, либо система продолжает работу.
После этого начинает работу подсистема «основной алгоритм». Она обрабатывает входные данные и находит точки поворота.
По окончании работы подсистемы «основной алгоритм» начинает работу подсистема «ввода и сохранения результата», которая в свою очередь передает данные подсистеме "графический интерфейс". Она отображает на экране результаты работы, формируя в системе координат (x,y) результат полигональной аппроксимации.
Если пользователь хочет сохранить входные данные или результат, то запускается подсистема ввода и сохранения результатов.
Подсистема "Основной алгоритм": Данная подсистема состоит из одного модуля, который и реализует сам алгоритм. Данный модуль состоит из четырех функций: 1) main - главная функция, из которой вызываются все остальные 2) get - функция считывания координат следующей введенной пользователем точки. Входными параметрами здесь являются переменные для записис координат следующей считываемой точки 3) rotate - функция подсчета координат после поворота на заданный угол FI. Входными параметрами здесь являются: координаты рассматриваемой точки и переменные для записи координат после поворота на заданный угол FI 4) is_way_point - функция проверки того, является ли рассматриваемая точка - точкой поворота. Входными параметрами здесь являются: координаты рассматриваемой точки и указатель на структуру точек. Выходным параметром является переменная, значение которой = 0 или 1 (1 - точка является точкой поворота, 0 - не является) Функция get: функция считывания координат следующей точки из файла Входные данные: переменные для записи координат следующей считываемой точки Выходные данные: значение 0 или (-1) Описание: данная функция считывает координаты следующей точки из файла и записывает их в переменные, которые являются входными параметрами. Если после текущего считывания координат в файле больше не остается коррдинат для дальнейшего считывания, то возвращаем в вызываемую программу значение (-1), иначе значение 0 Результат: записывает координаты следующей точки в переданные переменые Функция rotate: функция подсчета координат после поворота на заданный угол FI Входные данные: координаты рассматриваемой точки и переменные для записи координат после поворота Выходные данные: нет Описание: данная функция высчитывает координаты точек, которые получатся, если исходные повернуть на заданный угол FI (FI=PI/4). Новые координаты вычисляются по формулам: *x2 = *x1 * (float)cos (FI) + *y1 * (float)sin (FI) *y2 = *y1 * (float)cos (FI) - *x1 * (float)sin (FI) Результат:высчитывает координаты после поворота на заданный угол FI Функция is_way_point: функция проверки того, является ли рассматриваемая точка - точкой поворота Входные данные: координаты текущей и следующей точек Выходные данные: переменная, значение которой = 0 или 1 (1 - точка является точкой поворота, 0 - не является) Описание: Изначально значение переменной для определения того, является ли точка - точкой поворота равно 0. Далее смотрим, если разность по координате x между текущей и следующей точками >=0, то приращение по координате полагаем равным 1-це, иначе равным (-1)-це. Аналогично и для координаты y. Далее смотрим, если поменялось направление, то значение переменной для определения того, является ли точка полагаем равным 1-це. Результат: выясняет является ли следующая точка - точкой поворота Функция main: главная функция, из которой вызываются все остальные Описание: Сначала данная функция осуществляет проверку правильности запуска алгоритма (количество аргументов в командной строке должно бытьравным 3-м: название exe - файла, входной и выходной файлы). В случае неправильного запуска выдается соответствующее сообщение и алгоритм завершает свою работу. Если файлов, где должны хранится координаты и куда они будут записываться координаты после работы алгоритма, не существует то алгоритм так же завершает свою работу. Далее, сначала считываем 1-ю точку из файла, если она есть (иначе алгоритм завершает свою работу). Далее вызываем функция подсчета координат этой точки после поворота на заданный угол FI. Далее пока есть в файле еще не считанные координаты вызываем функцию считывания следующей точки из файла. Для каждой такой следующей считанной точки проверяем условие: если расстояние между текущей и следующей точками меньше eps * sqrt (2) (значение eps =1 ) (т.е. не вышли за полосу ширины eps * sqrt (2), т.е. угол больше, чем PI/4), то продолжаем этот процесс далее. Как только условие нарушаетя, т.е. вышли за полосу, то вызываем функция подсчета координат после поворота на заданный угол FI последней считанной точки. Далее с помощью вызова функции проверки того, является ли рассматриваемая точка - точкой поворота, смотрим является ли какая-нибудь из 2-х: последняя считанная точка или она же, но повернутая на угол FI - точкой поворота. Если да, то выводим последнюю считанную точку в выходной файл.
генерации случайных траекторий
Данный модуль генерирует случайную траекторию по результату задачи полигональной аппроксимации.
Состоит из функций:
• Функция gen_trajectory - управляющая функция подсистемы
• Функция division_piece - делит отрезок между двумя точками поворота на случайное число частей
• Функция deviation_point - генегирует случайное отклонение в заданной точке
• Функция check_appr - проверка аппроксимации
Функция gen_trajectory
-данная функция из результата полигональной аппроксимации генерирует случайную траекторию, т.е. подряд берет из массива
input парами точки делит на случайное количество частей и каждую точку отклоняет на случайное число не большее ширине
дороги.
Начало
masp - массив содержащий координаты точек поворота output и первую и последнюю точки input
kl - количество точек в массиве output
kol_points=0; (количество точек сгенерированной части траектории)
заполняем массив masp
masp[0][1]=input[1][1]; masp[0][2]=input[1][2];
цикл for (i=1;i<=kl;i++){ masp[i][1]=output[i][1]; masp[i][2]=output[i][2];}
masp[kl+1][1]=input[n][1]; masp[kl+1][2]=input[n][2]; (первая и последняя точки массива input записываются первой и
последней)
r_t - переменная, содержащее значение второй рассматриваемой точки, первоначально равно 0
цикл while (пока r_t!=kl)
{
увеличиваем r_t на 1 (т.е. первоначально рассматриваем 1 и 2 точки)
запуск функции division_piece(с входными параметрами (r_t-1) и r_t); (из данной функции запускается функция отклонения,
поэтому после завершения функции division_piece в переменной kol_points будет хранится число точек уже сгенерированной
части траектории и их координаты будут записаны в массив gen_point)
}
увеличиваем kol_points на 1;
записываем последнюю точку из массива masp в результирующий массив gen_point;
запуск функции check_appr; (полученную случайную траекторию прогоняет через алгоритм полигональной аппроксимации и
проверяет результат)
Конец функции.
Функция division_piece (int t1,t2);
-данная функция делит отрезок между точками t1 и t2 (номера точек из массива input) на случайное число частей и
вычисляет координаты каждой точки на прямой.
Начало
в переменные x1,y1 записываем координаты первой точки поворота и в x2,y2 соответственно второй;
kol_part - переменная количества частей
kol_part=random(20); (определяем случайным образом на какое количество частей будем делить отрезок)
kol_points++;
gen_point[kol_point][1]=masp[t1][1] (записываем первую точку в результирующий массив, потому что она отклонятся не будет)
цикл for(i=1;i<=kol_part;i++)
{
a[i,1]=i*(x2-x1)/kol_part; (вычисляем координаты новых точек на отрезке)
a[i,2]=i*(y2-y1)/kol_part;
запуск функции deviation_point (с параметрами a[i,1],a[i,2] и t1,t2); (функция посчитает случайное отклонение точки от
идеальной траектории и запишет в массив gen_point под соответствующими номерами, параметры t1, t2 ,будут необходимы в
дальнейших расчетах)
}
Конец функции.
Функция deviation_point (float tx,ty , int t1,t2);
-данная функция случайным образом определяет отклонение определенной точки (tx,ty) от идеальной траектории и запоминает
полученную точку в результирующем массиве gen_point
Начало
определяем угловой коэфицент k прямой проходящий через точки t1 и t2, при этом условно определим сдвиг координатной сетки,
т.о. чтобы начало координат совпадало с первой точкой;
k=(y2-y1)/(x2-x1);
Теперь легко найти угловой коэфицент перпендикуляра
kp=-1/k;
Далее генерируем длину отклонения
dl=random(10); Если (dl!=0) dl=1/dl; иначе dl=0;
ix,iy -искомые координаты точки, с учетом отклонения по перпендикуляру
ix=tx+dl/sqrt(1+sqr(kp)); (выведенная формула вычисления координаты ix)
b=ty+kp*tx; (определяем точное уравнение перпендикулярной прямой)
iy=kp*ix+b; (вычисляем из уравнения iy)
Т.к. условно координатная сетка была сдвинута к t1 точке, вернем ее на прежнее место
ix=ix+masp[t1][1];
iy=iy+masp[t1][2];( добавляем координаты t1 точки поворота к координатам)
увеличиваем kol_points на 1;
записываем полученную точку в массив gen_point под номером kol_points;
Конец функции;
Функция check_appr
-данная функция полученный случайным образом набор координат gen_point, количества kol_points прогоняет через алгоритм
полигональной аппроксимации и сравнивает результат с массивом output
Начало
запуск подсистемы расчета полигональной аппроксимации и получение результата в массив result;
check-переменная логического типа первоначально равна true
определяем количество элементов в массиве result;
сравниваем количество элементов в массивах output и result, если несовпадают то check=false;
если (check=true)
{
сравниваем покоординатно два массива output и result;
если какая-нибудь координата не совпадает, то check=false;
}
если (check=true) то вывод сообщения, что результат полигональной аппроксимации начального набора данных совпадает с
результатом аппроксимации случайно сгенерированной траектории по той же идеальной
иначе сообщение о несовпадении
Конец функции.
Алгоритм вычисления разности между "идеальной траекторией"
и результатами полигональной аппроксимации по мерам максимума
расстояния.
Необходимые структуры данных:
struct POINT {
float x; // coordinates
float y;
}
Данная структура необходима для хранения координат.
Входные данные:
POINT input[] - массив с исходными координатамию
POINT output[] - массив с результатами работы алгоритма.
M - количество точек поворота
Алгоритм:
k=1
max=-1
for(i=1;iменьшеM;i++)
{
z1=output[i]
z2=output[i+1]
Найти уравнение прямой, проходяшей через точки z1, z2
while(input[k]!=z2)
{
A=расстояние от точки input[k] до прямой
max=Max(max,A)
k++
}
}
Подсистема "Обработка ошибок":
Функция Parse_Error:функция обработки всех возможных ошибок
Входные параметры: массив кодов ошибок
Выходные параметры: значение логического типа: истина, если код ошибки свидетельствует о её отсутствии или ошибку удалось
устранить, ложь - произошла ошибка и её не удалось устранить
Описание: данная функция будет искать в массиве не нулевые элементы (коды произошедших ошибок). Для каждого такого не
нулевого элемента (кода ошибки) эта функциябудет выводить сообщение о типе ошибке, о месте ее возникновения. Те типы ошибок, которые можно будет устранить - будут устраняться и данная функция будет выдавать сообщение о том, что ошибка устранена. В случае невозможности устранения ошибки функция будет выдавать сообщение о том, что ошибка не может быть устранена.
Результат: выдает сообщение о месте обнаружения ошибки, исправляет ее, если это возможно и выдает сообщение о том,
удалось исправить ошибку или нет.
Parse_Error(Массив кодов ошибок):
Начало функции
Цикл по длине массива с кодами ошибок
Смотрим очередной элемент массива
Switch очередной элемент массива
1 : Вывод сообщения о месте происхождения ошибки и о ее типе
Если (ошибку можно устранить) то
Начало
Устраняем ошибку
Вывод сообщения о том, что ошибка устранена
Переменная логического типа:= истина
Конец
Иначе
Начало
Вывод сообщения о том, что ошибку нельзя устранить
Переменная логического типа:= ложь
Конец
2 : Вывод сообщения о месте происхождения ошибки и о ее типе
Если (ошибку можно устранить) то
Начало
Устраняем ошибку
Вывод сообщения о том, что ошибка устранена
Переменная логического типа:= истина
Конец
Иначе
Начало
Вывод сообщения о том, что ошибку нельзя устранить
Переменная логического типа:= ложь
Конец
...
n : Вывод сообщения о месте происхождения ошибки и о ее типе
Если (ошибку можно устранить) то
Начало
Устраняем ошибку
Вывод сообщения о том, что ошибка устранена
Переменная логического типа:= истина
Конец
Иначе
Начало
Вывод сообщения о том, что ошибку нельзя устранить
Переменная логического типа:= ложь
Конец
Конец цикла
Конец функции
Модуль управления подсистемами
Описание модуля:
Данный модуль включает в себя две функции: функцию инициализации всех подсистем Init_All_Subsystem, которая
запускается в начале работы системы, и функцию завершения подсистем - Close_All_Subsystem.
function Init_All_Subsystem (){
Проверить, существуют ли все необходимые файлы для работы системы.
Если нет, то сообщить об ошибке.
Попытаться создать пустой файл в директории для хранения временных файлов.
Если не удалось, то сообщить об ошибке.
Удалить этот файл.
Если не удалось, то сообщить об ошибке.
Проверить, установлена ли поддержка Java-апплетов у клиента.
Если нет, то сообщить об ошибке.
Если была хотя бы одна ошибка, выйти из программы.
Открыть начальную форму программы.
}
function Close_All_Subsystem (){
Если пользователь не забрал файлы с результатами с сервера.
Предупредить и предложить их забрать.
Завершить сессию пользователя, если она не была завершена.
Удалить все временные файлы.
}
Подсистема "Графический интерфейс":
Данная подсистема состоит из 1 модуля "Графический интерфейс". Данный модуль включает в себя 5 функций:
1) Mouse_click - функция обработки щелчка мыши
2) Mouse_move - функция обработки движения мыши
3) Draw_all - функция прорисовки всех точек (включая точки поворота) и траекторий
4) Clean_screen - функция очистки экрана
5) Draw_grid - функция прорисовки сетки и серого экрана
Описание:
Процедура mouse_click:
Входные параметры: нет
Запуск данной функции происходит при случае ввода координат в интерактивном режиме.
После нажатия мышки по полю функция автоматически запоминает координату (x,y)
Увеличиваем количество введенных точек n на 1 (n++);
Запуска функции draw_all с параметром n, которая в свою очередь перерисовывает заново все точки из массива input
и прочерчивает прямые между ними;
Координату (x,y) записываем в массив input под номером n (input[n][1]=x, input[n][2]=y);
Выход из процедуры mouse_click.
Процедура mouse_move:
Функция запускается при нахождении мыши на графическом поле.
При нахождении мыши на поле функция mouse_move считывает координату (x,y) в данный момент времени;
Прописывает ее ниже графической сетки;
Выход из процедуры mouse_move.
Функция Draw_all: функция прорисовки всех точек (включая точки поворота) и траекторий
Входные данные: нет
Выходные данные: нет
Описание: данная функция сначала вызывает функцию прорисовки сетки. Затем просматривает все элементы массива input.
Если обе координаты текущей точки не равны 0, то прорисовываем эту точку и берем следующую точку из массива. Если
обе ее координаты не равны 0, то так же прорисовываем ее и соединяем эту точку с предыдущей
точкой линией. Этот процесс продолжаем до тех пор, пока не будут просмотрены все ненулевые
координаты массива input. Аналогично поступаем и с массивом output, только точки и линии прорисовываем
другим цветом и другим размером.
Результат: изображает на экране исходные координаты, точки поворота и траектории(идеальную и результат полигональной
аппроксимации)
Функция Clean_screen: функция очистки экрана
Входные данные: нет
Выходные данные: нет
Описание: данная функция сначала обнуляет массивы input и output, а затем вызывает функцию прорисовки серого экрана с сеткой
Результат: изображает серый экран с сеткой и обнуляет все массивы
Функция Draw_grid: функция прорисовки сетки и серого экрана
Входные данные: нет
Выходные данные: нет
Описание: данная функция изображает серый экран и сетку поверх него
Результат: прорисовывает серый экран и сетку поврх него
Draw_all:
Начало функции
вызов Draw_grid
// рисуем результат полигональной аппроксимации
если координаты первой точки не пустые, то
начало
передавая координаты текущей точки, увеличенные на радиус изображаемой точки, рисуем точку(цвет синий).
запоминаем координаты начала линии в переменной xbegin:=input[1][1]
ybegin:=input[2][1]
конец
иначе
выход из функции.
если координаты второй точки не пустые, то
начало
передавая координаты текущей точки, увеличенные на радиус изображаемой точки, рисуем точку(цвет синий).
запоминаем координаты конца линии в переменной xend:=input[2][1]
yend:=input[2][2]
рисуем линию(цвет синий), координаты начала и конца которой соответственно равны (xbegin,ybegin) (xend,yend)
конец
иначе
выход из функции.
цикл по длине массива input(n)(i=3..n)
начало
если координаты текущей точки не пустые, то
начало
передавая координаты текущей точки, увеличенные на радиус изображаемой точки, рисуем точку.
запоминаем новые координаты для следующей линии
xbegin:=input[i-1][1]
ybegin:=input[i-1][1]
xend:=input[i][1]
yend:=input[i][2]
рисуем линию(цвет синий), координаты начала и конца которой соответственно равны (xbegin,ybegin) (xend,yend)
конец
иначе
выход из функции
конец
// рисуем идеальную траекторию
если координаты первой точки не пустые, то
начало
передавая координаты текущей точки, увеличенные на радиус изображаемой точки, рисуем точку(цвет красный).
запоминаем координаты начала линии в переменной xbegin:=output[1][1]
ybegin:=output[2][1]
конец
иначе
выход из функции.
если координаты второй точки не пустые, то
начало
передавая координаты текущей точки, увеличенные на радиус изображаемой точки, рисуем точку(цвет красный).
запоминаем координаты конца линии в переменной xend:=output[2][1]
yend:=output[2][2]
рисуем линию(цвет красный), координаты начала и конца которой соответственно равны (xbegin,ybegin) (xend,yend)
конец
иначе
выход из функции.
цикл по длине массива output(m)(i=3..m)
начало
если координаты текущей точки не пустые, то
начало
передавая координаты текущей точки, увеличенные на радиус изображаемой точки, рисуем точку(цвет красный).
запоминаем новые координаты для следующей линии
xbegin:=output[i-1][1]
ybegin:=output[i-1][1]
xend:=output[i][1]
yend:=output[i][2]
рисуем линию(цвет красный), координаты начала и конца которой соответственно равны (xbegin,ybegin) (xend,yend)
конец
иначе
выход из функции
конец
конец функции
Draw_grid:
Начало функции
прорисовка серого прямоугольника с заданной шириной и высотой
задаем ширину сетки
цикл по высоте экрана
прорисовка линии сетки с текущими координатами: (x,y)-начало линии,(x`,y`)- конец линии
увеличение координат y и y` на ширину сетки
конец цикла
цикл по длине экрана
прорисовка линии сетки с текущими координатами: (x,y)-начало линии,(x`,y`)- конец линии
увеличение координат x и x` на ширину сетки
конец цикла
Конец функции
Clean_screen:
Начало функции
цикл по длине массива input(n)(i=1..n)
если((input[1][i]<>0)и (input[2][i])<>0) то
начало
input[1][i]:=0
input[2][i]:=0
конец
цикл по длине массива output(m)(i=1..m)
если первая и вторая координата текущей точки не пустые, то
начало
опустошаем текущие координаты
конец
вызов функции Draw_grid
конец функции
Сохранение результата
Язык: PHP (save.php)
Сохранение результата Язык: PHP (save.php) Скрипт запускается при нажатии на кнопку `сохранить`. Осуществляет сохранение на клиентской машине сформированных в ходе работы (и хранящихся в данный момент на сервере) файлов *in и *out. Файл *in содержит начальные данных, файл *out содержит результат работы алгоритма (точки поворота). Описание: Имена файлов *in, *out задаются при загрузке на сервер с помощью инициализации сессии, таким образом, достигается уникальность имен для каждого пользователя. При нажатии на кнопку `сохранить` в переменную $down записывается имя файла, который необходимо загрузить с сервера (берется из сессии). Переменная $down_file содержит путь к файлу. Проверяем существует ли такой файл если, то в заголовке отправляется ссылка на загружаемый файл: Echo “META HTTP-EQUIV=’Refresh’ CONTENT=’0; URL=”.$down_file[$_GET[‘down’]].”’”; Иначе выдаем сообщение об ошибке. После загрузки файла разрушаем сессию: session_start(); unset($_SESSION['vars']); session_destroy(); // разрушаем сессию
Ввод данных из файла
Данный модуль реализует несколько функций:
1. Ввод данных (input.php)
Язык: PHP
Для того чтобы загрузить данные из файла пользователю необходимо нажать на кнопку `обзор`. При нажатии на данную кнопку открывается диалоговое окно, с помощью которого пользователь выбирает нужный файл, после чего происходит его загрузка на сервер (файл *in). Далее запускается скрипт (alggo.php) запускающий основной алгоритм.
2. Запуск основного алгоритма (alggo.php)
Язык: PHP
Данный скрипт запускает основной алгоритм, входными параметрами являются имя файла (*in). По окончании работы формируется новый файл (*out) содержащий результат работы алгоритма (точки поворота).
Ввод данных в интерактивном режиме
После того, как пользователь мышью задал координаты (или задал новую координату при интерактивном тестировании) эти координаты должны быть переданы на сервер, где находится основной алгоритм. Это происходит следующим образом: Пользователь нажимает кнопку «Вычислить». По нажатии на эту кнопку вызывается обработчик, который сначала формирует двумерный массив с координатами. После этого этот массив при помощи GET-запроса передаётся на сервер, где php-скрипт запускает основной алгоритм. По окончании работы алгоритма формируется файл с результатами. Представим это графически:
Модуль реализует несколько функций (вызывается при нажатии на кнопку `вычислить`):
1. Считывание координат (koord.java)
Язык: JAVA
Данная функция формирует двумерный массив (input[][]), содержащий координаты (x, y), введенные пользователем в интерактивном режиме. После нажатия на кнопку `вычислить` сформированный массив с помощью GET отправляется на сервер.
2. Формирование файла (formf.php)
Язык: PHP
Данный скрипт получает отправленный функцией koord.java массив input[][], и переписывает его в файл *in.
3. Запуск основного алгоритма (alggo.php) (описан выше).
4. Вызов `Отображение результата`
Отображение результата
Отображение результата Запускается при нажатии на кнопку `показать`. 1. Формирование массивов (massiv.php) Язык: PHP Скрипт берет сформированные файлы *in и *out и переписывает данные, хранящиеся в данных файлах в массивы input[] и output[]. Затем эти массивы передаются в подсистему `графический интерфейс`. Описание: Отправляем GET запрос на сервер: GET /~адрес/ HTTP/1.1 Host: cs.karelia.ru Получаем файлы *in и *out и обрабатываем их удаляя служебную информацию содержащуюся в заголовке. Данные из этих файлов заносятся в массивы input[] и output[]. Внутреннее устройство подсистемы и ее взаимодействие с другими подсистемами.
