Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




02.07.2022


02.07.2022


02.07.2022


01.07.2022


01.07.2022





Яндекс.Метрика

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

21.06.2022

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

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

Применение

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

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