Размещено на http://www.allbest.ru/

Министерство образования Республики Беларусь

Учреждение образования

«Белорусский государственный университет информатики и радиоэлектроники»

Кафедра интеллектуальных информационных технологий

Факультет информационных технологий и управления

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

по курсу: “Проектирование интеллектуальных систем и систем принятия решений”

НА ТЕМУ: Разработка программного макета лабораторного практикума по курсу ГИИС и КГ

Разработчик:

студент гр. 021703

Граков А.А.

Руководитель:

Самодумкин С.А.

МИНСК 2005



АННОТАЦИЯ

на курсовой проект «Разработка программного макета лабораторного практикума по курсу ГИИС и КГ» студента Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники» Гракова Алексея

Работа выполнена на 38 листах с пояснительной запиской на 28 листах; включает 4 раздела, 2 приложения, 5 рисунков и 5 литературных источников.

Темой работы является обучение студентов алгоритмам машинной графики. графика модуль оболочка полигон

В первом разделе проекта приведено описание алгоритмов машинной графики, а в частности построение выпуклой оболочки, построение триангуляции Делоне, построение звездчатого полигона.

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

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

Четвёртый раздел посвящён тестированию программы, приводятся примеры работы программы.



ВВЕДЕНИЕ

Цель курсового проекта:

Разработка программного макета лабораторного практикума по курсу «ГИИСиКГ».

Решаемые задачи:

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

Построение выпуклой оболочки.

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

Построение триангуляции Делоне

Диаграмма Воронова

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

Также следует реализовать теоретическую часть для каждого из вышеуказанных графических методов. Теоретическая часть должна быть представлена в качестве материалов к лекциям по курсу ГИИС.



1. АНАЛИТИЧЕСКИЙ ОБЗОР ЛИТЕРАТУРЫ

Машинная графика - это совокупность методов и средств для преобразования данных в графическую форму представления с помощью ЭВМ [1].

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

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

- синтез;

- анализ;

- обработка изображения.

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

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

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

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

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

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

Пиксель - наименьший элемент носителя изображения, которому можно индивидуально назначить цвет или степень яркости [4].

Построение выпуклой оболочки.

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

Один из способов построения выпуклой оболочки конечного набора точек на плоскости напоминает вычерчивание при помощи карандаша и линейки. Вначале выбирается точка a, принадлежащая S, заведомо являющаяся вершиной границы выпуклой оболочки. В качестве такой точки можно взять самую левую точку из набора S (если таких точек несколько, выбирается самая нижняя). Затем вертикальный луч поворачивается вокруг этой точки по направлению часовой стрелки до тех пор, пока он не будет проходить через точку b, принадлежащую S.Тогда отрезок ab будет ребром границы выпуклой оболочки. Для поиска следующего ребра будем продолжать вращение луча по часовой стрелке вокруг точки b до встречи со следующей точкой c Є S . Отрезок bc будет следующим ребром границы выпуклой оболочки.

Процесс повторяется до тех пор, пока снова не встретится точка a. Этот метод называется методом «заворачивания подарка».

Основным шагом алгоритма является отыскание точки, следующей за точкой, вокруг которой вращается луч. Для этого ищется самая первая точка, в направлении вращения луча или самая последняя в обратном направлении. Пусть имеется текущая точка D, являющаяся вершиной границы выпуклой оболочки. Анализируются все точки Pi, не вошедшие в выпуклую оболочку. Пусть предполагается, что точка P4 является следующей вершиной в границе выпуклой оболочки. Если это так, то все углы, образуемые вектором p и вектором qi должны быть отрицательными относительно вектора p. Если какой-то угол оказывается положительным, то вектор p заменяется на соответствующий вектор qi и процесс повторяется до тех пор, пока не найдётся положительных углов. На рисунке следующей вершиной границы выпуклой оболочки будет точка P1.

Для вычисления знака угла между двумя векторами можно воспользоваться выражением: a ? b ?

sin(?) = a b a b

где - угол между векторами a и b. При этом знак синуса соответствует знаку угла.

Рисунок 1.1 Вычисление угла

Временные затраты данного алгоритма равны O(hn) , где h - число вершин в границе искомой выпуклой области. Работа алгоритма проиллюстрирована ниже.

Триангуляция Делоне.

