Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости
while sn<>nil do
begin
tt:=sn^.n;
dispose(sn);
sn:=tt;
end;
st:=nil;
s:=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;
ins(st,t);
end;
if st=nil then exit;
l:=st;
r:=st;
t:=st;
repeat
if
(r^.x if
(l^.x>t^.x) or ((l^.y>t^.y)and(l^.x=t^.x)) then l:=t;
t:=t^.next; until
t=st; if
l^.x=r^.x then begin
str((now-time)*24*60*60:0:2,strr);
TimeL.Caption:=strr+'s';
writ(l^.x,l^.y); if
not((r^.x=l^.x)and(r^.y=l^.y)) then writ(r^.x,r^.y);
t:=l;
while l<>nil do
begin
t:=l;
cut(l,t);
dispose(t); end;
exit; end; t:=l; t:=st; repeat repl: if
st=nil then break;
p:=t;
t:=t^.next; if
(p^.x-l^.x)*(r^.y-l^.y)<=(p^.y-l^.y)*(r^.x-l^.x) then
begin
cut(st,p);
ins(s,p);
goto repl;
end; until
t=st;
sort2(s,s^.prev); if st <>
nil then begin
sort(st,st^.prev);
t:=st^.prev;
st^.prev^.next:=s;
st^.prev:=s^.prev;
s^.prev^.next:=st;
s^.prev:=t;
st:=st^.prev;
grah(s); end; t:=s; repeat
writ(t^.x,t^.y);
t:=t^.next; until
t=s; while
s<>nil do begin t:=s;
cut(s,t);
dispose(t); end; inc(kkk); until
now-time>timew;
str((now-time)/kkk*24*60*60:0:6,strr);
TimeL.Caption:=strr+'s';
PaintBox1.Refresh; end; { end graham} procedure
TForm1.PaintBox1MouseDown(Sender: TObject; Button: TMouseButton; Shift:
TShiftState; X, Y: Integer); var t:pr; begin
new(t);
t^.x:=(x-x0)/mx;
t^.y:=(y-y0)/my;
t^.n:=cn; cn:=t;
Canvas.Pen.Color :=clBlue;
Canvas.Ellipse(x-1,y-1,x+1,y+1); end; {-------------------------------------} procedure
TForm1.QButtonClick(Sender: TObject); type
prec=^rec;
rec=record
x,y:tp;
p,n:prec; end;
list=record
b,e:prec;
end; var
t,bb,ee:prec;
ll,gr,ls:list; procedure
cut(var l:list;t:prec); begin if
t^.p<>nil then t^.p^.n:=t^.n
else l.b:=t^.n; if
t^.n<>nil then t^.n^.p:=t^.p
else l.e:=t^.p; end; procedure
clr(var l:list); begin l.b:=nil; l.e:=nil; end; procedure
add(var l:list;var t:prec); begin t^.n:=nil; if
l.e<>nil then l.e^.n:=t; t^.p:=l.e; l.e:=t; if l.b=nil
then l.b:=t; end; procedure
con(var l1,l2:list); begin if
l2.b<>nil then l2.b^.p:=l1.e else exit; if
l1.b<>nil then l1.e^.n:=l2.b else begin
l1:=l2; exit; end;
l1.e:=l2.e; end; procedure
proc(var ls:list;b,e:prec); var
l1,l2:list;
r,t,m:prec; begin if
ls.b=nil then exit; t:=ls.b; m:=t; while
t<>nil do begin if
(b^.x-m^.x)*(b^.y+m^.y)+(m^.x-e^.x)*(e^.y+m^.y)<(b^.x-t^.x)*(b^.y+t^.y)+(t^.x-e^.x)*(e^.y+t^.y)
then
m:=t;
t:=t^.n; end;
cut(ls,m); clr(l1); t:=ls.b; while
t<>nil do begin
r:=t^.n; if
(t^.x-b^.x)*(m^.y-b^.y)>(m^.x-b^.x)*(t^.y-b^.y) then
begin
cut(ls,t);
add(l1,t) end;
t:=r; end; clr(l2); t:=ls.b; while
t<>nil do begin
r:=t^.n; if
(t^.x-e^.x)*(m^.y-e^.y)<(m^.x-e^.x)*(t^.y-e^.y) then
begin
cut(ls,t);
add(l2,t) end;
t:=r; end;
con(gr,ls);
proc(l1,b,m);
proc(l2,m,e); ls:=l1;
add(ls,m);
con(ls,l2); end; begin
time:=now; kkk:=0; repeat while
sn<>nil do begin
tt:=sn^.n;
dispose(sn);
sn:=tt; end; clr(ls); clr(gr); 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; bb:=ls.b; t:=ls.b; while
t<>nil do begin if
(t^.x
then bb:=t;
t:=t^.n; end;
cut(ls,bb); t:=ls.b; while
(t<>nil) and ((t^.x=bb^.x)and(t^.y=bb^.y)) do
t:=t^.n; ee:=t; while
t<>nil do begin if
((t^.x<>bb^.x)or(t^.y<>bb^.y)) and
(((t^.x-bb^.x)*(ee^.y-bb^.y)<(ee^.x-bb^.x)*(t^.y-bb^.y)) or
(((t^.x-bb^.x)*(ee^.y-bb^.y)=(ee^.x-bb^.x)*(t^.y-bb^.y))and(abs(ee^.x-bb^.x)+abs(ee^.y-bb^.y)
then ee:=t;
t:=t^.n; end; if
(ee<>nil) and ((ee^.x<>bb^.x) or (ee^.y<>bb^.y))
then begin
cut(ls,ee);
proc(ls,bb,ee);
clr(ll);
add(ll,bb);
con(ll,ls);
add(ll,ee);
ls:=ll; end else begin
clr(ls);
add(ls,bb);
dispose(ee); end; t:=ls.b; while
ls.b<>nil do begin if
(t=ls.b)or(t=ls.e)or
((t^.x-t^.p^.x)*(t^.n^.y-t^.p^.y)<>(t^.n^.x-t^.p^.x)*(t^.y-t^.p^.y))
then writ(t^.x,t^.y);
t:=t^.n;
dispose(ls.b);
ls.b:=t; end; t:=gr.b; while
t<>gr.e do begin
t:=t^.n;
dispose(t^.p); end; if t<>nil
then dispose(t); inc(kkk); until
now-time>timew;
str((now-time)/kkk*24*60*60:0:6,strr);
TimeL.Caption:=strr+'s';
PaintBox1.Refresh; end; {------------------------------} procedure
TForm1.DiveRuleClick(Sender: TObject); type
prec=^rec;
rec=record
a,x,y:tp;
p,n:prec; end; var
r,t,ls,gs:prec; procedure
add(var l:prec;t:prec); begin if l=nil
then begin l:=t;
t^.n:=l;
t^.p:=l end else begin
t^.n:=l;
t^.p:=l^.p;
l^.p^.n:=t;
l^.p:=t; end; end; function
arc(x,y:extended):extended; begin if
abs(x)>abs(y) then begin if
x>0 then
arc:=1+y/x else
arc:=5+y/x; end else begin if
y>0 then
arc:=3-x/y else begin