Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости
arc:=0
else
arc:=7-x/y;
end;
end;
end;
procedure con(var l1,l2:prec);
var t:prec;
begin
if l2=nil then exit;
if l1=nil then
begin
l1:=l2;
exit;
end;
l1^.p^.n:=l2;
l2^.p^.n:=l1;
t:=l1^.p;
l1^.p:=l2^.p;
l2^.p:=t;
end;
procedure cut(l1,l2:prec);
var t:prec;
begin
l1^.p^.n:=l2;
l2^.p^.n:=l1;
t:=l1^.p;
l1^.p:=l2^.p;
l2^.p:=t;
end;
procedure grah(var st:prec);
var r,t,d:prec;
f:integer;
begin
if st^.n=st^.p then exit;
r:=st;
t:=st;
f:=0;
while (f<=0) or (t<>r) do
begin
if t^.n=t^.p then break;
if ((t^.n^.x-t^.p^.x)*(t^.y-t^.p^.y)>(t^.x-t^.p^.x)*(t^.n^.y-t^.p^.y))
or (((t^.n^.x-t^.p^.x)*(t^.y-t^.p^.y)=(t^.x-t^.p^.x)*(t^.n^.y-t^.p^.y))
and (abs(t^.y-t^.p^.y)+abs(t^.y-t^.n^.y)=abs(t^.p^.y-t^.n^.y)) and(abs(t^.x-t^.p^.x)+abs(t^.x-t^.n^.x)=abs(t^.p^.x-t^.n^.x)))
then
begin
if t=r then
begin
dec(f);
r:=t^.n;
end;
d:=t;
t:=t^.n;
cut(t,d);
t:=t^.p;
con(gs,d);
end else
begin
t:=t^.n;
if t=r then inc(f);
end;
end;
st:=t;
end;
procedure proc(var ls:prec);
var t,l1,l2,r,l:prec;
x,y:tp;
f:boolean;
begin
if ls^.n=ls
then exit;
l1:=ls;
l2:=ls;
repeat
l1:=l1^.n;
l2:=l2^.p;
until (l1=l2) or (l1^.p=l2);
l1:=ls;
cut(l1,l2);
proc(l1);
proc(l2);
if l1^.n=l1 then
if l2^.n<>l2 then begin
t:=l1;
l1:=l2;
l2:=t;
end else
begin
l1^.n:=l2;
l1^.p:=l2;
l2^.n:=l1;
l2^.p:=l1;
ls:=l1;
exit;
end;
x:=(l1^.x+l1^.n^.x+l1^.n^.n^.x)/3;
y:=(l1^.y+l1^.n^.y+l1^.n^.n^.y)/3;
r:=l1;
r^.a:=arc((r^.x-x),(r^.y-y));
t:=l1;
repeat
t^.a:=arc((t^.x-x),(t^.y-y));
if (r^.a>t^.a) or ((r^.a=t^.a) and (abs(r^.x-x)+abs(r^.y-y)>abs(t^.x-x)+abs(t^.y-y))) then r:=t;
t:=t^.n;
until t=l1;
l1:=r;
l:=l2;
r:=l;
t:=r;
f:=false;
repeat
if (t.x-x)*(r^.y-y)>(r^.x-x)*(t.y-y) then r:=t;
if (t.x-x)*(l^.y-y)<(l^.x-x)*(t.y-y) then l:=t;
f:=f or((x-t^.p^.x)*(t^.y-t^.p^.y)>(t^.x-t^.p^.x)*(y-t^.p^.y));
t:=t^.n;
until (t=l2);
if (l^.x=x) and (l^.y=y) then r:=r^.n
else l:=l^.n;
if f then
begin
cut(l,r);
if l<>r then con(gs,l);
end;
l2:=r;
r:=l2;
r^.a:=arc((r^.x-x),(r^.y-y));
t:=l2;
repeat
t^.a:=arc((t^.x-x),(t^.y-y));
if (r^.a>t^.a) or ((r^.a=t^.a) and (abs(r^.x-x)+abs(r^.y-y)>abs(t^.x-x)+abs(t^.y-y))) then r:=t;
t:=t^.n;
until t=l2;
l2:=r;
l1^.p^.n:=nil;
l2^.p^.n:=nil;
r:=l1;
l:=l2;
ls:=nil;
while (r<>nil) and (l<>nil) do
begin
if
(r^.a begin
t:=r;
r:=r^.n;
if r<>nil then r^.p:=t^.p;
add(ls,t); end
else begin
t:=l;
l:=l^.n;
if l<>nil then l^.p:=t^.p;
add(ls,t); end; end; if r<>nil
then begin
r^.p^.n:=r;
con(ls,r); end; if l<>nil
then begin
l^.p^.n:=l;
con(ls,l); end; grah(ls); end; begin
time:=now; kkk:=0; repeat while
sn<>nil do begin
tt:=sn^.n;
dispose(sn);
sn:=tt; end; ls:=nil; gs:=nil; tt:=cn; if tt=nil
then exit; while
tt<>nil do begin
new(t);
t^.x:=tt^.x;
t^.y:=tt^.y;
tt:=tt^.n;
add(ls,t); end; proc(ls); t:=ls; if t<>nil
then repeat
r:=t;
writ(t^.x,t^.y);
t:=t^.n;
dispose(r); until
t=ls; t:=gs; if t<>nil
then repeat
r:=t;
t:=t^.n;
dispose(r); until
t=gs; inc(kkk); until
now-time>timew;
str((now-time)/kkk*24*60*60:0:6,strr);
TimeL.Caption:=strr+'s';
PaintBox1.Refresh; end; {Div end} procedure
TForm1.CircleClick(Sender: TObject); var i:integer; t:pr; begin while
cn<>nil do begin
t:=cn^.n;
dispose(cn);
cn:=t; end; while
sn<>nil do begin
t:=sn^.n;
dispose(sn);
sn:=t; end; mx:=0; my:=0; for i:=1
to QRandom.Value do begin
new(t);
t^.n:=cn;
cn:=t;
t^.x:=Range.Value*sin(i);
t^.y:=Range.Value*cos(i); if
mx if
my end; if mx<>0
then mx:=0.8*(Width div 2)/mx; if my<>0
then my:=0.8*(Height div 2)/my;
PaintBox1.Refresh; end; { online} procedure
TForm1.Button2Click(Sender: TObject); label onend; type
prec=^TTree;
TTree=record
x,y:tp;
l,r,u,n,p,gr:prec;
kl,kr:integer; end; var
ls,t,p,n,gr:prec; procedure
disp(t:prec); begin if t=nil
then exit;
disp(t^.l);
disp(t^.r);
dispose(t); end; function
max(a,b:integer):integer; begin if a>b
then max:=a
else max:=b; end; procedure
getleft(m,n:prec;var l:prec); var
fm,fn,f:boolean; begin l:=nil; if
((p^.x=m^.x) and (p^.y=m^.y)) or ((p^.x=n^.x) and (p^.y=n^.y)) then
exit; if
((p^.x=m^.n^.x) and (p^.y=m^.n^.y)) or ((p^.x=n^.n^.x) and
(p^.y=n^.n^.y)) then exit; if
(m^.n=m) or
(((m^.n^.x-p^.x)*(m^.y-p^.y)=(m^.x-p^.x)*(m^.n^.y-p^.y)) and
(abs(m^.x-p^.x)=abs(m^.n^.x-p^.x)+abs(m^.n^.x-m^.x)) and
(abs(m^.y-p^.y)=abs(m^.n^.y-p^.y)+abs(m^.n^.y-m^.y))) or
(((m^.p^.x-p^.x)*(m^.y-p^.y)>(m^.x-p^.x)*(m^.p^.y-p^.y)) and
((m^.n^.x-p^.x)*(m^.y-p^.y)>(m^.x-p^.x)*(m^.n^.y-p^.y))) then begin l:=m; exit; end; if
(n^.n=n) or
(((n^.n^.x-p^.x)*(n^.y-p^.y)=(n^.x-p^.x)*(n^.n^.y-p^.y)) and
(abs(n^.x-p^.x)=abs(n^.n^.x-p^.x)+abs(n^.n^.x-n^.x)) and
(abs(n^.y-p^.y)=abs(n^.n^.y-p^.y)+abs(n^.n^.y-n^.y))) or
(((n^.p^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(n^.p^.y-p^.y)) and
((n^.n^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(n^.n^.y-p^.y))) then begin l:=n; exit; end; if
m^.n<>m then begin
fm:=((m^.n^.x-p^.x)*(m^.y-p^.y)>(m^.x-p^.x)*(m^.n^.y-p^.y)) or
((m^.p^.x-p^.x)*(m^.y-p^.y)<(m^.x-p^.x)*(m^.p^.y-p^.y));
fn:=((n^.n^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(n^.n^.y-p^.y)) or
((n^.p^.x-p^.x)*(n^.y-p^.y)<(n^.x-p^.x)*(n^.p^.y-p^.y));
f:=(m^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(m^.y-p^.y); if
(m^.l<>nil)