Первым шагом определяем самую нижнюю-правую точку, пусть это - точка 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.  8  Комментарии к статье  8 8  Обсудить в чате