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.

Висновки

 

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


 

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

33599. Процесс консультирования 73.5 KB
  Диагностика организации. Услугами консультантов пользуются органы государственной власти и местного самоуправления коммерческие и некоммерческие организации. Зарождение управленческого консультирования было вызвано двумя основными причинами: постоянным поиском предпринимателями и руководителями новых средств повышения эффективности и результативности организации; желанием специалистовуправленцев найти коммерческое приложение своим способностям. Консультирование заключается в приспособлении разработанной консультантами эффективной...
33600. Методы и модели принятия управленческого решения 44 KB
  Физическая модель выглядит как моделируемая целостность и должна обладать аналогичными характеристиками копируемого объекта. Отличительная характеристика физической модели состоит в том что в некотором смысле она выглядит как моделируемая целостность. Математическая модель принятия управленческих решений В математической модели называемой также символической используются символы для описания свойств или характеристик объекта или события.
33601. Территория и границы Российской Федерации как фактор развития российского государства 88.5 KB
  Центральный федеральный округ Белгородская область Брянская область Владимирская область Воронежская область Ивановская область Калужская область Костромская область Курская область Липецкая область Московская область Орловская область Рязанская область Смоленская область Тамбовская область Тверская область Тульская область Ярославская область Город федерального значения Москва Южный федеральный округ Северозападный федеральный округ Дальневосточный федеральный округ Сибирский федеральный округ Уральский федеральный округ...
33602. Влияние природных условий и природных ресурсов на территориальную организацию общества 50.5 KB
  Зависимость размещения отраслей производства народного хозяйства от природных особенностей территории. Классификация природных ресурсов и распределение их по территории страны. Под природными условиями понимается совокупность важнейших естественных характеристик территории отражающих основные особенности компонентов природной среды или местных природных феноменов. Климатические особенности территории проявляются прежде всего в соотношении тепла и влаги.
33603. Особенности территориальной организации населения России 40.5 KB
  Численность и естественное движение населения. Миграция населения. Региональные различия расселения населения.
33604. Закономерности территориальной организации производства 39.5 KB
  Показатели экономической эффективности размещения производства. Специфика размещения производства в России. Комплексное развитие производства.
33605. Особенности территориальной и отраслевой структуры хозяйства страны 159.5 KB
  ШШ Производственная сфера экономики включает: отрасли создающие материальные блага промышленность сельское хозяйство строительство; отрасли доставляющие материальные блага потребителю транспорт и связь; отрасли действующие в сфере обращения торговля общественное питание материально техническое снабжение сбыт заготовки. К непроизводственной сфере относят: отрасли услуг жилищнокоммунальное хозяйство бытовое обслуживание; образование и научное отрасли социального обслуживания здравоохранение культура...
33606. Урбанизация и особенности расселения населения 61 KB
  В настоящее время более половины населения мира живет в сельской местности. В России учитывается не только число жителей но и показатель занятости населения промышленность сфера обслуживания. Процесс роста городского населения увеличения числа городов и их укрупнения возникновения сетей и систем городов а также повышения роли городов в современном мире называется урбанизацией.
33607. Инновационный процесс 103.5 KB
  Таким образом в условиях рыночной экономики такой неотъемлемый критерий инновации как практическая воплощенность новой идеи оказывается тесно связанным с критерием ее коммерческой реализуемости посредством появления на рынке новой инновационной продукции или услуг. Деятельность организации по осуществлению инновационных процессов называется инновационной деятельностью. Основные составляющие инновационной деятельности: Научноисследовательские и опытноконструкторские работы НИОКР Технологические работы подготовка производства и...