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.

Висновки

 

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


 

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

21548. Схема механизмов швейного предприятия 12.55 MB
  Машины машиныавтоматы и автоматические линии легкой промышленности М. Швейные машины: Иллюстрированное пособие. Швейные машины М. Швейные машины: Иллюстрированное пособие.
21549. Регулировки механизма челнока 4.66 MB
  I регулировка зазора между носиком челнока и иглой 005 мм – 01 мм. II – регулировка зазора между зубом установочного пальца и дном открытого паза П шпуледержателя 8 который должен составлять 06 – 08 мм рис. III – регулировка натяжения нижней нити; осуществляется поворотом регулировочного винта с большей головкой на тормозной пластине шпульного колпачка. IV – регулировка количества подаваемого в челнок масла рис.
21550. Зигзаг-машины 7.3 MB
  Принципиальное отличие от стачивающих машин в том что зигзагмашины Имеют специальный дополнительный механизм отклонения иглы в направлении поперёк строчки Оснащены челноком увеличенного объёма вследствие увеличения нити в стежке Располагают челночный вал вдоль строчки что необходимо для отклонения иглы поперёк строчки. На рисунке 1 показаны параметры простейших зигзагстрочек: а – двухукольного зигзага и б – четырёхукольного – для усиленного стачивания где tи – величина отклонения иглы при прокладывании стежка tИ – шаг подачи...
21551. Машины цепного переплетения ниток 1.22 MB
  1 Общая характеристика машин цепного стежка. В связи с появлением нетрадиционных материалов для пошива а также с тенденцией автоматизации основных и вспомогательных операций спрос на машины цепного стежка неизменно высок. Преимущества машин цепного стежка: Уменьшенное истирание верхней нити при подаче в машину вследствие отсутствия операции обвода её вокруг шпуледержателя. Недостатки машин цепного стежка: повышенная распускаемость строчки вследствие открытости переплетения и существенное увеличение расхода ниток – в 16 – 23 раза на к...
21552. Устройство машины типа ЭЗМ с пластинчатым ножом 2.53 MB
  Абалкин ЛИ 1 Устройство машины типа ЭЗМ с пластинчатым ножом. 11 дана принципиальная схема этой машины на которой обозначено: Трёхфазный электродвигатель Кривошип с противовесом Шатун в верхней головке которого – шариковый подшипник Корпус из пластика или алюминия Ползун в направляющих Пластинчатый нож закреплённый в ползуне Платформа машины Ролики на игольчатых подшипниках 4 шт. Паспортные данные машины ЭЗМ316 Высота настила до 16 см Частота вращения кривошипа n = 2700 об мин Ход ножа...
21553. Устройство механизма иглы машины КУР - 31 4.16 MB
  Устройство механизма иглы машины КУР 31. Технологическое назначение механизма – ввести верхнюю нить в материалы и образовать петлюнапуск. Кинематическое назначение механизма – преобразовать вращение главного вала в возвратнопоступательное движение игловодителя На рисунке 1 дана пространственная структурная схема механизма иглы машины ряда КУР31. 8 – иглодержатель 9 – игловодитель 10 – челнок К1 и К2 калибры для выполнения регулировок механизма А’ – отверстие в рукаве для калибра К1 l эль – длина калибра К2.
21554. Международные валютно-кредитные и финансовые отношения 115.5 KB
  Первоначально возникла национальная валютная система это форма организации валютных отношений страны сложившаяся исторически и закрепленная национальным законодательством а так же обычаями международного права. На национальную валютную систему возлагается ряд функций: формирование и использование валютных ресурсов; обеспечение внешнеэкономических связей страны; обеспечение оптимальных условий функционирования национального хозяйства. Региональная валютная система это форма организации валютных отношений ряда государств...
21555. Международные экономические организации 90 KB
  Необходимость регулирования мировой экономики на межгосударственном уровне Интернационализация хозяйственной жизни рост взаимозависимости между странами а также возникновение глобальных проблем объективно предопределяют необходимость активного сознательного регулирования мирового хозяйства. В период между двумя мировыми войнами не было широкого распространения межгосударственного регулирования мировой экономики. При голосовании принципиальных вопросов США могли контролировать принятие решений ибо обладали большим количеством голосов в...
21556. Международный рынок услуг 221 KB
  Международный рынок услуг. Международный рынок услуг. План: Сущность и сегменты международного рынка услуг. Особенности формирования и развития международного рынка услуг.