Xreferat.com » Рефераты по математике » Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости

Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости

c^.u^.r:=l;

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).

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: