Випукла оболонка: Огортання множини точок у найменшій кількості поворотів

Найменша сумка, що вміщує всі точки

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

Основний тест, який повинен проходити будь-який алгоритм обчислення кулі

Усі три алгоритми спираються на одну основну операцію: якщо задано три точки a, b та c, то як потрібно повернутися від точки b при ходінні з точки a до точки c? Знаки плоскій крижової (cross) добуткової функції відповідають на це в одному множенні та відніманні:

cross(a, b, c) = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) cross > 0 → проти годинникової стрілки (лівий) поворот в точці b cross < 0 → за годинниковою стрілкою (правий) поворот в точці b cross == 0 → точки a, b та c лежать на одній прямій

cross(a, b, c) = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)

cross > 0   →  counter-clockwise (left) turn at b
cross < 0   →  clockwise (right) turn at b
cross == 0  →  a, b, c are collinear

Алгоритм Грэма: сортування один раз, обвід один раз

Алгоритм Рональда Грэма 1972 року спочатку обирає точку з найнижчою y-координатою (розв’язуючи рівність за найнижчою x) як фіксований поворот, потім сортує всі інші точки за кутом параболи відносно цієї поворотної точки. Потім алгоритм обводить відсортовані точки один раз, підтримуючи стек кандидатів оболонки та видаляючи з верху стека будь-яку точку, додавання якої створило б гонку за годинниковою стрілкою (неліву) поворот:

поворот = точка з найнижчою y-координатою (у разі рівності – з найнижчою x) точки = всі інші точки, відсортовані за кутом параболи відносно поворотної точки стек = [поворот, точки[0]] для p у точках[1:]: поки перетин(стек[-2], стек[-1], p) <= 0: // не лівий поворот стек.pop() стек.push(p) повернути стек // оболонка, в порядку Вартість сортування становить O(n log n), а обвід сам по собі – O(n) — кожна точка додається один раз і видаляється з стека не більше одного разу — тому весь алгоритм має складність O(n log n), повністю домінований початковим сортуванням, незалежно від того, скільки точок опиниться на кінцевій оболонці.

pivot = point with lowest y (then lowest x)
points = all other points, sorted by polar angle around pivot
stack = [pivot, points[0]]
for p in points[1:]:
    while cross(stack[-2], stack[-1], p) <= 0:   // not a left turn
        stack.pop()
    stack.push(p)
return stack                                     // the hull, in order

Алгоритм «Марша Джера:» обертка подарунка, по одній грані за раз

Алгоритм «обертки подарунка» (R. A. Jarvis, 1973) працює абсолютно інакше: починаючи з найлівішої точки, він повторювано знаходить одну точку, таку що всі інші точки лежать проти годинникової стрілки від краю від цієї поточної точки – буквально обертає стрічку навколо зовнішньої сторони набору, по одній грані за раз – доки не повернеться до початку.

поточна = найлівіша точка оболочка = [поточна] повторювати: кандидат = будь-яка інша точка для кожної точки p: якщо переріз(поточна, кандидат, p) < 0: // p більш годинниковий кандидат = p // → кандидат стає p оболочка.додати(кандидат) поточна = кандидат поки поточна не дорівнює оболочці[0] Знаходження кожної наступної вершини оболонки коштує O(n), а їх є h вершин, щоб знайти, тому загальна вартість становить O(nh). Коли оболонка має дуже мало вершин відносно n – поширена ситуація для точок, вибірконих всередині фігури, а не на її межі – алгоритм «Марша Джера» може обійти Graham scan з його O(n log n). Коли h наближається до n, це деградує до O(n²) і Graham scan комфортно перемагає.

current = leftmost point
hull = [current]
repeat:
    candidate = any other point
    for each point p:
        if cross(current, candidate, p) < 0:      // p is more clockwise
            candidate = p                          // → candidate becomes p
    hull.push(candidate)
    current = candidate
until current == hull[0]

Quickhull: розділяй та володарюй

Quickhull (розроблений незалежно кількома авторами, популяризований Барбером, Добкіном і Хугдампаа у 1996 році) використовує свою структуру безпосередньо з алгоритму сортування QuickSort. Почніть із двох екстремальних точок – найлівішої та найправішої, які гарантовано знаходяться на оболонці, та розділіть усі інші точки на два набори: лівий і правий від цієї лінії. Для кожного боку знайдіть точку, найвіддаленішу від лінії – вона також повинна знаходитися на оболонці, і рекурсивно застосуйте Quickhull до двох менших трикутників, які це створює, відкидаючи будь-яку точку всередині трикутника, утвореного до цього моменту, оскільки точка всередині трикутника, що лежить на межі відомої оболонки, ніколи не може бути на самій оболонці.

Середня продуктивність Quickhull становить O(n log n), а агресивне відкидання внутрішніх точок часто робить його найшвидшим з трьох алгоритмів у практичних умовах на типових, неагресивних даних – але, як і звичайний QuickSort, його найгірший випадок (уважно розташована, ворожа точка) погіршується до O(n²).

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Convex Hull і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.