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

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

Применение

Первый алгоритм ^{[ уточнить ]} сортирует набор точек ${\displaystyle S}$ за счёт увеличения ${\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}$ .

Литература

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