Опукла оболонка

Множина E крайніх точок S представляє собою найменшу підмножину S, яка має властивість: conv(E) = conv(S), при чому Е в точності співпадає з множиною вершин conv(S).

Для знаходження опуклої оболонки скінченної множини необхідно виконати наступне:

1. Визначити крайні точки;

2. Впорядкувати ці точки так, щоб вони утворювали опуклий многокутник.

Теорема. Точка p не є крайньою плоскої опуклої множини S тоді і тільки тоді, коли вона лежить в деякому трикутнику, вершинами якого є точки з S, але сама вона не є вершиною цього трикутника.

Існує O(N3) трикутників, які визначаються N точками множини S. Отже за час O(N3) можна визначити, чи є задана точка крайньою. Повторення цієї процедури для всіх N точок множини S вимагає часу O(N4).

Точка P не є крайньою, оскільки вона лежить всередині трикутника P1P2P3.

Теорема. Промінь, який виходить із внутрішньої точки обмеженої замкненої фігури F, перетинає границю F рівно в одній точці.

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

Теорема. В якості внутрішньої точки q можна взяти центроїд довільних трьох неколінеарних точок.

Для цього беруться дві довільні точки та шукається така третя точка з інших N - 2 точок, яка не лежить на прямій, що визначається першими двома.

Задача. На площині дано дві точки p1 та p2. Яка з цих точок має більший полярний кут?

p2 утворює з віссю Ох строго менший полярний кут, ніж p1 тоді і тільки тоді, коли трикутник (O, p2, p1) має строго додатню площу (або точка P1 лежить зліва від прямої OP2).

Приклад. Площа трикутника OP2P1 дорівнює Ѕ * P2  P1 = Ѕ * = Ѕ * (30 - 6) = 12.

Метод обхода Грехема

Знайдемо внутрішню точку O множини точок S та перетворимо координати інших точок так, щоб знайдена внутрішня точка стала початком координат. Впорядкуємо лексикографічно N точок у відповідності зі значеннями полярного кута та відстані від початку координат (при цьому переводити координати точок до полярної системи координат не треба).

Алгоритм Грехема полягає в однократному перегляді впорядкованої послідовності точок, в процесі якої видаляються внутрішні точки. Перегляд починається з точки p0, в якості якої можна взяти саму праву (з максимальною абсцисою) з найменшою ординатою (вона точно належить опуклій оболонці). Послідовно перевіряються трійки точок p1p2p3, при чому

1. Якщо трійка p1p2p3 утворює правий поворот, то видалити вершину p2 та перевірити трійку p0p1p3.

2. Якщо трійка p1p2p3 утворює лівий поворот, то продовжувати перегляд, перейшовши до трійки p2p3p4.

Оболонка Грехема