">
Информатика Программирование
Информация о работе

Тема: Функциональное илогическое программирование

Описание: Руководство программиста. Общее описание алгоритма. Поиск фигур. Распознавание фигур. Метод их рисования. Округление. Проверка на существование ячеек и их значений, на совпадение желаемого символа и значения . Способ сортировки. Поведения программы при некорректных ситуациях.
Предмет: Информатика.
Дисциплина: Программирование.
Тип: Курсовая работа
Дата: 27.08.2012 г.
Язык: Русский
Скачиваний: 12
Поднять уникальность

Похожие работы:

Пояснительная записка к Курсовой работе

по дисциплине

«Функциональное и логическое программирование»

2012

Содержание

Содержание2

1.Техническое задание3

2.Руководство программиста5

3. Руководство пользователя11

Заключение15

Список использованной литературы16

Техническое задание

Дана рабочая плоскость (представленная в виде стандартного файла Windows DIB), содержащая некоторые непересекающиеся геометрические фигуры (круг, квадрат, треугольник и т.п). Необходимо идентифицировать указанные в индивидуальном задании фигуры, определить их положение, размер, проанализировать, отсортировать и преобразовать в фигуры другого вида. Считаем, что толщина линий контура геометрических фигур равна единице. Для выполнения работы использовать следующие средства:

clisp.exe или любое другое инструментальное средство языка Lisp.

txt2bmp.exe – осуществляет преобразование файлов форматов bmp, png в текстовый файл и наоборот. Можно использовать другие исполняемые программы.

Требуется написать программу на языке Lisp, которая:

Считывает текстовый файл в память.

Идентифицирует фигуры.

Преобразует фигуры.

Выводит на консоль текстовую информацию (какие фигуры распознаны, преобразованы с указанием координат и размеров).

.bat-файл выполняет следующие действия:

Запускает txt2bmp.exe – осуществляет преобразование графического файла в текстовый файл.

Запускает программу, написанную на языке LISP.

Запускает txt2bmp.exe – осуществляет преобразование текстового файла в графический файл.

Кроме этого необходимо выполнить следующие пункты:

Программа должна корректно обрабатывать нештатные ситуации

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

Вариант 15

На указанной плоскости идентифицировать 4 треугольника и преобразовать их в окружности с центром в одной из вершин треугольника и радиусом, равным половине высоты треугольника, проведенной из выбранной вершины. Самый левый треугольник преобразовать подобным образом в эллипс, большая полуось соответствует высоте треугольника, а малая полуось равна по длине половине большой полуоси.

Руководство программиста

Общее описание алгоритма

Читается файл и заносится в массив

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

Находится первая точка фигуры

Находятся три точки фигуры

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

Если фигура треугольник, то рассчитывается его радиус, равный половине его высоты к нижнему основанию.

Выводится сообщение о вершинах треугольника и номер преобразуемого треугольника

Если фигура первый треугольник, то рисуется эллипс из верхней точки с радиусами равными высоте треугольника и рассчитанному радиусу.

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

Выводится сообщение об успешном преобразовании

Счетчик треугольников увеличивается на единицу

Если счетчик в цикле стал равен четырем, то производится выход из цикла

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

Чтение из массива в файл

Алгоритм поиска фигур

Из текстового файла считываются символы в двоичный массив. Далее массив начинает считаться сверху вниз, что позволяет определить левый треугольник первым. Находится точка – она будет начальной точкой. С помощью функции find_tgl рекурсивно обходится найденная фигура, просматривая 9 вариантов развития событий: 8 различных направлений обхода и не нахождение следующей точки – возвращается на один шаг и рассматривает продолжает просматривать непройденные ячейки. Значения ячеек в массиве, которые равны #1, заменяются на значение #2. Тем самым программа помечает эту фигуру как пройденную.

Алгоритм распознавания фигур

От этой начальной точки находится при помощи функции points2 самая верхняя вершина (при прохождении фигуры вверх-вправо, т.к. считается, что нормальный треугольник имеет верхнюю точку, находящуюся относительно координат Х в промежутке между координатами нижних точек). От верхней точки находится последовательно самая правая-нижняя точка (направление вправо-вниз, фунция points3) и левая нижняя точка (направление влево-вниз, функция points1). Далее проверяется, есть ли прямые линии между этими точками (фунция checkLine). Частный случай, когда за треугольник может приниматься отрезок. От этого избавляемся с помощью вычисления высоты с помощью функции hight_tr – она не должна быть меньше единицы.

Функция checkLine проверяет правильность линий с помощью алгоритма Брезенхема и количество ошибок может быть не больше пяти.

Отрезок рисуется между двумя точками — (x0,y0) и (x1,y1), где в этих парах указаны колонка и строка, соответственно, номера которых растут вправо и вниз. Сначала предполагатся, что линия идёт вниз и вправо, причём горизонтальное расстояние x1 ? x0 превосходит вертикальное y1 ? y0, т.е. наклон линии от горизонтали — менее 45°. Цельсостоит в том, чтобы для каждой колонки x между x0 и x1, определить, какая строка y ближе всего к линии, и нарисовать точку (x,y).

