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

Цей алгоритм сортує набір точок ${\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}$.

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

Вхідні дані: список 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)
• Чаднов Р. В. Алгоритмы построения выпуклых оболочек и их применение в ГИС и САПР — Томск: Томск. гос. ун-т. Факультет информатики, 2004.- 61 с.
• A. M. Andrew, «Another Efficient Algorithm for Convex Hulls in Two Dimensions», Info. Proc. Letters 9, 216—219 (1979).