Алгоритм Ендрю

Зображення перебігу алгоритму

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

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

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

Застосування

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

Для побудови верхньої оболонки точки множини $S$ впорядковується відповідно до зростання абсциси. Після цього відбувається обробка отриманих даних за алгоритмом Грехема. Для цього алгоритм Ендрю використовує стек $x_{0},x_{1},\dots ,x_{t}$ для зберігання поточної верхньої оболонки. Точка $x_{t}$ вважається, що знаходиться на вершині стека. Після закінчення роботи алгоритму стек містить верхню оболонку множини $S$.

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

Псевдокод

Вхідні дані: список P точок на площині.

Передумова: повинно бути не менше 3 точок.

Відсортуйте точки P за координатою x (у разі рівності, сортуйте за координатою y).

Ініціалізуйте U та L як порожні списки.
Списки будуть містити вершини верхньої та нижньої оболонок відповідно.

for i = 1, 2, ..., n:
     while L містить принаймні дві точки та послідовність останніх двох точок
             L і точка P[i] не робить повороту проти годинникової стрілки:
         вилучити останню точку з L
     додати P[i] до L

for i = n, n-1, ..., 1:
     while U містить щонайменше дві точки та послідовність останніх двох точок
             U і точка P[i] не робить повороту проти годинникової стрілки:
         видалити останню точку з U
     додати P[i] до U

Видаліть останню точку кожного списку (це те саме, що перша точка іншого списку).
Об'єднайте L і U, щоб отримати опуклу оболонку точок P.
У підсумку точки будуть перераховані в порядку проти годинникової стрілки.

Див. також

• Монотонний многокутник

Література

• Препарата Ф., Шеймос М. Вычислительная геометрия: введение. — Москва: Мир, 1989. (с. 132—133)
• Чаднов Р. В. Алгоритмы построения выпуклых оболочек и их применение в ГИС и САПР [Архівовано 14 березня 2014 у Wayback Machine.] — Томск: Томск. гос. ун-т. Факультет информатики, 2004.- 61 с.
• A. M. Andrew, «Another Efficient Algorithm for Convex Hulls in Two Dimensions», Info. Proc. Letters 9, 216—219 (1979).