75673

Задачі обчислювальної геометрії

Практическая работа

Информатика, кибернетика и программирование

Припустимо, що знайдена найменша в лексикографічному порядку точка р1 заданої множини точок. Ця точка завідомо є вершиною оболонки, і тепер треба знайти наступну за нею вершину р2 опуклої оболонки. Точка р2 - це точка, яка має найменший позитивний полярний кут відносно точки р1 як початку координат

Украинкский

2015-01-24

264.79 KB

1 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Практична робота №1 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013

Тема: Задачі обчислювальної геометрії.

Мета: Навчитися розв’язувати задачі обчислювальної геометрії: реалізовувати абстрактні типи геометричних даних, розв’язувати задачі опрацювання точкових множин.

Завдання:

Варіант № 9. Побудувати опуклу лінійну оболонку множини точок A1A2...An методом Джарвіса.

Теоретичні відомості

Суть методу обходу Джарвіса для побудови опуклої оболонки:

  1.  шукаємо крайню точку p1.
  2.  шукаємо p2 таку, що всі інші точки лежать по один бік від p1 p2.
  3.  шукаємо p3 таку, що всі інші точки лежать по один бік від p2 p3 і т.д., поки не буде знайдена точка p1.

Зауваження: якщо на прямій, що містить сторону conv(L) pipi+1 лежить декілька точок із L,, то в якості pi+1 треба взяти найдальшу від pi.

Алгоритм, що використаний у програмі:

Припустимо, що знайдена найменша в лексикографічному порядку точка р1 заданої множини точок. Ця точка завідомо є вершиною оболонки, і тепер треба знайти наступну за нею вершину р2 опуклої оболонки. Точка р2 - це точка, яка має найменший позитивний полярний кут відносно точки р1 як початку координат. Аналогічно наступна точка р3 має найменший полярний кут відносно точки р2 як початку координат, і кожна наступна точка опуклої оболонки може бути знайдена за лінійний час. Алгоритм Джарвіса обходить кругом опуклу оболонку ( звідси і відповідну назву - обхід Джарвіса ), породжуючи в потрібному порядку послідовність крайніх точок, по одній точці на кожному кроці. Таким чином, будується частина опуклої оболонки (ламана лінія) від найменшої у лексикографічному порядку точки до найбільшої у лексикографічному порядку точки. Побудова опуклої оболонки завершується знаходженням іншої ламаної, що йде з найбільшої у лексикографічному порядку точки в найменшу у лексикографічному порядку точку.


Як видно з малюнка, на поточному кроці вже знайдено три точки, що утворюють опуклу оболонку. Це 2, 5 і 8. Наступна точка "i" повинна утворювати максимальний кут 5-8-i. Інтуїтивно зрозуміло, що це буде точка 4. Сам кут при цьому не шукається, а шукається тільки його косинус. Кут 5-8-i є кутом у трикутнику. Значення кута варіюється в інтервалі [0,180] градусів. Ми пам'ятаємо, що косинус кута в цьому інтервалі є монотонно спадною функцією. Тому можемо зробити висновок: чим більше кут, тим менше його косинус.
Також не
 забуваємо обробляти вироджений випадок, коли є два претенденти (точки A і B) на вакантне місце бути наступною точкою в опуклій оболонці. При цьому остання крапка в опуклій оболонці X і точки A, B лежать на одній прямій. У такому випадку потрібно вибрати ту точку, яка найбільш віддалена від точки X. У той момент, коли наступна точка в опуклій оболонці збіглася з першою, можна зробити висновок, що опукла оболонка побудована. 


Блок-схема алгоритму


Лістинг фрагментів програми

class UserPoint // point class

{

   public:

   int x,y;

   UserPoint(void);

   UserPoint(int X, int Y);

   ~UserPoint(void);

   void Draw(HDC hdc);

   void Connect (HDC hdc);

};

bool operator != (const point &a, const point &b)  // operator != overloading

{

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

}

double distanceBtwP (const point &a, const point &b) // distance btw two points

{

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

}

//------------------------------------------

//-------GLOBAL VARIABLES----

