Скан Грехама
Клацніть, щоб додати точку · перетягніть, щоб пересунути
Опукла оболонка набору точок — це найменший опуклий багатокутник, що містить їх усі: форма, яку утворює гумка, натягнута на крайні точки. Обчислення опуклих оболонок є фундаментальною задачею обчислювальної геометрії з застосуваннями у виявленні зіткнень, аналізі форм, плануванні маршрутів та русі роботів. Оптимальна складність у найгіршому випадку — O(n log n) для n вхідних точок; алгоритми, чутливі до виводу, як сканування Джарвіса, досягають O(nh), де h — кількість вершин оболонки.
Симулятор реалізує і анімує три класичних алгоритми. Сканування Грехема сортує всі точки за полярним кутом, потім обходить їх зі стеком, відкидаючи точки, що утворюють правий поворот. Сканування Джарвіса («загортання подарунку») щоразу обирає точку з найменшим кутом проти годинникової стрілки. Quickhull рекурсивно ділить набір точок, вибираючи найвіддаленішу точку над кожним ребром.
Яка часова складність сканування Грехема, Джарвіса і Quickhull?
Сканування Грехема виконується за O(n log n) через початкове кутове сортування; обхід зі стеком — O(n). Сканування Джарвіса — O(nh): у найгіршому випадку O(n²), але для типових наборів точок O(n log n). Quickhull має O(n log n) у середньому, але O(n²) у найгіршому. Алгоритм Чана (1996) досягає оптимального O(n log h) у всіх випадках.
Як тест на векторний добуток визначає ліві та праві повороти?
Для трьох точок A, B, C обчислюється 2D-векторний добуток (B−A)×(C−A) = (Bx−Ax)(Cy−Ay) − (By−Ay)(Cx−Ax). Додатне значення означає, що C ліворуч від напрямленої прямої A→B (поворот проти годинникової стрілки); від'ємне — праворуч (відкидається у скануванні Грехема); нуль — колінеарність. Цей O(1) тест орієнтації є основним примітивом у всіх алгоритмах опуклої оболонки.
Яка нижня межа складності обчислення опуклої оболонки?
Задача має нижню межу Ω(n log n) в моделі алгебраїчного дерева рішень, що доводиться зведенням до сортування: числа x₁, …, xn розміщуються як точки (xᵢ, xᵢ²) на параболі — їхня опукла оболонка повертає їх у відсортованому порядку. Це робить сканування Грехема асимптотично оптимальним.
У 2D-фізиці ігор два опуклих багатокутника можна перевірити на перетин за допомогою теореми про розділяючу вісь (SAT): якщо існує пряма, що розділяє дві оболонки, вони не перетинаються, і достатньо перевірити лише O(h₁+h₂) кандидатів на осі. Алгоритм GJK розширює це на 3D. Обидва — SAT і GJK — є основними інструментами у Unity, Bullet та інших фізичних рушіях.
Точки, що лежать на ребрі оболонки, але не є вершинами (колінеарні між двома вершинами), можуть включатися або виключатися залежно від варіанту алгоритму. Стандартне сканування Грехема виключає їх під час дедуплікації при сортуванні. Деякі застосування (обчислення площі) воліють включати всі граничні точки. Тест на нульовий векторний добуток потрібно обробляти обережно.
Алгоритм Чана (1996) досягає O(n log h) — це оптимально. Підхід Чана: вгадати h у подвоювальних фазах (спробувати h = 2, 4, 8, …), запустити мінісканування Джарвіса, що зупиняється після h кроків, використовуючи попередньо обчислені скануванн Грехема на групах n/h точок. Коли вгадане h збігається з реальним, алгоритм завершується. Кожна фаза коштує O(n log h); подвоєння додає лише константний множник.
У 2D лінійному програмуванні допустима область, задана m нерівностями, — це опуклий багатокутник. Оптимальний розв'язок завжди знаходиться у вершині допустимого многогранника. Метод симплексу обходить вершини; методи внутрішньої точки — перетинають interior. У вищих вимірах перебір вершин допустимого многогранника еквівалентний обчисленню опуклої оболонки.
У 3D опукла оболонка n точок — це опуклий многогранник із щонайбільше O(n) вершинами, ребрами та гранями (формула Ейлера V − E + F = 2). Алгоритми включають 3D-сканування Грехема, «розділяй і пануй» O(n log n) та QuickHull3D (бібліотека qhull, 1996) — практичний стандарт, що використовується у SciPy, MATLAB та ігрових рушіях.
Дублікати (ідентичні координати) потрібно обробляти явно; більшість реалізацій видаляє їх за O(n log n) на етапі попередньої обробки. У скануванні Грехема дублікати породжують нульові векторні добутки та неоднозначність при кутовому сортуванні. У скануванні Джарвіса вибір дубліката як наступної вершини оболонки може спричинити нескінченний цикл.
Існує класична двоїстість: 2D-діаграма Вороного n точок еквівалентна проекції 3D-опуклої оболонки тих самих точок, підняти на параболоїд z = x² + y². Нижня оболонка після проекції дає тріангуляцію Делоне, а її двоїстий граф — діаграму Вороного. Будь-який O(n log n)-алгоритм 3D-опуклої оболонки дає O(n log n)-алгоритм Вороного.
У методі опорних векторів (SVM) класифікатор із максимальним зазором між двома класами відповідає пошуку найближчих точок на опуклих оболонках двох класів. Опорні вектори SVM — це саме ті точки оболонки, що найближчі до розділяючої гіперплощини. Опукла оболонка також застосовується у глибині даних (метод Тьюкі), виявленні аномалій і багатоцільовій оптимізації.