75673

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

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

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

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

Украинкский

2015-01-24

264.79 KB

0 чел.

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

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

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

Кафедра ПЗ

Практична робота №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.

Висновки

 

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


 

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

51585. Матеріально технічне забезпечення сервісно-виробничого процесу 90 KB
  У залах обладнання розміщають відповідно до напрямків руху потоків відвідувачів і обслуговуючого персоналу, а також потоків чистого й використаного посуду. Ширина проходів у залах визначається відстанню між спинками стільців, вільними сторонами столів або між спинками стільців і вільними сторонами (кутами) столів
51587. Рідна мова 24.5 KB
  Перше речення було просте але присудок у нього є не дієслово а іменник виражений в значенні дієслова. А ось друге речення стало для дітей важким. Тому що речення було із зверненням . Мабуть ми вчителі мало уваги звертаємо на такі речення.
51588. Розвивальні ігри. Принцип розвязання протиріччя 55 KB
  Пригадайте чим ми займалися на минулому занятті Що ми збудували Чарівну країну А хто є господаркою цієї країни Королева Пригадайте її ім’я Фантазія А яке завдання загадала вам Королева Фантазія Діти розповідають що вони подарують своєму другові або показують свої малюнки створених за допомогою геометричних фігур. Було в неї багато помічників: це і діти які вміють фантазувати і казкові герої які люблять творити чудеса. Відгадайте хто завжди говорить: Діти давайте жити дружноâ€ Кіт Леопольд І завітав герой...
51589. Зняття статичних характеристик і визначення параметрів транзисторів в схемі з СЕ 76.5 KB
  Мета роботи: Вивчення особливостей роботи транзистора в схемі з ОЕ (зняття вхідної та вихідної характеристик) і визначення параметрів транзистора по характеристикам.