//------------------------------------------

int n=0;

vector<UserPoint> mas;  // array of points on the plane

vector<int> convex_hull; // vector includes indexes of points of initial array

double P; // perimeter of convex hull

int connect = 0;

bool addPermission = true;

//------------------------------------------

//------------------------------------------

bool operator != (const UserPoint &a, const UserPoint &b)  // operator != overloading

{

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

}

double distanceBtwP (const UserPoint &a, const UserPoint &b) // distance btw two points

{

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

}

void input(int press_x, int press_y, int n)

{

   mas.resize(n);  // making size of array == n

mas[n-1].x=press_x;  //LOWORD(lParam)

mas[n-1].y=press_y;  //HIWORD(lParam)

}

//---------------------------------------------------------------

// ---------------- funcs for compare of double numbers:

double eps = 1e-8;  // number for compare

double Fabs(const double &a) // |x|

{

   if (a<0)

       return –a;

   return a;

}

bool Equal(const double &a, const double &b)  // ==

{

   return Fabs(a-b) <= eps;

}

bool More(const double &a, const double &b)   // >

{

   return !Equal(a,b) && a > b;

}

bool Less(const double &a, const double &b)  // <

{

   return !Equal(a,b) && a < b;

}

// ----------------------------------------------------

// ----------------------------------------------------

double CosAngle(const UserPoint &prev,const UserPoint &cur,const UserPoint &next) // returns cosine btw current-previus & current-next rays

{

   UserPoint v1(next.x – cur.x, next.y – cur.y);  // ray 1: next point – current point, coordinates of vector

   UserPoint v2(prev.x – cur.x, prev.y – cur.y);  // ray 2: previous point  - reviou point, coordinates of vector

   return (v1.x * v2.x + v1.y * v2.y) / (distanceBtwP(prev,cur) * distanceBtwP(cur,next)); // cosine btw rays

}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

void ConvexHullJarvis(const vector<UserPoint> &mas, vector<int> &convex_hull)

{

   // find edge left point on the bottom

   int base = 0;

   for (int i=1;i<n;i++)

   {

       if (mas[i].y < mas[base].y)

           base = I;

       else

           if (mas[i].y == mas[base].y &&

               mas[i].x <  mas[base].x)

               base = I;

   }

   convex_hull.push_back(base); // this point IS a part of convex hull, push it to the vectorof indexes

   UserPoint first = mas[base];  //our “first” point in mas

   UserPoint cur = first; // in the beginning current point is first point

   UserPoint prev = UserPoint(first.x – 1, first.y); // imaginary previous point in the beginning

   do

   {

       // the greater the angle, the less the cosine => we should find the less cosine (the biggest angle):

       double minCosAngle = 1e9;

       double maxLen = 1e9;

       int next = -1;

       for (int i=0;i<n;i++)  // go through the array

       {

           double curCosAngle = CosAngle(prev, cur, mas[i]);  //  getting cosine btw current-previous ray && vector connecting next point (mas[i]) in mas

           // searching for the less cosine

           if (Less(curCosAngle,minCosAngle)) // if found less cosine

           {

               next = I; // next point index

               minCosAngle = curCosAngle;

               maxLen = distanceBtwP(cur,mas[i]);  // distance btw currnet point and next point – max I

           }

           else if (Equal(curCosAngle, minCosAngle)) // if points on one line  (degenerate case)

           {

               double curLen = distanceBtwP(cur,mas[i]);  // current I

               if (More(curLen,maxLen))  // if current I > max I

               {

                   next = I; // next point index

                   maxLen = curLen; // max length becomes current

               }

           }

       }

       prev = cur;  // current point will be revious point in the next iteration

       cur = mas[next]; // next point will be current in the next iteration

       convex_hull.push_back(next); //  push index of next point to the vector of indexes

   }

   while (cur != first); // while the last point will be the first

}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

void solve()

{

   ConvexHullJarvis(mas,convex_hull);

   for (size_t i=0; i<convex_hull.size()-1; i++)

       P += distanceBtwP(mas[convex_hull[i]],mas[convex_hull[i+1]]);  // perimeter of the convex hull

}

