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

 

Содержание

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

1.1 Постановка задачи. Вариант 30.

1.1.1 Программа на языке F#:

1.1.2 Программа на языке LISP:

1.2 Входные данные

1.3 Выходные данные

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

2.1 Чтение данных из файла

2.2 Идентификация фигуры

2.2.1 Поиск первой точки фигуры

2.2.2 Захват фигуры

2.2.3 Поиск треугольников

2.2.4 Алгоритм поиска треугольника

2.2.5 Проверка замкнутости фигуры

2.2.6 Проверка принадлежности точки отрезку

2.2.7 Поиск наиболее отдаленной от отрезка точки

2.3 Построение измененного треугольника

2.4Вывод результата работы программы

2.4.1 Вывод обработанного изображения

2.4.2 Вывод информации о распознанных фигурах

2.5Применение макросов в программе

2.6 Блок-схема программы

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

Заключение

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

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

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

·Microsoft Visual Studio 2008.

·FSharp.

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

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

.1 Постановка задачи. Вариант 30

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

Требуется написать две программы:

1.Программа на языке F#.

.Программа на языке Lisp.

.1.1 Программа на языке F#:

1.Имеет графический интерфейс.

.Отображает обрабатываемое изображение.

.Запускает батник, который выполняет следующие действия: .запускает txt2bmp.exe - осуществляет преобразование графического файла в текстовый файл;.запускает программу, написанную на языке LISP;.запускает txt2bmp.exe - осуществляет преобразование текстового файла в графический файл.

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

.1.2 Программа на языке LISP:

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

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

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

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

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

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

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

.При написании программы необходимо разработать собственные макросы.

.2 Входные данные

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

Рис.1 Пример корректных исходных данных.

Рис. 2 Пример Некорректных исходных данных.

Треугольник считается некорректным и игнорируется в случае, если:

.Треугольник не замкнут

.Треугольник пересекается с другой фигурой

.Сторона треугольника не идеально прямая.

.3 Выходные данные

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

Рис. 3 Пример результата работы программы.

треугольник программа преобразование

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

2.1 Чтение данных из файла

Сначала преобразуем графический файл в текстовый, используя утилиту txt2bmp. В результате получает текстовый файл «out.txt» заполненный нулями и единицами. 0 - цвет пикселя изображения белый, 1 - цвет пикселя чёрный.

Текстовый файл считываем в список. Каждый элемент списка - строка нулей и единиц считанная из текстового файла.

Рис.1. Хранение изображения в памяти.

.2 Идентификация фигуры

.2.1 Поиск первой точки фигуры

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

Рис.2. Обход матрицы изображения. Поиск первой точки.

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

.2.2 Захват фигуры

Координаты первой единичной точки передаем в функцию захвата фигуры.

Принцип работы функции захвата фигуры:

.получаем список координат соседних ненулевых точек для данной точки.

.Сохраняем координаты найденной точки в списке точек фигуры и заменяем его значение на 0.

.Повторяем пункты 1 и 2 для всех точек из списка, полученного в пункте 1

.Фигура считается обнаруженной, если все соседние точки равны нулю.

Рис. 3. Порядок обхода соседних точек точки .

Рис.4. Начало захвата фигуры.

Рис. 5. Завершение захвата фигуры

Списки координат точек фигур сохраняем в списке фигур. Поиск фигур заканчивается, когда доходим до нижней правой точки.

2.2.3 Поиск треугольников

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

Рис. 6. Общие положения треугольников на изображении.

.2.4 Алгоритм поиска треугольника

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

.Выделяем четыре крайние точки, переходим в пункт 3.

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

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

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

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

.Выделяем левую и правую точки, переходим в пункт 8

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

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

.2.5 Проверка замкнутости фигуры

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

Рис. 7. Проверка замкнутости.

На левой стороне Рисунка №7 у каждой точки есть как минимум 2 соседние точки с единичным значением - фигура замкнута. На правой части Рисунка №7 точка выделенная красным кружком имеет только одну единичную соседнюю точку - фигура не замкнута.

