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

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

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

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

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

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

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

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

Посилання

1. [1] [Архівовано 11 березня 2014 у Wayback Machine.], Monotone chain