Метод рисования фигур

Чтобы нарисовать эллипс, необходимо иметь радиус, который вычисляется из высоты треугольника. Высота рассчитывается из двух формул площади треугольников S= ? ah и S = (p(p-a)(p-b)(p-c))? где p = (a+b+c)/2. Длины сторон находятся из формулы нахождения гипотенузы, где катетами выступают разности по Х и по Y точек треугольника

Для рисования эллипса использовалась система уравнений

x = x0 + Rxcos a

y = y0 + Rysin a,

где а-параметр менялся от 0 до 2? с шагом ?/360.

Если ячейка с округленными координатами (x, y) существует и ее значение равно #, т.е. она не заполнена и таким образом не будет мешать распознаванию других фигур, то значение этой ячейки меняется на #3.

(defun print_ellipse (rx ry p1)

(

progn

(setq k 0)

(setq step_el (/ pi 360))

(loop

(cond ( (or (equal k (* 2 pi)) (> k (* 2 pi))) (return)))

(setq x1 (round-up (+ (car p1) (* rx (cos k)))))

(setq y1 (round-up (+ (cadr p1) (* ry (sin k)))))

(if (and (exist_cell x1 y1) (cell_number data x1 y1 #))

(setf (aref data x1 y1) g_ellipse)

)

(setq k (+ k step_el))

)

))

Таким образом, после всех манипуляций с массивом значения ячеек равные # равносильны незаполненной области, равные #1 принадлежат фигурам, до которых «не дошел» алгоритм – так бывает, если фигур треугольников больше четырех. Значения ячеек равные #3 принадлежат эллипсам, а равные #4 – треугольникам, которые прошли преобразование эллипсов.

(setq g_null #) – пустые клетки

(setq g_start #1) – фигуры, не прошедшие какую-либо обработку

(setq g_checking #2) – прошедшие обработку фигуры (любые)

(setq g_ellipse #3) – эллипс

(setq g_triangles #4) – треугольники, преобразованные в эллипсы

Округление

Так как стандартная функция округления в lisp округляет только в большую сторону, была написана следующая функция, которая округляет в зависимости от остатка разности округленного значения и самого числа, которое требуется округлить

(defun round-up (m)

(

progn

(setq r (ceiling m))

(setq d (- r m))

(if (> 0.5 d) r (- r 1))

))

Проверка на существование ячеек и их значений

Одна из самых необходимых функций является проверка на существование ячейки (например при рисовании фигуры или пограничного состояния ячейки). Ячейка существует только в указанных границах диапазона, определяемого глобальными переменными g_width и g_height

(defun exist_cell (i j)

(

if (or (or (> i (- g_width 1))(> j (- g_height 1))) (or (< i 0) (< j 0)))

nil T ; nil - если не существует

))

Проверка на совпадение желаемого символа и значения в ячейке

(defun cell_number (data i j ch)

(

equal ch (aref data i j); T - значение заданной ячейки совпадает с желаемым

))

Способ сортировки

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

Алгоритмы, описывающие поведения программы при некорректных ситуациях

Если алгоритм поиска не находит заданного количества треугольников, то выводится сообщение “not enough triangles”.

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

Если треугольник не замкнутый, то считается, что это не треугольник и программа переходит к следующей фигуре, аналогично с другими фигурами или треугольниками с искажениями. Это можно определить, с помощью функции checkLine, которая проверяет линию между крайними точками.

Блок-схема алгоритма распознавания и преобразования треугольника

Алгоритмом уже найдена первая точка фигуры, она будет не обязательно самая левая-нижняя. И фигура помечена как пройденная – заполнение #2 ячеек фигуры

3. Руководство пользователя

Изображения фигур до работы программы

Корректные ситуации



Некорректные ситуации



Примеры работы программы

Пример 1. Начальное изображение подается на вход (некорректная ситуация)



Преобразуется в



Вывод в консоли:



Пример 2. Начальное изображение подается на вход (корректная ситуация)



Преобразуется в



Вывод в консоли:



Пример 3. Начальное изображение подается на вход (корректная ситуация)



Преобразуется в



Вывод в консоли:



Заключение

Была написана программа, которая идентифицирует 4 треугольника и преобразовывает каждый из них в эллипсы. При чем самый левый треугольник преобразуется в эллипс с радиусами равными высоте и половине высоты треугольника, а остальные в окружности с радиусом равным половине их высоты. Высотой считается линия проведенная из верхней (первой) вершины треугольника перпендикулярно основанию (сторона 2-3).

Алгоритм был реализован на языке программирования Lisp. Данная курсовая работа позволила применить на практике знания, которые были получены на курсе “Функциональное и логическое программирование” и изучить алгоритмы распознавания и преобразования фигур.

Список использованной литературы

http://ru.wikipedia.org/wiki/Эллипс

http://ru.wikipedia.org/wiki/Алгоритм_Брезенхема

Материалы лекции по дисциплине «Функциональное и логическое программирование» (http://wiki.margtu.ru/index.php?wakka=HomePage/20112012/3kurs/FILP/Lections&v=urx)