2.2.6 Проверка принадлежности точки отрезку

1.Если координаты всех точек по совпадают, то возвращаем иначе - переходим в пункт 2.

.Если координаты всех точек по совпадают, то возвращаем TRUE, иначе - переходим в пункт 3.

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

.Проверяем равенство уравнения:

(1)

- координаты точки, начало и конец отрезка.

Если равенство выполняется, то точка принадлежит отрезку - возвращаем , иначе - .

.2.7 Поиск наиболее отдаленной от отрезка точки

Чтобы вычислит расстояние от точки до отрезка, воспользуемся следующей формулой:

(2)

Рис. 8. Вычисление расстояния от точки до отрезка.

Расстоянием от точки до отрезка считается длинна перпендикуляра, опущенного из заданной точки на отрезок.

.3 Построение измененного треугольника

1.Находим середины сторон треугольника по формуле:

(3)

(4)

- координаты точки, начало и конец отрезка.

Переходим в пункт 2.

2.Соединяем вычисленные точки отрезками - в цикле вычисляем координаты всех точек отрезка по формуле:

(5)

(6)

координаты вычисленной точки.

координата начала отрезка.

длинна проекции отрезка на ось

длинна проекции отрезка на ось

2.4Вывод результата работы программы

.4.1 Вывод обработанного изображения

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

.4.2 Вывод информации о распознанных фигурах

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

Рис. 9. Выделение границ фигуры.

2.5Применение макросов в программе

Мáкрос - программный объект, который во время вычисления заменяется на новый объект, создаваемый определением макроса на основе его аргументов, затем выражается обычным образом.

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

(defmacro get-shades(checker)

`(dolist (points shades)

(setq triangles (append triangles (list (,checker points))))

)

)

(defun get-all-triangles ()

(get-shades check-triangle)

)

2.6 Блок-схема программы

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

При запуске программа загружает в левое верхнее окошко файл с изображением «image.bmp».

Рис. 10. Окно программы при запуске.

Если при запуске программы файл с изображением не найден, то срабатывает исключение и выводится соответствующее сообщение об ошибке «Изображение с названием Image.png не найдено»

Рис. 11. Ошибка при запуске программы.

При попытке запуска обработки изображения без открытого файла «Image.png» так же выводится сообщение об ошибке «Ошибка: изображение не открыто»

Рис. 12. Запуск программы без входного файла.

Для того, чтобы начать обработку изображения, надо нажать кнопку «Запуск». Программа запустит bat-файл, обработает изображение, выведет информацию о найденных фигурах в нижней части окна и загрузит обработанное изображение в верхний правый угол окна программы.

Рис. 13. Результат работы программы.

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

Рис. 14. Запуск программы с некорректными входными данными.

Программа может работать в двух режимах:

.Отображение искомых треугольников вместе с измененными.

.Отображение только измененных треугольников.

Рис. 15. Работа программы в режиме 1.

Кнопка «Об авторе» выводит информацию об авторе программы и постановку задачи.

Рис. 16. Информация об авторе.

Кнопка «Выход» завершает работу программы.

Заключение

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

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

·Microsoft Visual Studio 2010.

·FSharp.

·clisp.exe

·txt2bmp.exe

·Notepad++

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

1.F Sharp, URL: #"justify">2.Первое знакомство с F#, URL: #"justify">3.Windows Form Application in F#, URL: #"justify">4.Осваиваем F#: построение красочного множества Мандельброта с навигацией и интеграция с C#, URL: #"justify">.Преимущества Common Lisp, URL: #"justify">.Visual F#, URL: http://msdn.microsoft.com/ru-ru/library/dd233154.aspx

Содержание 1.Техническое задание 1.1 Постановка задачи. Вариант 30. 1.1.1 Программа на языке F#: 1.1.2 Программа на языке LISP: 1.2 Входные

Больше работ по теме: