Тема: побудова мінімальної опуклої оболонки мовою C++.

Мета

• навчальна:
  • ознайомити з методами побудови мінімальної опуклої оболонки;
  • навчити програмно будувати мінімальну опуклу оболонку;
• розвивальна:
  • розвивати логічне та образне мислення, самостійність;
  • виробити вміння застосовувати набуті знання до практичних завдань;
  • активізувати пізнавальні здібності учнів;
  • розвивати увагу та пам’ять;
• виховна:
  • виховувати наполегливість, інтерес до пізнання;
  • сприяти розумінню необхідності знань з іформатики.

Учень повинен пояснювати:

• що таке опукла оболонка;
• які існують способи для побудови опуклої оболонки;
• суть методу Грехема;
• суть методу Джарвіса.

• використовувати набуті знання на практиці;
• будувати опуклу оболонку методом Грехема;
• будувати опуклу оболонку методом Джарвіса;
• створювати фрагменти коду для реалізації алгоритмів Грехема та Джарвіса;
• програмно втілити алгоритми побудови опуклої оболонки мовою C++;
• дотримуватися санітарно-гігієнічних норм і норм техніки безпеки праці.

Обладнання: комп’ютери зі встановленими ОС та середовищем програмування мовою C++ або стійким сполученням з Інтернетом для роботи з середовищами програмування у режимі online.

Структура уроку

1. Організаційний момент.
2. Актуалізація опорних знань.
3. Вивчення нового матеріалу.
4. Інструктаж з ТБ.
5. Закріплення вивченого матеріалу.
6. Підбиття підсумків уроку.
7. Домашнє завдання.

Хід уроку

1. Організаційний момент
Вітання з класом. Перевірка присутності і готовності учнів до уроку. Перевірка виконання домашнього завдання.

2. Актуалізація опорних знань

1. Що таке ламана?
2. Що таке многокутник?
3. Який многокутник називають опуклим?
4. Що таке додатний напрям вимірювання кутів?
5. Назвіть алгоритми упорядкування лінійних масивів?
6. Що таке (часова) ефективність алгоритму?

3. Вивчення нового матеріалу

Означення 1. Для довільної непорожньої скінченної множини точок S (зображено блакитними кругами на малюнках нижче) означимо такі поняття (зображено оранжевими ліліями):

• оболонка — довільна замкнена лінія без самоперетинів і така, що всі точки S лежать всередині цієї кривої;

  

• опукла оболонка — оболонка, що обмежує опуклу фігуру;

  

• мінімальна опукла оболонка (МОО) — опукла оболонка, що лежить всередині всіх опуклих оболонок.

  

Примітка 1. В означенні 1 замість запроваджені поняття можна означити не як лінії, а як замкнені множини точок, обмежені відповідними лініями.

Примітка 2. Мінімальна опукла оболонка є:

Пошук мінімальної опуклої оболонки зводиться до відбору й упорядкування потрібних точок з S. Упорядкування є необхідним, бо результатом виконання алгоритму має бути послідовність вершин опуклого многокутника у порядку обходу по периметру.

Зазвичай накладають додаткову умову на порядок розташування вершин: напрямок обходу многокутника має бути додатним. Інакше кажучи, у додатному напрямку вимірювання кутів: у тому напрямку, в якому поворот від додатного напрямку осі абсцис Ox до додатного напрямку осі ординат Oy. Зазвичай це є напрямом проти напряму руху годинникової стрілки.

Побудову мінімальної опуклої оболонки — традиційне завдання обчислювальної геометрії. Для неї існує багато різних алгоритмів, з яких далі розглянуто два: Грехема (Graham scan) і Джарвіса (Jarvis march).

Алгоритм Грехема (Graham scan)

1. Знайти стартову точку A, що належить до мінімальної опуклої оболонки. Наприклад, точку з найменшою абсцисою x. Якщо таких точок кілька, то потрібно вибрати ту, в якої ордината y найменша. Цю точку (будемо називати її стартової) перемістити у початок списку. Всю подальшу роботу проводити без зміни початкового масиву точок. Для цього використати непряму адресацію за допомогою списку (втіленого вектором) p для номерів точок (їхніх позиції) у масиві координат a.