Триангуляция для конечного набора точек S является задачей триангуляции выпуклой оболочки CH(S), охватывающей все точки набора S. Отрезки прямых линий при триангуляции не могут пересекаться -- они могут только встречаться в общих точках, принадлежащих набору S. Поскольку отрезки прямых линий замыкают треугольники, мы будем считать их ребрами. На рис. 3 показаны два различных варианта триангуляции для одного и того же набора точек (временно проигнорируем окружности, проведенные на этих рисунках).

Для данного набора точек S мы можем видеть, что все точки из набора S могут быть подразделены на граничные точки -- те точки, которые лежат на границе выпуклой оболочки CH(S), и внутренние точки -- лежащие внутри выпуклой оболочки CH(S). Также можно классифицировать и ребра, полученные в результате триангуляции S, как ребра оболочки и внутренние ребра. К ребрам оболочки относятся ребра, расположенные вдоль границы выпуклой оболочки CH(S), а к внутренним ребрам -- все остальные ребра, образующие сеть треугольников внутри выпуклой оболочки. Отметим, что каждое ребро оболочки соединяет две соседние граничные точки, тогда как внутренние ребра могут соединять две точки любого типа. В частности, если внутреннее ребро соединяет две граничные точки, то оно является хордой выпуклой оболочки CH(S). Заметим также, что каждое ребро триангуляции является границей двух областей: каждое внутреннее ребро находится между двумя треугольниками, а каждое ребро оболочки -- между треугольником и бесконечной плоскостью.

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

