:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » Выпуклая оболочка » Алгоритм Грэхема
  Алгоритм Грэхема



Перевод: Кантор И.
e-mail: algolist@mail.ru
web: iliakan@gmail.com

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

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








  Псевдокод



1. Найти нижнюю ( правую ) точку.
    Пометить ее p(0)
    Отсортировать все остальные точки по углу относительно p(0),
      Если одинаковый угол - по расстоянию от p(0).
      помечаем их p(1),...,p(n-1)
2. Заметим, что получившиеся точки образуют простой
   многоугольник, т.е ломаную без самопересечений.
   
   Применяем 'обход Грэхема':
   
      Стек 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)

Обход Грэхема - основная часть метода, которая используется и в других алгоритмах. Он, как и алгоритм Мелькмана, позволяет получить из простого многоугольника его выпуклую оболочку за Theta(n) операций.

Если многоугольник хранится в виде кольцевого списка точек, то более удобен следующий псевдокод:

v := НАЧАЛО кольца; w := ПРЕД(v); f:= false;

while (СЛЕД(v) =/= НАЧАЛО or f == false ) do {
    if (СЛЕД(v)==w) then f:= true;
    if (три точки v, СЛЕД(v), СЛЕД(СЛЕД(v))
        образуют левый поворот) then v:=СЛЕД(v);
    else {
        Удалить СЛЕД(v);
        v := ПРЕД(v);
    }
}

Функция, определяющая наличие левого поворота:

// isLeft(): tests if a point is Left|On|Right of an infinite line.
//    Input:  three points P0, P1, and P2
//    Return: >0 for P2 left of the line through P0 and P1
//            =0 for P2 on the line
//            <0 for P2 right of the line
isLeft( coord *p0, coord *p1, coord *p2 ) {
    return (p1->x - p0->x)*(p2->y - p0->y) - (p2->x - p0->x)*(p1->y - p0->y);
}

При реализации необходимо правильно поддерживать случай удаления начальной вершины. Она обязательно должна проверяться в конце алгоритма(что может привести к многочисленным отходам назад с удалением), но при этом должно корректно проводиться сравнение в первом while.