Выпуклые оболочки / Алгоритмы построения ВО 1
.docАлгоритмы построения выпуклой оболочки
1. Обход Грэхема (точки упорядочены относительно центроида)
v := начало; w := Pred(v); f := false;
{f=’подошли к точке начало в прямом направлении’}
while ( Next(v) начало) or not f
do
if (Next(v)=w) then f := true;
if тройка(v, Next(v), Next(Next(v)) = левый поворот
then v := Next(v) {движение вперёд}
else Delete (Next(v));
v := Pred(v)
fi
od;
2. Вариант обхода Грэхема для случая, когда
точки p1, p2, …, pn упорядочены по углу относительно крайней точки p0.
Create(St);
St p0; St p1; St p2;
for i := 3 to n
do
while тройка(Pred_Top(St), Top(St), pi ) = не левый поворот
do
Pop(St)
od {while};
St pi;
od {for}
3. Алгоритм QuickCH
func QuickCH(S; L, R) : List;
Begin
if S={L, R} then return (L, R) (* CH из одного ребра*)
else
H := самая_дальняя_точка (S; L, R);
S1:=точки из S, расположенные слева от прямой LH или на ней;
S2:=точки из S, расположенные справа от прямой HR или на ней;
return QuickCH(S1; L, H){QuickCH(S2; H, R) – H}
fi
end
Здесь знак обозначает операцию конкатенации двух последовательностей.
Алгоритмы построения выпуклой оболочки
1. Обход Грэхема (точки упорядочены относительно центроида)
v := начало; w := Pred(v); f := false;
{f=’подошли к точке начало в прямом направлении’}
while ( Next(v) начало) or not f
do
if (Next(v)=w) then f := true;
if тройка(v, Next(v), Next(Next(v)) = левый поворот
then v := Next(v) {движение вперёд}
else Delete (Next(v));
v := Pred(v)
fi
od;
2. Вариант обхода Грэхема для случая, когда
точки p1, p2, …, pn упорядочены по углу относительно крайней точки p0.
Create(St);
St p0; St p1; St p2;
for i := 3 to n
do
while тройка(Pred_Top(St), Top(St), pi ) = не левый поворот
do
Pop(St)
od {while};
St pi;
od {for}
3. Алгоритм QuickCH
func QuickCH(S; L, R) : List;
Begin
if S={L, R} then return (L, R) (* CH из одного ребра*)
else
H := самая_дальняя_точка (S; L, R);
S1:=точки из S, расположенные слева от прямой LH или на ней;
S2:=точки из S, расположенные справа от прямой HR или на ней;
return QuickCH(S1; L, H){QuickCH(S2; H, R) – H}
fi
end
Здесь знак обозначает операцию конкатенации двух последовательностей.