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.

Висновки

 

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


 

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

44265. Ремонт коллекторов электрических машин постоянного тока 1.37 MB
  Стержни обмотки якоря двигателя соединены по определенней схеме с пластинами коллектора. С помощью щеток 2 скользящих по пластинам коллектора обмотка якоря соединяется с внешней сетью. Провести внешний осмотр коллектора и электрощеток при разборке и дефектации электрической машины. Перечень признаков ослабления посадки пластин коллектора при которых необходимо произвести обтяжку конуса: почернение каждой второй или третьей пластины коллектора; сколы на электрощетках; отдельные...
44266. Исследование отмывающей способности раствора ПАВ «DeltaGreen» с концентрацией 5,0% 1.81 MB
  Ежегодно миллионы тонн нефти выливаются на поверхность Мирового океана, попадают в почву и грунтовые воды, сгорают, загрязняя воздух. Большинство земель в той или иной мере загрязнены сейчас нефтепродуктами.
44267. Методичні вказівки. Психологія 466.5 KB
  Як теоретико-прикладне дослідження дипломна робота повинна містити глибоке теоретичне осмислення актуальної проблеми, а також обґрунтований проект практичного її розв’язання, виконаний на основі проведеного аналізу певного об’єкту, феномену, явища, процесу, іншого, виділення різних аспектів, показу його зв’язків з іншими явищами
44268. Рынок государственных ценных бумаг и особенности его функционирования 778.5 KB
  Рынок государственных ценных бумаг и особенности его функционирования. Теоретические основы функционирования рынка государственных ценных бумаг Сущность государственного рынка ценных бумаг и его участники. Характеристика государственных ценных бумаг Правовые основы функционирования рынка государственных ценных бумаг Анализ рынка государственных ценных бумаг России Оценка выпуска и обращения федеральных займов Анализ развития рынка...
44270. Интернет как модус коллективного бессознательного в информационном обществе: новейшая мифология Интернет-рекламы 3.41 MB
  Бессознательное имеет определенные специфические характеристики, которые отличают его от предсознания и самого сознания. Стремления и мотивы, сходные с инстинктами, существуют в бессознательном отвлеченно и не связано. Бессознательное лишает свое содержимое целого ряда атрибутов, таких, как время и взаимоисключение, поскольку функции, выполняющие эти атрибуты, свойственны сознанию
44271. Лингвистические особенности жаргона северодвинских рок-музыкантов 548 KB
  Особенности морфемной структуры жаргонного слова и способы образования жаргонных единиц. Материалы к словарю жаргона северодвинских рок-музыкантов. В принципе каждый социальный диалект может быть изучен с чисто структурных позиций описан его словарь выявлены источники его пополнения безусловно что этим фактам может быть дана и социолингвистическая интерпретация но они могут быть освещены и исключительно лексикологически выявлены наиболее частотные морфологические модели особенности фонетики и синтаксиса если таковые...
44272. Система запалювання з новим способом загоряння палива 3.04 MB
  Виконаний вибір головних розмірів і обмотки якоря, розрахунок геометрії магнітопроводу і вибір проводу обмотки якоря, визначення розмірів магнітного кола, розрахунок магнітного кола, розрахунок обмотки збудження, розрахунок колектора і щіток, розрахунок додаткових полюсів, розрахунок втрат
44273. Классификация гражданско-правовых договоров 338 KB
  Общие признаки такие как: правомерность действия действие принципа допустимости и свободы договора совпадение воли и волеизъявления не могут исключить возможность их классификации. Общее для всех сделок учение о делении их на консенсуальные и реальные может применяться и к договорам. Гражданский кодекс РФ содержит в себе правила об отдельных видах обязательств и более распространенных в практике договорах. Это значит что все участники равны при заключении и исполнении договора при судебной защите их интересов.