Алгоритм Эндрю (Glikjnmb |u;jZ)

Алгоритм Эндрю — алгоритм построения выпуклой оболочки в двумерном пространстве, модификация алгоритма Грэхема.

В отличие от алгоритма Грэхема, использует лексикографическое упорядочение точек по координатам, за счёт этого алгоритму не требуется использовать вещественные числа и тригонометрические функции. Алгоритм по отдельности вычисляет верхнюю и нижнюю оболочки из последовательных цепей точек. В сущности, алгоритм Эндрю является частным случаем алгоритма Грэхема, когда центральная точка выбирается бесконечно удалённой в отрицательном направлении по оси ординат, так что в этом случае упорядоченность по абсциссе совпадает с упорядоченностью по полярному углу.

Применение

Первый алгоритм^{[уточнить]} сортирует набор точек $S$ за счёт увеличения $x$, а затем $y$. Пусть минимальные и максимальные координаты $x$ будут $x_{min}$ и $x_{max}$. Очевидно что у первой из точек $x=x_{min}$. Но могут быть и другие точки с этой минимальной $x$-координатой. Найдём такие точки в которых есть два минимума и два максимума и соединим их отрезком. Остальное множество точек разделяется на два, в зависимости от того с какой стороны от этой прямой точки лежат. Таким образом мы можем определить новую нижнюю и новую верхнюю линии. В совокупности эти линии и дают требуемую оболочку.

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

Литература

• Препарата Ф., Шеймос М. Вычислительная геометрия: введение. — Москва: Мир, 1989.
• Чаднов Р. В. Алгоритмы построения выпуклых оболочек и их применение в ГИС и САПР. Дипломная работа. Томск: Томский государственный университет, 2004