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.
|
