Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости
y:=y0+Trunc(t^.y*my);
Canvas.MoveTo(x,y);
while t<>nil do
begin
x:=x0+Trunc(t^.x*mx);
y:=y0+Trunc(t^.y*my);
Canvas.LineTo(x,y);
t:=t^.n;
end;
x:=x0+Trunc(sn^.x*mx);
y:=y0+Trunc(sn^.y*my);
Canvas.LineTo(x,y);
end;
Canvas.Pen.Color :=clBlue;
t:=cn;
while t<>nil do
begin
x:=x0+Trunc(t^.x*mx);
y:=y0+Trunc(t^.y*my);
Canvas.Ellipse(x-1,y-1,x+1,y+1);
t:=t^.n;
end;
end;
end;
procedure TForm1.RandomButtonClick(Sender: TObject);
var
i:integer;
t:pr;
begin
randomize();
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:=random(2*Range.Value+1)-Range.Value;
t^.y:=random(2*Range.Value+1)-Range.Value;
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; procedure
TForm1.ResetButtonClick(Sender: TObject); var 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:=1; my:=1;
PaintBox1.Refresh; end; procedure
TForm1.FormCreate(Sender: TObject); begin cn:=nil; sn:=nil; mx:=1; my:=1; with
PaintBox1 do begin
x0:=Width div 2;
y0:=Height div 2; end; end; procedure
TForm1.GrahamButtonClick(Sender: TObject); label repl; type
prec=^rec;
rec=record
x,y:tp;
next,prev:prec; end; var
st,t,s,l,r,p:prec; procedure
inss(var st:prec;t,d:prec); begin if st=nil
then begin st:=t;
d^.next:=t;
st^.prev:=d; end else begin
st^.prev^.next:=t;
d^.next:=st;
t^.prev:=st^.prev;
st^.prev:=d; end; end; procedure
ins(var st,t:prec); begin if st=nil
then begin st:=t;
st^.next:=t;
st^.prev:=t; end else begin
t^.next:=st;
t^.prev:=st^.prev;
st^.prev^.next:=t;
st^.prev:=t; end; end; procedure
cut(var st,t:prec); begin if
st^.next=st then st:=nil else begin if
t=st then
st:=t^.next;
t^.next^.prev:=t^.prev;
t^.prev^.next:=t^.next; end; end; procedure
sort(var b:prec;e:prec); var p,q:prec; x:tp; begin if b=e
then exit; if
b^.next=e then begin if
(b^.x>e^.x) or ((b^.x=e^.x)and(b^.y>e^.y)) then begin
x:=b^.x;
b^.x:=e^.x;
e^.x:=x;
x:=b^.y;
b^.y:=e^.y;
e^.y:=x; end; exit; end; p:=b; q:=e; while
(p<>q)and(p^.next<>q) do begin
p:=p^.next;
q:=q^.prev; end; if p=q
then q:=q.next;
p^.next:=b;
b^.prev:=p;
q^.prev:=e;
e^.next:=q;
sort(b,p);
sort(q,e); p:=b; b:=nil; while
(p<>nil)and(q<>nil) do begin if
(p^.x>q^.x)or((p^.x=q^.x)and(p^.y>q^.y)) then begin
e:=q;
cut(q,e);
ins(b,e); end
else begin
e:=p;
cut(p,e);
ins(b,e); end; end; if p<>nil
then begin e:=p;
inss(b,e,e^.prev); end; if q<>nil
then begin e:=q;
inss(b,e,e^.prev); end; end; procedure
sort2(var b:prec;e:prec); var p,q:prec; x:tp; begin if b=e
then exit; if
b^.next=e then begin if
(b^.x begin
x:=b^.x;
b^.x:=e^.x;
e^.x:=x;
x:=b^.y;
b^.y:=e^.y;
e^.y:=x; end; exit; end; p:=b; q:=e; while
(p<>q)and(p^.next<>q) do begin
p:=p^.next;
q:=q^.prev; end; if p=q
then q:=q.next;
p^.next:=b;
b^.prev:=p;
q^.prev:=e;
e^.next:=q;
sort2(b,p);
sort2(q,e); p:=b; b:=nil; while
(p<>nil)and(q<>nil) do begin if
(p^.x begin
e:=q;
cut(q,e);
ins(b,e); end
else begin
e:=p;
cut(p,e);
ins(b,e); end; end; if p<>nil
then begin e:=p;
inss(b,e,e^.prev); end; if q<>nil
then begin e:=q;
inss(b,e,e^.prev); end; end; procedure
grah(var st:prec); var
r,t,g:prec; f:integer; begin if
st^.next=st^.prev then exit; r:=st; t:=st; f:=0; while
(f<=0) or (t<>r) do begin if
(t^.next^.x-t^.prev^.x)*(t^.y-t^.prev^.y)>=(t^.x-t^.prev^.x)*(t^.next^.y-t^.prev^.y)
then begin
if t=r then
begin
dec(f);
r:=t^.next;
end;
t:=t^.prev;
g:=t^.next;
cut(st,g);
dispose(g); end
else begin
t:=t^.next;
if t=r then inc(f); end; end; end; begin
time:=now; kkk:=0;