2. Упорядкувати дані точки, крім стартової, таким чином, щоб при переході до кожної наступної точки рух вектора, спрямованого зі стартової точки у поточну точку, відбувався у додатному напрямку вимірювання кутів або без повороту зі зменшенням відстані до стартової точки.
   
   Запровадити таке упорядкування на множині даних точок, відмінних від стартової: будемо казати, що B < C, якщо поворот від напрямку вектора AB до напрямку вектора BС можна здійснити у додатному напрямку на кут, менший від розгорнутого. Побутовою мовою: якщо точка С перебуває ліворуч при русі вздовж вектора AB.

   
   
   Якщо точки A, B, С розташовано на одній прямій, то будемо казати, що B < C, якщо AB > AC (записано нерівність між довжинами відрізків).
   
   Для порівняння точок можна використати функцію rotate, яка повертає таке значення:

   • абсолютна величина — подвоєна площа трикутника з вершинами A(a_x, a_y), B(b_x, b_y), C(c_x, c_y);

   • знак — додатний лише у тому випадку, коли поворот від напрямку вектора AB до напрямку вектора BС — можна здійснити у додатному напрямку на кут, менший від розгорнутого.

   int rotate(point a, point b, point c)
   { return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x); }

   Інакше кажучи, ця функція повертає аплікату (кординату z) векторного добутку AB × BС.
   
   Інший спосіб порівняння даних точок — це порівняння кутів повороту від додатного напрямку осі абсцис до напрямку вектора, спрямованого зі стартової точки у поточну. Значення цього кута при даному виборі стартової точки (найменша ордината при найменшій абсцисі) лежить у проміжку (−π/2, π/2]. Інакше кажучи, можна порівнювати полярні координати з полюсом у стартовій точці:

   • кут від додатного напряму осі абсцис до напряму вектора, спрямованого від стартової точки у поточну (кутовий аргумент);

   • відстань від стартової точки до поточної.

   Ця альтернатива пов'язана з використанням наближеного обчислення значення трансцендентної функції арктангенсу. На відміну від використаних арифметичних дій, які для цілих чисел дають точний результат. Точний результат без обмеження на діапазон значень цілих чисел у мові C++.
   
   Для упорядкування можна застосовувати будь-який алгоритм, заснований на попарному порівнянні елементів. Наприклад, швидкий метод Хоара. Результат упорядкування можна проілюструвати таким малюнком.

   

   Якщо сполучити точки в отриманому порядку, то отримаємо багатокутник, який може виявитися неопуклим.

   

   У разі розташування даних точок на одній прямій багатокутник може виродитися у відрізок.

3. Якщо дані точки розташовано на одній прямій, вивести список з двох крайніх точок і припинити виконання алгоритму.

4. Видалити з переліку вершин ті, в яких внутрішній кут отриманого много­кутника більший від розгорнутого. Для цього використати стек S (список) і розташувати у ньому дві вершини (стартову й першу з упорядкованих), які гарантовано входять у мінімальну опуклу оболонку. Потім переглянути всі інші вершини і відстежити напрямок повороту в них щодо останніх двох вершин у стеці S:

   • якщо напрям повороту від’ємний, «зрізати кут» видаленням зі стеку останньої вершини;

   • якщо напрям повороту додатний, поточну вершина занести у стек.

У результаті стек S міститиме шукану послідовність вершин у потрібній нам орієнтації, що визначає мінімальної опуклої оболонки.

— див. код, у якому:

• список координат точок не зазнає змін, а використано масив P для подання перестановки індексів, що відповідає упорядкуванню;

