Перевод: Кантор И. e-mail: algolist@mail.ru web: iliakan@gmail.com
Этот алгоритм за O( n ) времени 'выправляет' впуклости многоугольника, то есть замкнутой непересекающейся ломаной, строя таким образом выпуклую оболочку.
Что интересно, точки могут поступать по мере выполнения алгоритма, и их количество может быть заранее не известно. Главное, чтобы ломаная не пересекалась.
Для начала объявим вспомогательную функцию, которая для любой тройки x, y, z будет f>0, f=0 или f<0 в зависимости от того, находится ли z справа, на одной линии или слева от линии (x, y).
Пусть ломаная задана точками v1, ..., vm.
Алгоритм начинает с пустого дека D.
Дек - список с операциями:
push v - положить элемент на верх дека,
insert v - положить элемент под низ дека,
pop - убрать верхний элемент дека,
remove - удалить нижний элемент дека.
Псевдокод.
Шаг 1:
Ввод v1, v2, v3;
if (v1,v2,v3)>0
then {push v1; push v2;}
else {push v2; push v1;}
push v3; insert v3;
Шаг 2:
Ввод v;
until ((v,db,db+1)<0 or (dt-1,dt,c)<0) do { ввод v };
Шаг 3:
until ((dt-1,dt,v)>0) do pop;
push v;
Шаг 4:
until ((v,db,db+1)>0) do remove;
insert v;
Идти на Шаг 2.
