Модификация эталонного проекта «Выпуклая оболочка»

Федеральное агентство

по образованию 
 

Государственное образовательное  учреждение

Московский  государственный  индустриальный университет

(ГОУ  МГИУ) 

Кафедра информационных технологий и систем в экономике и управлении 
 
 
 

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

курсовой  работы  
 

Тема: Модификация эталонного проекта «Выпуклая оболочка» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                                              Студент jjgfb ghd

                                              Группа 2291

                                              Преподаватель Носова Т.К. 
 
 
 
 
 

Москва 2010 

АННОТАЦИЯ

      В данной курсовой работе требуется  модифицировать текст эталонного  проекта «Выпуклая оболочка» таким образом, чтобы индуктивно определить, количество рёбер выпуклой оболочки, параллельных оси ординат. Программа написана на языке C++. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

СОДЕРЖАНИЕ 

Введение.......................................................................................................................................................4

1. Теоретическая часть
1. Описание Выпуклой оболочки......................................................................................................5
2. Описание алгоритма программы...................................................................................................6
2. Проектная часть.....................................................................................................................................7
1. Описание структуры программы..................................................................................................7
2. Описание класса R2Point...............................................................................................................7
1. Назначение............................................................................................................................7
2. Описание данных..................................................................................................................7
3. Описание методов................................................................................................................7
1. Описание конструктора R2Point()................................................................................7
2. Описание метода dist.....................................................................................................7
3. Описание метода area....................................................................................................7
4. Описание метода equal..................................................................................................8
5. Описание метода isTriangle...........................................................................................8
6. Описание метода inside.................................................................................................8
7. Описание метода light...................................................................................................8
8. Описание метода test.....................................................................................................8
3. Описание класса Deq......................................................................................................................8
1. Назначение............................................................................................................................8
2. Описание данных..................................................................................................................8
3. Свойства Deq........................................................................................................................9
4. Описание методов класса Deq.............................................................................................9
4. Описание класса Figure..................................................................................................................9
1. Назначение............................................................................................................................9
2. Описание методов................................................................................................................9
5. Описание класса Polygon.............................................................................................................10
1. Описание данных..................................................................................................................10
2. Описание методов................................................................................................................10
1. Описание конструктора Polygon ().............................................................................10
2. Описание метода add...................................................................................................10
3. Описание метода grow.................................................................................................10
4. Описание метода count................................................................................................11
6. Описание класса Segment.............................................................................................................11
1. Назначение..........................................................................................................................11
2. Описание данных................................................................................................................11
3. Описание методов..............................................................................................................11
1. Описание метода add...................................................................................................11
2. Описание метода count................................................................................................11
7. Описание класса Point..................................................................................................................12
1. Назначение..........................................................................................................................12
8. Описание класса Void...................................................................................................................12
1. Назначение..........................................................................................................................12
9. Описание класса Convex..............................................................................................................12
1. Назначение..........................................................................................................................12
2. Описание данных................................................................................................................12
10. Описание функции main....................................................................................................12
3. Испытательная программа..................................................................................................................14

Заключение.................................................................................................................................................16

Список  литературы....................................................................................................................................17

Приложение 1. Примеры работы программы…………………………………………………………..18

Приложение 1. Текст программы………….…………………………………………………………….20 

 

ВВЕДЕНИЕ

    Цель  данной курсовой работы - модифицировать текст эталонного проекта «Выпуклая оболочка», для индуктивного определения количества ребер выпуклой оболочки, параллельных оси ординат. Для этого понадобится добавить несколько методов, помогающих сделать этот расчет. Программа написана на языке С++. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 

1.1. Описание Выпуклой оболочки 

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

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

     Выпуклой  оболочкой conv (М) множества М называется наименьшее выпуклое множество, содержащее М.

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

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

 

Рис.1.1 Выпуклая оболочка точек плоскости  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.2. Описание алгоритма программы 

      Проверка  условия выполняется с помощью метода test. Этот метод проверяет, параллельно ли ребро оси ординат. Если условие выполняется, то возвращается единица, в противном случае – ноль. На рис.2 отрезок аb (рис.2) параллелен оси ординат, test возвращает единицу. Отрезок ae не параллелен оси ординат, следовательно, test возвращает ноль, и т.д. Проверив все точки на рис.2, найдем одно ребро, удовлетворяющие условию.

 

Рис. 1.2. Выпуклая оболочка с ребром, параллельным оси ординат 
 
 
 
 
 
 
 
 
 
 
 

2. ПРОЕКТНАЯ ЧАСТЬ

2.1. Описание структуры проекта

      В данном проекте используется метод  проектирования сверху вниз.

2.2. Описание класса R2Point

2.2.1. Назначение

      Класс R2Point хранит данные о координатах точки на плоскости и методы, работающие с этой точкой на плоскости.