• замість порівняння відстані для точок однієї прямої використано суму модулів абсолютних координат, що пропорційна відстані (коефіцієнт пропорційності для різних кутів нахилу різний.;

Приклад даних (кількість точок і їхні координати)

10
110 66  88 108  88 30  85 83  60 72  53 45  32 72  39 108  11 58  25 8

узгоджено з наступним малюнком, у якому нижній лівий кут відповідає початку координат (0,0).

Відповідь — список номерів точок вхідних даних — у цьому випадку така:

8 9 2 0 1 7

Інакше кажучи, вершини мінімальної опуклої оболонки у цьому випадку такі: (11, 58), (25, 8), (88, 30), (110, 66), (88, 108), (39, 108).

Іншого прикладу вхідних даних:

4
0 0  4 4  8 8  2 2

— всі точки на одній прямій — відповідь така:

0 2

Інакше кажучи, мінімальна опукла оболонка у цьому випадку є відрізком з такими кінцями: (0, 0), (8, 8).

Примітка 3. Деякі публікації в інтернеті не містять перевірки, чи розташовано всі точки на одній прямій, а подані у них демонстраційні розв'язання у цьому випадку або дають хибну відповідь, або аварійно завершуються. З іншого боку, в завданнях олімпіад з інформатики, що вимагають побудови мінімальної лінійної оболонки, деякі тести описують розташування точок на одній прямій.

Складність першого й останнього кроків алгоритму є лінійною за кількістю вершин n. Хоча в останньому випадку є вкладений цикл, але кожну вершину всередині цього циклу лише один раз буде занесено у стек, і не більше одного разу її буде видалено з нього. Складність всього алгоритму визначається другим кроком — упорядкуванням, складність якого O(n ∙ log n) і є складністю усього алгоритму.

Чи можна поліпшити (асмптотичну) ефективність алгоритму? Виявляється, що ні. Якщо алгоритм упорядкування засновано на попарному порівнянні, то доведено, що таку оцінка в загальному випадку покращити не можливо. З цієї точки зору алгоритм Грехема оптимальний. Проте у нього є не дуже добра особливість: він не є адаптивним в тому сенсі, що не важливо, скільки вершин в результаті увійде в оболонку (три, п'ять, десять або більше). Все одно час буде лінійно-логарифмічним. Таку адаптивність має алгоритм Джарвіса, до розгляду якого ми переходимо.

Алгоритм Джарвіса (Jarvis march) (інша назва — алгоритм загортання подарунків) концеп­туально влаштований простіше, ніж алгоритм Грехема, бо не вимагає упоряд­кування:

1. Знайти стартову точку, що належить до мінімальної опуклої оболонки, й оголосити її поточною.

2. Якщо всі дані точки розташовано на одній прямій, вивести список з двох крайніх точок і припинити виконання алгоритму.

3. Шукати найправішу точку (з даних) щодо поточної точки й робити її поточною доти, поки поточною знову виявиться стартова вершина. Точку, яку вже зарахували до оболонки, надалі можна не враховувати.

Примітка 4. Вислів: «шукати найправішу точку» є описом побутовою мовою, що неприйнятно для строгого викладу. Ці слова потрібно тлумачити так: серед усіх векторів, спрямованих з поточної точки у решту даних точок, вибрати той, поворот від якого у додатному напрямку вимірювання кутів до напрямку інших векторів можна здійснити на кут, менший від розгорнутого. Якщо таких векторів кілька, то вибрати найдовший. Його кінець і буде наступною вершиною мінімальної опуклої оболонки. Порівняння векторів можна здійснити, використавши запроваджену вище функцію rotate.

Наступний малюнок ілюструє дію коду.

Оцінимо складність алгоритму Джарвіса. Перший крок линійний за n. Другий крок містить вкладений цикл. Кількість зовнішніх ітерацій у ньому дорівнює кількості вершин h у мінімальній лінійній оболонці, кількість внутрішніх ітерацій не перевищує n. Отже, складність всього алгоритму дорівнює O(hn). Незвичайним у цій формулі є те, що складність визначається не лише довжиною вхідних даних, але і довжиною вихідних даних. Маємо алгоритм, чутливий до вихідних даних (output-sensitive algorithm).

У найгіршому випадку всі дані точки належать до мінімальної опуклої оболонки, тоді h = n і складність підскакує до квадратичної. У найкращому випадку h = 3 і складність стає лінійної. Заздалегідь зрозуміти, який випадок нас чекає кожного разу, не так просто. Можна лише виходити з характеру завдання:

• якщо точок багато і вони рівномірно заповнюють деяку область, то (можливо) алгоритм Джарвіса буде працювати швидше;

• якщо точки зосереджено на межі області, то швидше працюватиме алгоритм Грехема.

Пошук мінімальної опуклої оболонки пов'язаний з розпізнаванням образів, кластери­зацією і є допоміжним засобом при вирішенні складніших завдань обчислю­вальної геометрії. Він має тривимірне узагальнення.

4. Інструктаж з ТБ
5. Закріплення вивченого матеріалу

Завдання 1. Програмно втілити алгоритм Грехема.

Завдання 2. Програмно втілити алгоритм Джарвіса.

Зберегти файли з назвами Ваше_прізвище_1 і Ваше_прізвище_2 у теці, вказаній вчителем.

6. Підбиття підсумків уроку
Виставлення оцінок.

7. Домашнє завдання
Вивчити матеріал уроку. При потребі доробити завдання, виконання яких розпочато у класі. Підготуватися до відповіді на такі питання:

1. Що таке опукла оболонка? Навести приклади.
2. Що таке мінімальна опукла оболонка? Навести приклади.
3. Подати алгоритм Грехема розмовною мовою.
4. Проілюструвати частину алгоритму Грехема кодом.
5. Яка ефективність алгоритму Грехема?
6. Подати алгоритм Джарвіса розмовною мовою.
7. Проілюструвати частину алгоритму Джарвіса кодом.
8. Яка ефективність алгоритму Грехема?
9. Порівняти алгоритми побудови мінімальної опуклої оболонки.

Створити розв'язання такої задачі.

Завдання. Задано n точок координатної площини. Довільним чином одну з них видаляються. Знайти середнє число вершин опуклої оболонки множини з n−1 точки, що залишилися.

Вхідні дані. Перший рядок містить єдине число n (3 ≤ n ≤ 200 000) — початкову кількість точок у множині. У наступних n рядках задано пари чисел, які не перевищують по модулю 10⁹ — координати точок. Ніякі дві точки не збігаються.

Вихідні дані. Вивести середнє число вершин в опуклій оболонці множини без однієї точки у вигляді нескоротного дробу p/q.

У роботі використано матеріали сторінки https://habr.com/post/144921/. Демон­стра­ційні розв'язання мовою C++ переклав Олександр Рудик.