Теорема о триангуляции набора точек. Предположим, что набор точек S содержит n>3 точек и не все из них коллинеарны. Кроме того, i точек из них являются внутренними (т. е. лежащими внутри выпуклой оболочки CH(S). Тогда при любом способе триангуляции набора S будет получено точно n + i - 2 треугольников.

Для доказательства теоремы рассмотрим сначала триангуляцию n-i граничных точек. Поскольку все они являются вершинами выпуклого полигона, то при такой триангуляции будет получено (n - i) - 2 треугольников. (В этом нетрудно удостовериться и, более того, можно показать, что любая триангуляция произвольного m-стороннего полигона - выпуклого или невыпуклого -- содержит m - 2 треугольника). Теперь проверим, что будет происходить с триангуляцией при добавлении оставшихся i внутренних точек, каждый раз по одной. Мы утверждаем, что добавление каждой такой точки приводит к увеличению числа треугольников на два. Во-первых, точка может оказаться внутри некоторого треугольника и тогда такой треугольник заменяется тремя новыми треугольниками. Во-вторых, если точка совпадает с одним из ребер триангуляции, то каждый из двух треугольников, примыкающих к этому ребру, заменяется двумя новыми треугольниками. Из этого следует, что после добавления всех г точек, общее число треугольников составит (n - i - 2) + (2i), или просто n + i - 2.

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

Для формирования триангуляции Делоне нам потребуется несколько новых определений. Набор точек считается круговым, если существует некоторая окружность, на которой лежат все точки набора. Такая окружность будет описанной для данного набора точек. Описанная окружность для треугольника проходит через все три ее (не коллинеарные) вершины. Говорят, что окружность будет свободной от точек в отношении к заданному набору точек S, если внутри окружности нет ни одной точки из набора S. Но, однако, точки из набора S могут располагаться на самой свободной от точек окружности.

Триангуляция набора точек S будет триангуляцией Делоне, если описанная окружность для каждого треугольника будет свободна от точек. На схеме триангуляции показаны две окружности, которые явно не содержат внутри себя других точек (можно провести окружности и для других треугольников, чтобы убедиться, что они также свободны от точек набора). Это правило не соблюдается-- внутрь проведенной окружности попала одна точка другого треугольника, следовательно, эта триангуляция не относится к типу Делоне.

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

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

· спящие ребра: ребро триангуляции Делоне является спящим, если она еще не было обнаружено алгоритмом:

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

· мертвые ребра: ребро считается мертвым, если оно обнаружено и известны обе примыкающие к нему области.

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

На каждой итерации выбирается любое одно из ребер е границы и оно подвергается обработке, заключающейся в поиске неизвестной области, ко торой принадлежит ребро е. Если эта область окажется треугольником f, определяемым концевыми точками ребра е и некоторой третьей вершины v, то ребро е становится мертвым, поскольку теперь известны обе примыкающие к нему области. Каждое из двух других ребер треугольника t переводятся в следующее состояние: из спящего в живое или из живого в мертвое. Здесь вершина v будет называться сопряженной с ребром е. противном случае, если неизвестная область оказывается бесконечной плоскостью, то ребро е просто умирает. В этом случае ребро е не имеет сопряженной вершины.

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

Пусть точки p и q лежат внутри некоторого многоугольника. Будем говорить, что точка q видна из точки p, если отрезок, соединяющий эти точки, целиком содержится в заданном многоугольнике.

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

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

Рассмотрим следующую задачу: на плоскости задан набор точек s₀, s₁, s₂, … s_n-1 . Требуется построить «минимальный» звездчатый многоугольник так, чтобы его ядро содержало точку s₀ .

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

Для определения того, в какое место границы текущего многоугольника нужно вставить точку s_i , заметим, что все вершины звездчатого многоугольника должны быть упорядочены вокруг точки его ядра, а значит, и относительно точки s₀ , принадлежащей ядру. Будем обходить границу многоугольника по часовой стрелке, начиная с s₀ , сравнивая каждый раз вставляемую точку и очередную точку границы. Для точек введем соотношения: p<q, если И_p < И_q или И_p = И_q и V_p<V_q. При таком упорядочении, обход текущего многоугольника осуществляется от больших точек к меньшим точкам.

Построение диаграммы Воронова.

Определение диаграммы Воронова

• Пусть P множество из n различных точек на плоскости.

• Диаграмма Воронова для P - это разбиение плоскости на n областей (локусов), по одному для каждой точки.

• Точка q лежит в области соответствующей pi P если

• Расстояние( q, pi ) < Расстояние( q, pj ), для любой pi P, j i.

Точка q лежит на ребре диаграммы e между pi и pj тогда и только тогда, когда окружность максимального радиуса с центром в q касается только pi и pj

– Ребро диаграммы - подмножество точек локуса равноудаленных от pi и pj

Диаграмма Воронова имеет линейную сложность

{|v|, |e| = O(n)}

Утверждение:

For n 3, |v| 2n 5 and |e| 3n 6

Д-во: Общий случай

• Формула Эйлера: для связного, планарного графа



|v| - |e| + f = 2

Где:

|v| количество вершин

|e| количество ребер

f число граней

Время выполнения алгоритма:

Каждая новая сторона может породить максимум две дуги

а Разделяющая цепь может иметь максимум 2n - 1 дуг

а максимум O(n) областей и возможных окружностей с очереди событий

Область/Окружность Обработчик событий O(log n)

Поэтому, время выполнения O(n log n) - полное время выполнения

Более подробно алгоритм построения диаграммы Воронова описан в файле презентации «Диаграмма Воронова.ppt»

2. ПРОЕКТИРОВАНИЕ СИСТЕМЫ

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

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

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

Графическое представление происходит в классе CDinkumView, в методе OnDraw, в котором реализуется отображение координатной сетки - Show_grid. Данный метод учитывает текущие размеры окна, и в соответствии с ними перерисовывает координатную сетку. На рисунке, приведенном ниже можно видеть, что при изменении размеров окна комментариев, меняется распределение точек на координатной плоскости.

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

В программе реализован свой класс вектора (Vector2D), который отвечает за все операции с векторами и точками.

3. РЕАЛИЗАЦИЯ СИСТЕМЫ

Программа разработана на языке C++, в среде Visual Studio, с использованием библиотеки классов MFC.

В программе реализованы следующие классы, каждый из которых отвечает за свою задачу:

CContainer

Polygonn

TriangleList

Triangle

DebugInfo

NextStep

Vector2D

В классе CContainer содержатся данные и функции, которые используются классами-наследниками.

static int NUM_POINTS - количество точек

static int SCALE - масштаб координатной стеки

static Vector2D *v_points - массив векторов

static COLORREF SEL_STATES[4] - массив возможных состояний точек

CRect setInside(Vector2D pt, CDC *dc, int index, int alg_type) - метод, который рисует точки, в соответствии с состоянием каждой точки.

void init_points (); - инициализация точек (генерация случайным образом)

void draw_points (CDC *dc); - рисование точек

void garbage_collector(); - метод удаления выделенной памяти

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

Point *b_p, *e_p; - указатели на хранимые точки

void init(); - инициализация данных

void create_report(); - создание отчета

void garbage_collector(); - удаление выделенной памяти

int draw_all (CDC *dc, int i_step, int j_step); - рисование заданного шага по i,j

int AddVertex(Vector2D *v,int num=0); - добавление вершины

int ConvS (Vector2D *s, bool true_if_start_again=false) - функция построения выпуклого многоугольника.

Данные и методы, приведенные ниже относятся к построению звездчатого полигона:

Vector2D *vertices - набор точек

int numVertices ; - количество точек

int maxVertices ; - максимальное количество точек

int AddVertex(const Vector2D &v, int after); - добавление вершины в полигону

int polarCmp(Vector2D *p, Vector2D *q); - сравнение точек по углу между ними

void Polygonn::resize(int size); - изменение размера массива точек

Polygonn* build_a_star (); - построение звездчатого полигона

void DrawStarPolygon(CDC *dc, const Polygonn * pl=NULL ); - отрисовка полигона.

Класс TriangleList отвечает за реализацию метода триангуляции Делоне, содержит в себе список треугольников Triangle

Triangle *triangles - указатель на класс треугольника

int count; - количество треугольников

void Insert(Triangle t); - добавление треугольника

void draw_triangle(Triangle ,CDC *) - рисование треугольника

void draw_all(CDC *dc, bool if_init,int *res); - рисование промежуточных результатов

void garbage_collector(); - удаление выделенной памяти

Класс Triangle - это простой класс, в котором хранятся три точки, которые представляют собой треугольник.

Vector2D a, b, c; - координаты точек

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

Edge *edges; - список ребер

void Insert(Edge& e); - добавление ребра в список

void Del(Edge&); - удаление ребра из списка

bool Find(Edge&); - поиск заданного ребра с списке

Edge RemoveAt0(); - удаление первого ребра из списка

int IsEmpty() - проверяет есть ли список

Класс Edge представляет собой ребро (отрезок) с начальной и конечной точкой

Vector2D org; - начальная точка

Vector2D dest; - и конечная точка

void Flip(); - поворот ребра

void Rot(); - построение перпендикуляра к ребру

bool Intersect(Edge& e, double& t, CDC *dc); - проверка на пересечения перпендикуляра окружности.

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

int x,y - координаты начальной точки вектора

double polarAngle () const; - возвращает арктангенс угла между точками x,y

double length() const; - вычисляет длину вектора

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

int current_step; - текущий шаг алгоритма

double angle; - угол

Vector2D last_point; - последняя найденная точка

Vector2D base_point; - базовая точка (откуда происходит поиск)

Vector2D new_point; - точка кандидат (кандидат на добавление в список)

Класс NextStep содержит список шагов (указатель на DebugInfo), а также дополнительную информацию

Vector2D cur_points; - информация по содержимому

DebugInfo* p_debug ; - список шагов

4. МЕТОДИКА И ПРОГРАММА ИСПЫТАНИЙ

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



Рисунок 2 Пример построения выпуклой оболочки

Второй пример иллюстрирует работу программу программы при построении триангуляции Делоне.

Рисунок 3 Пример построения триангуляции Делоне

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

Рисунок 4. Пример звездчатого полигона.

Ниже приведен пример сгенерированного текста.



ЗАКЛЮЧЕНИЕ

В результате выполнения данного курсового проекта был разработан программный макет лабораторного практикума по курсу ГИИСиКГ, проанализирована теория, описывающая методы компьютерной графики, а также разработано программное приложение, реализующее 3 алгоритма машинной графики, демонстрирующее их работу и генерирующее задачи, а также решение к ним. Программное приложение разработано на языке C++ в среде Visual Studio 6.0 c использованием MFC.



СПИСОК ЛИТЕРАТУРЫ

1. Роджерс Д. "Математические основы машинной графики", М.: Мир, 2001, - 456с.

2. Мешков А., Тихомиров Ю. Visual C и MFC. СПб.: “БХВ-Петербург”, 2002, - 1002c.

3. Препарата Ф., Шеймос М. “Вычислительная геометрия”. М.: “Мир”, 1989 - 464с.

4. Шикин Е. В., Боресков А.В. “Компьютерная графика. Полигональные модели.”, М.: “Диалог МИФИ”, 2001 - 420с.

Размещено на Allbest.ru

...