2.2.2. Описание данных

      Данными класса являются координаты точки на плоскости.

2.2.3.Описание методов

1. Описание конструкторов

      Класс R2Point содержит 2 конструктора. В конструкторе без параметров координаты точки обнуляются. Конструктор с параметром через заголовок записывает новые координаты точки.

2. Описание метода dist

      Этот  метод предназначен для вычисления расстояния между двумя точками по формуле

sqrt((a.x-b.x) +(a.y-b.y)), где а.х - абсцисса точки а, b.х - абсцисса точки b, а.у -ордината точки а, b.у - ордината точки b. 
 
 
 

Рис. 2.2.3.2 Нахождение расстояния между двумя точками

2.2.3.3.    Описание метода area

      Этот  метод предназначен для вычисления площади треугольника по трем точкам через формулу S =1/2((а.х - с.х) * (b.у - с.у) - (а.у - с.у) * (b.х - с.х)). Площадь может быть как положительной, так и отрицательной, зависит от порядка вершин. 
 
 
 
 

Рис 2.2.3.3 Нахождение площади треугольника по трем точкам

2.2.3.4.    Описание метода equal

    Сравнивает  точки, чтобы не было совпадений по координатам (совпадающих точек).

2.2.3.5.    Описание метода isTriangle

    Определяет, лежат ли три точки на одной  прямой. 
 
 
 
 

    Рис. 2.2.3.5 (а)(лежат)            Метод isTrianglе           Рис. 2.2.3.5 (б)(не лежат)

6. Описание метода inside

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

Рис. 2.2.3.6 Метод inside

7.   Описание метода light

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

8.   Описание метода test

    Проверяет, параллельно ли ребро оси ординат.(см. рис.1.2.) 

2.3.     Описание класса Deq

2.3.1.  Назначение

    Класс Deq служит для хранения вершин выпуклой оболочки, а также хранит данные и

методы, работающие с методом Deq. Deq представляет собой непрерывную реализацию дека объектов типа R2Point. Deg имеет head (голову) и tail (хвост).

2.3.2.  Описание данных

 

      Данными класса Deq является одномерный массив длинной в 16 элементов. Данными является адрес головы, хвоста, размер Deq.

    Array - массив, хранящий в себе вершины оболочки

    Size - переменная для хранения количества элементов в Deq

    Head – номер элемента головы

    Tail - номер элемента хвоста 
 
 
 

    Рис. 2.3.2 Класс Deq 
 

2.3.3. Свойства Deq

    Deq - обладает следующими свойствами:

• Читать и записывать можно только в хвост и голову
• Средние элементы Deq недоступны
• При записи элемента, он присоединяется к Deq
• При чтении первого элемента, этот элемент исчезает из Deq
• При чтении элемента из головы, головным становится следующий элемент
• При чтении из хвоста, хвостом становится предыдущий элемент

2.3.4. Описание методов класса Deq

• Forward- используется для чтения из головы
• Backward - используется для чтения из хвоста
• PushFront – используется для записи нового элемента в голову
• PushBack – используется для записи нового элемента в хвост
• PopFront – используется для чтения с удалением из головы
• РорВаск – используется для чтения с удалением из хвоста
• Front – используется для просмотра того, что в голове
• Back – используется для просмотра того, что в хвосте

 

2.4. Описание класса Figure

2.4.1. Назначение 

      Класс Figure содержит общие для выпуклой оболочки методы, которые должны быть виртуальными - add, perimeter, area и count; его наследниками являются классы Void, Point, Segment, Polygon. 

2.4.2.  Описание методов 

• Метод area предназначен для вычисления площади.
• Метод perimeter предназначен для вычисления периметра.
• Метод add предназначен для добавления новой вершины в оболочку.
• Метод count предназначен для возвращения количества ребер выпуклой оболочки, параллельных оси ординат.

 

2.5. Описание класса Polygon

2.5.1. Описание данных

    Данными в этом классе являются  S – площадь фигуры , P – периметр фигуры , k - счетчик рёбер, параллельных оси ординат.

2.5.2. Описание методов

2.5.2.1. Описание конструктора Polygon()

      Конструктор Polygon заносит в Deq три вершины оболочки. Он создает треугольник и вычисляет периметр и площадь получившейся фигуры. 

2.5.2.2 Описание метода add

      Этот  метод предназначен для добавления новых вершин в Deq. Но при добавлении новой точки возможны два случая:

1. Если в многоугольнике освещённых рёбер нет, то это означает, что новая точка попала внутрь или на границу старой выпуклой оболочки, и делать ничего не надо.
2. Если же освещённые ребра есть, то их надо удалить и соединить ребра с новой точкой. При реализации метода add (только в том случае, если есть освещенные ребра) выполняется следующие действия: