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

Автор работы: Пользователь скрыл имя, 04 Декабря 2010 в 12:58, курсовая работа

Описание

В данной курсовой работе требуется модифицировать текст эталонного проекта «Выпуклая оболочка» таким образом, чтобы индуктивно определить, количество рёбер выпуклой оболочки, параллельных оси ординат. Программа написана на языке 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

Скачать (228.45 Кб) Сколько стоит заказать работу?
Работа состоит из  1 файл

Курсач1.doc

— 389.00 Кб (Скачать документ)
  • удаляют ребра, попавшие внутрь оболочки
  • уменьшается периметр оболочки на длину удаленных ребер
  • увеличивается площадь оболочки на величину, равную площади треугольника, образованного удаляемым ребром и добавляемой точкой
  • к оболочке добавляется два новых ребра, а к её периметру сумма их длин.
 

      2.5.2.3 Описание метода grow

      Предназначен  для пересчета периметра и  площади, который необходимо производить  после удаления каждого ребра. В него передаются координаты удаляемых рёбер и координаты новой точки. После этого начинается корректировка площади, периметра и счётчика k, считающего количество ребер, параллельных оси ординат. Допустим, имеется выпуклая оболочка (рис.2.5.2.3(а)). Введем точку t (рис.2.5.2.3(б)). Точка t освещает ребра ае и ed. Метод grow вычтет из счетчика k удаляемые ребра, удовлетворяющие условию, вычтет длину данных ребер из периметра выпуклой оболочки, прибавит площадь треугольника aet и aed к площади выпуклой оболочки и удалит из программы точку е, записав на ее место точку t. Далее прибавит к площади выпуклой оболочки площадь треугольника atd , к периметру прибавит длины ребер at и td, прибавит к счетчику k добавленные ребра, удовлетворяющие условию. 
 
 
 
 
 
 
 
 
 

    Рис.2.5.2.3(а) Предыдущее состояние выпуклой оболочки   Рис.2.5.2.3(б)Следующее состояние 
 

        1. Описание  метода count

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

2.6. Описание класса Segment 

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

          Класс Segment - класс «двуугольник». Он предназначен для работы с двуугольником. В

данном классе также содержится метод count, который увеличивает счетчик k на единицу при

условии, что данный отрезок, будет параллелен оси ординат. 

2.6.2.  Данные

    Данными класса Segment являются 2 точки типа R2Point.

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

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

      Метод add предназначен для добавления новой вершины в оболочку. Если

      площадь для трех точек положительна, то add возвращает указатель на Polygon.

      2.6.3.2. Описание метода count

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

2.7. Описание класса Point

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

      Класс Point - класс «одноугольник». Данные класса – координаты одной точки. Периметр и площадь здесь являются нулевыми. Метод area возвращает 0, потому что у точки нет площади. Метод add передает управление классу Segment, если новая точка образует отрезок. Также после добавления новой точки управление может остаться у класса Point (в случае совпадения точки с имеющейся), для этого используют метод equal. Здесь метод count также возвращает ноль, так как в данном классе присутствует лишь одна точка .

2.8.  Описание класса Void

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

      Класс Void -класс «нульугольник». Методы perimeter, area и count здесь возвращают нулевые значения, так как пары чисел для проверки area в этом массиве нет. . Возвращаемым значением метода add является объект Point. 

2.9. Описание класса Convex 

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

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

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

      Данными класса является указатель на различные  классы

2.10. Описание функции main 

      В функции main происходит ввод координат точки и вывод площади, периметра и количества ребер, параллельных оси ординат. Главная функция зациклена оператором while. Выход из программы осуществляется путем ввода координат точки (-100;-100) или Ctrl+C.

      На  рисунке 2.10 изображена блок-схема главной функции.

      Блок 1 - начало

      Блок 2 - ввод вершин оболочки

    Блок 3 - проверка условия. Если хотя бы одна из координат точки равна -100, тогда осуществляется выход из программы, в противном случае программа выполняется

      Блок 4 - вывод параметров оболочки на экран

      Блок 5 - конец программы. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Рис. 2.10 Блок-схема 
 
 
 
 
 
 
 
 
 
 

3.ИСПЫТАТЕЛЬНАЯ ПРОГРАММА 

     В табл.1 приведены примеры ручного  и машинного счёта, по которым  проверяется правильность работы программы. 

      Таблица 1                

Номер испытания Координаты  точек Ручной  счёт Машинный  счёт
x y P S Кол. P S Кол.
1 0 0 0 0 0 0 0 0
0 1 2 0 1 2 0 1
0 2 4 0 1 4 0 1
2 1 0 0 0 0 0 0 0
1 4 8 0 1 8 0 1
5 4 13,6 8 1 13,6569 8 1
3 4 5 0 0 0 0 0 0
4 0 10 0 1 10 0 1
9 4 16,5 12,5 1 16,5021 12,5 1
 
 
 

На рис.3.1-3.3 получено графическое представление данной проверки. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

                                  

  

ЗАКЛЮЧЕНИЕ 

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

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

1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦМНО, 2000.

2. Подбельский В.В. /Язык С++ / – М.: МГИЭМ, 2008. 

3. Роганов Е.А. /Основы информатики и программирования - М.: МГИУ, 2001. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ПРИЛОЖЕНИЕ 1 

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

Рис.1 Пример 1 
 
 
 
 
 
 
 

Рис.2 Пример 2

Рис.3 Пример 3

 
 
 
 
 
 
 
 
 
 
 

ПРИЛОЖЕНИЕ 2 

Текст программы 
 

// Pol.cpp : Defines the entry point for the console application.

// 

//#include "stdafx.h"

#include <iostream.h>

#include <math.h> 

//Klass, opisyvauchiy tochku (Point) na ploskosti (R2)

class  R2Point

{

private:

      double x,y; 

public:

      R2Point(double a, double b)

       {

      x=a; y=b;

       };

      R2Point()

       {

       x=0; 

       y=0; 

       };

      double dist(R2Point a, R2Point b)

       {

       return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

       };

      double area(R2Point a, R2Point b, R2Point c)

       {

       double s= 0.5*((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x));

       return (s);

       };

      int equal(R2Point a, R2Point b)

       {

       return (a.x==b.x && a.y==b.y);

       };

      int isTriangle(R2Point a, R2Point b, R2Point c)

       {

       return (area(a, b, c) != 0.0);

       };

            int inside(R2Point a, R2Point b)

       {

       return ((a.x <= x && x <= b.x || a.x >= x && x >= b.x) &&

             (a.y <= y && y <= b.y || a.y >= y && y >= b.y));

       };

            int light(R2Point a, R2Point b)

       {

       double s=area(a, b, *this);

       return (s < 0.0 || (s == 0.0 && ! inside(a, b)));

       };

            int test(R2Point a, R2Point b)

            {

            if (a.x == b.x)

            return(1);

            else return(0);

            }

}; 

//Nepreryvnaya realizaciya deka

class Deq

{    

      //private final static int DEFSIZE = 16;

       R2Point array[16];

      int size, head, tail;

      int forward (int index)

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