Поиск по сайту.

Другие алгоритмы.

Математика:
Вычислительная геометрия:
Построение выпуклой оболочки.



Алгоритм Грэхема.

Автор: Unknown.
Перевод: Кантор И.

     Первым шагом определяем самую нижнюю-правую точку, пусть это - точка 0. Она наверняка лежит на оболочке ( Шаг А ). Следующая стадия - сортировка всех точек по углу между осью Х и линией ( 0 , эта точка ). Точка с самым большим углом отправляется в стек за точкой 0 ( Шаг B ).

     Дальше все точки обрабатываются по очереди, начиная от самого меньшего угла ( точка 1 ) и до тех пор, пока не достигнута точка 9. Процесс состоит из теста, является ли строго левым поворот к новой точке на пути: верхняя-1 точка стека - верхняя точка стека - тестируемая точка. Если это так, тогда она идет в стек и переходим к следующей точке. Если нет - то убираем вершину стека и повторяем проверку с той же точкой. Это проиллюстрировано в шагах C-L. Иногда из стека приходтся убирать несколько точек подряд, так как они последовательно не проходят проверки: обнаруживается правый поворот. Вообще говоря, в алгоритме еще нужна проверка на то, нет ли поворота _обратно_, и в этом случае точку следует оставить: мы имеем прямую. Но это уже мелочи.







Псевдокод.

Найти нижнюю ( правую ) точку.
Пометить ее p(0)
Отсортировать все остальные точки по углу относительно p(0)
    Если одинаковый угол - по расстоянию.
    помечаем их p(1),...,p(n-1)
    Стек S=(p(n-1),p(0))=(p(t-1),p(i)); t - индекс вершины
    i = 1
    while i < n do
        if p(i) строго слева от ( p(t-1),p(t) )
        then Push(S,i) and i = i + 1
        else Pop(S)


Вверх по странице, к оглавлению и навигации.