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<abs(t^.x) then mx:=abs(t^.x);
if my<abs(t^.y) then my:=abs(t^.y);
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<abs(t^.x) then mx:=abs(t^.x);
if my<abs(t^.y) then my:=abs(t^.y);
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.
F. P. Preparata, M. I. Shamos, Computational geometry, Ph. D. Thesis, Dept. Of Comput. Sci., Yale Univ., 1985.
[1]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).