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

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

x:=x0+Trunc(t^.x*mx);

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;

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

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

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

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