Результат виконання

Складність алгоритму

Складність алгоритму дорівнює ( 6n2 + 7n + 4 ) від деякого часу виконання T.

Висновки

 

Навчилися розв’язувати задачі обчислювальної геометрії: реалізовувати абстрактні типи геометричних даних, розв’язувати задачі опрацювання точкових множин. Було побудовано опуклу лінійну оболонку множини точок методом Джарвіса.


 

А также другие работы, которые могут Вас заинтересовать

46179. Литогенез 211 KB
  Понятие осадочных горных пород.генез совокупность природных процессов образования и последующих изменений осадочных горных пород. Вальтером который выделил в процессе образования осадочных пород 5 основных фаз: выветривание горных пород денудация включая перенос исходного материала осадков отложение диагенез и метаморфизм. В цикле литогенеза различают следующие стадии: 1 образование и мобилизация исходного вещества осадков в процессе физического и химического разрушения материнских пород и его перенос к месту захоронения ...
46180. Структура научно-исследовательской работы. Требования к введению, реферату, основной части и заключению 64 KB
  Структура научно-исследовательской работы. Приложение задачи Введение Данная контрольная работа посвящена теме Структура научно-исследовательской работы. Целью написания данной работы является изучение структурных элементов научно-исследовательской работы.
46181. Анализ отчета о прибылях и убытках ОАО «Заря» 88 KB
  Как видно из таблицы 17, за отчетный период убыток от продаж увеличился на 427 тыс. руб., что является отрицательным моментом в деятельности предприятия. Что касается процентов к уплате, то их величина уменьшилась на 770 тыс. руб
46182. Ветеринарно-санитарная экспертиза продуктов животноводства и гигиены сельскохозяйственных животных 356 KB
  Вынужденный убой животных в вашем хозяйствеместо и способ убоя причины и пути реализации мяса сравните с действующими правилами и сделайте соответствующие выводы. Ветеринарносанитарная экспертиза продуктов убоя животных при отравлении. Вынужденный убой животных в вашем хозяйстве место и способ убоя причины и пути реализации мяса сравните с действующими правилами и сделайте соответствующие выводы.
46183. Гимнастика женщин во второй половине беременности. Лечебная физкультура при язвенной болезни. Упражнения при остеохондрозе 70 KB
  Исходное положение: основная стойка руки на поясе. Исходное положение: основная стойка руки на поясе. Исходное положение: основная стойка руки на поясе. Исходное положение: стоя ноги на ширине плеч руки у груди согнуты в локтях.
46184. Социальная педагогика как наука и общественная практика 62 KB
  Вывод: Закономерности развития социальной педагогики как науки лежат в сфере гуманитарных и социальных наук а также в реальной практике общественной и культурной жизни что и можно назвать истоками развития. Нужно отметить что социальная педагогика возникает в недрах экономиче ской культурной идеологической сфер жизни. Вывод: Источниками дальнейшего развития социальной педагогики можно назвать определённые сферы практической жизни и области знаний. В практике социальной жизни т.
46185. Автоматизация холодильных компрессорных станций 222.5 KB
  По уровню автоматизации компрессорные холодильные установки занимает одно из ведущих мест среди других отраслей промышленности. Холодильные установки характеризуются непрерывностью протекающих в них процессов. При этом выработка холода в любой момент времени должна соответствовать потреблению (нагрузке).
46186. МОДЕЛИРОВАНИЕ СИСТЕМ 667.5 KB
  Формализуемые решения Литература Основы моделирования систем Модели и моделирование Модель и моделирование универсальные понятия атрибуты одного из наиболее мощных методов познания в любой профессиональной области познания системы процесса явления.
46187. Изучение явления сухого трения 51.5 KB
  Цель работы: Экспериментальное изучение закономерностей сухого трения; Научиться измерять и вычислять коэффициент трения скольжения и покоя различными способами. Определение коэффициента трения скольжения. Вид вещества Сила упругости F Н Масса бруска mкг Деформация пружины x м Перемещение бруска м Коэффициент трения S1 S2 S3 S4 Экс.