Відкрити головне меню
Зображення перебігу алгоритму
Верхня (червона) та нижня (синя) опуклі оболонки

Алгоритм Ендрю, також відомий як монотонний ланцюг — алгоритм побудови опуклої оболонки на площині, є модифікацією алгоритму Грехема.

На відміну від алгоритму Грехема, в якому побудова здійснюється за допомогою стеку, використовує лексикографічне впорядкування точок по координатах, що дозволяє алгоритму не використовувати дійсні числа і тригонометричні функції. Алгоритм окремо обчислює верхню і нижню оболонки з послідовних ланцюгів точок. Фактично, алгоритм Ендрю є окремим випадком алгоритму Грехема, коли центральна точка вибирається нескінченно віддаленою у від'ємному напрямку по осі ординат, так що в цьому випадку впорядкування по абсцисі збігається з впорядкуванням по полярному куту.

Зміст

ЗастосуванняРедагувати

Цей алгоритм сортує набір точок   за рахунок збільшення по осі  , а у разі, коли у точок координати   однакові, то по  . Нехай мінімальні і максимальні координати   будуть   і  . Очевидно, що у першій з точок  . Але можуть бути й інші точки з цієї мінімальної  -координатою. Знайдемо такі точки в яких є два мінімуму і два максимуму і з'єднаємо їх відрізком. Остання множина точок ділиться на дві, залежно від того з якого боку від цієї прямої точки розташовані. Таким чином ми можемо визначити нову нижню і нову верхню лінії. Об'єднання цих ліній дає шукану опуклу оболонку.

Для побудови верхньої оболонки точки множини   впорядковується відповідно до зростання абсциси. Після цього відбувається обробка отриманих даних за алгоритмом Грехема. Для цього алгоритм Ендрю використовує стек   для зберігання поточної верхньої оболонки. Точка   вважається, що знаходиться на вершині стека. Після закінчення роботи алгоритму стек містить верхню оболонку множини  .

Даний алгоритм можна запрограмувати на багатьох мовах програмування.[1]

Див. такожРедагувати

ЛітератураРедагувати

ПосиланняРедагувати

  1. [1], Monotone chain