Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости
l^.u:=c^.u;
end;
end else
begin
dl:=l;
l^.u:=nil;
end;
c^.l:=dr;
if dr<>nil then dr^.u:=c;
dr:=c;
dr^.u:=nil;
continue;
end;
end;
l:=l^.u;
end;
balance(r,dl,true);
end;
procedure add(p:prec);
var l,r,d:prec;
begin
getleft(t,n,l);
if l<>nil then
begin
getright(t,n,r);
if (n=r) or ((n^.x-r^.x)*(l^.y-r^.y)<(l^.x-r^.x)*(n^.y-r^.y)) then
begin
cutl(r,d,t);
n:=r;
cutr(l,t,d);
ins(l,p);
end else
begin
cutr(l,t,d);
balance(l^.n,d,true);
p^.l:=t;
t^.u:=p;
t:=d;
cutl(r,d,t);
p^.r:=t;
t^.u:=p;
t:=p;
p^.u:=nil;
balance(p,t,true);
end;
l^.n:=p;
p^.p:=l;
r^.p:=p;
p^.n:=r;
end;
end;
begin
kkk:=0;
time:=now;
repeat
while sn<>nil do
begin
tt:=sn^.n;
dispose(sn);
sn:=tt;
end;
ls:=nil;
gr:=nil;
tt:=cn;
if tt=nil then goto onend;
while tt<>nil do
begin
new(t);
t^.gr:=gr;
gr:=t;
t^.x:=tt^.x;
t^.y:=tt^.y;
t^.n:=ls;
ls:=t;
tt:=tt^.n;
end;
t:=ls;
ls:=ls^.n;
t^.u:=nil;
t^.l:=nil;
t^.r:=nil;
t^.n:=t;
t^.p:=t;
t^.kl:=0;
t^.kr:=0;
n:=t;
while ls<>nil do
begin
p:=ls;
ls:=ls^.n;
add(p);
end;
p:=n;
repeat
writ(p^.x,p^.y);
t:=p;
p:=p^.n;
until p=n;
while gr<>nil do
begin
p:=gr;
gr:=gr^.gr;
dispose(p);
end;
onend:
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.Button1Click(Sender: TObject);
begin
while sn<>nil do
begin
tt:=sn^.n;
dispose(sn);
sn:=tt;
end;
while cn<>nil do
begin
tt:=cn^.n;
dispose(cn);
cn:=tt;
end;
halt;
end;
procedure TForm1.Button3Click(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;
new(t);
t^.n:=cn;
cn:=t;
t^.x:=0;
t^.y:=10;
if
mx if
my for i:=2
to QRandom.Value do begin
new(t);
t^.n:=cn;
cn:=t;
t^.x:=i-2;
t^.y:=exp(i-2)/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; end. 1
F. P. Preparata, M. I. Shamos, Computational geometry, Ph. D.
Thesis, Dept. Of Comput. Sci., Yale Univ., 1985. S.
G. Akl and G. T. Toussaint, Efficient convex hull algorithm for
pattern recognition aplications, Proc.
4th
Int’l Joint Conf. On Pattern Recognition,
Kyoto, Japan, pp. 483-487 (1978). 2
A. Rosenfeld, Picture
Processing by Computers,
Academic Press, New York, 1969. 3
H. Freeman, Computer
processing of line-drawing images, Comput.
Surveys 6, 57-97
(1974). 4
P. McMullen and G. C.
Shephard, Convex
Polytopes and the Upper Bound Conjecture,
Cambridge University Press, Cambridge, England, 1971 5
R. L. Graham, An efficient
algorithm for determining the convex hull of a finite planar set,
Info, Proc. Lett.
1,
132-133 (1972). 6
A. M. Andrew, Another
efficient algorithm for convex hulls in two dimension, Info.
Proc. Lett. 9,
216-219 (1979). 7
M. I. Shamos, Computational geometry, Ph. D. Thesis, Dept. Of
Comput. Sci., Yale Univ., 1978. 8
F. P. Preparata, An optimal
real time algorithm for planar convex hulls, Comm.
ACM
22, 402-405 (1979).Литература