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

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

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

Применение

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

Для построения верхней оболочки точки множества [math]\displaystyle{ S }[/math] упорядочивается в соответствии с возрастанием абсциссы и после совершается работа полученных данных по алгоритму Грэхема. Для этого алгоритм Эндрю использует стек [math]\displaystyle{ x_0, x_1, \dots, x_t }[/math] для хранения текущей верхней оболочки. Точка [math]\displaystyle{ x_t }[/math] считается находящейся на вершине стека. После окончания работы алгоритма стек содержит верхнюю оболочку множества [math]\displaystyle{ S }[/math].

Литература

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