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

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

repeat

while sn<>nil do

begin

tt:=sn^.n;

dispose(sn);

sn:=tt;

end;


st:=nil;

s:=nil;

tt:=cn;

if tt=nil then exit;

while tt<>nil do

begin

new(t);

t^.x:=tt^.x;

t^.y:=tt^.y;

tt:=tt^.n;

ins(st,t);

end;

if st=nil then exit;

l:=st;

r:=st;

t:=st;

repeat

if (r^.x

if (l^.x>t^.x) or ((l^.y>t^.y)and(l^.x=t^.x)) then l:=t;

t:=t^.next;

until t=st;

if l^.x=r^.x then

begin

str((now-time)*24*60*60:0:2,strr);

TimeL.Caption:=strr+'s';

writ(l^.x,l^.y);

if not((r^.x=l^.x)and(r^.y=l^.y)) then writ(r^.x,r^.y);

t:=l;

while l<>nil do

begin

t:=l;

cut(l,t);

dispose(t);

end;

exit;

end;

t:=l;

t:=st;

repeat

repl:

if st=nil then break;

p:=t;

t:=t^.next;

if (p^.x-l^.x)*(r^.y-l^.y)<=(p^.y-l^.y)*(r^.x-l^.x) then

begin

cut(st,p);

ins(s,p);

goto repl;

end;

until t=st;

sort2(s,s^.prev);

if st <> nil then

begin

sort(st,st^.prev);

t:=st^.prev;

st^.prev^.next:=s;

st^.prev:=s^.prev;

s^.prev^.next:=st;

s^.prev:=t;

st:=st^.prev;

grah(s);

end;

t:=s;

repeat

writ(t^.x,t^.y);

t:=t^.next;

until t=s;

while s<>nil do

begin

t:=s;

cut(s,t);

dispose(t);

end;

inc(kkk);

until now-time>timew;

str((now-time)/kkk*24*60*60:0:6,strr);

TimeL.Caption:=strr+'s';

PaintBox1.Refresh;

end;

{ end graham}

procedure TForm1.PaintBox1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

var

t:pr;

begin

new(t);

t^.x:=(x-x0)/mx;

t^.y:=(y-y0)/my;

t^.n:=cn;

cn:=t;

Canvas.Pen.Color :=clBlue;

Canvas.Ellipse(x-1,y-1,x+1,y+1);

end;

{-------------------------------------}

procedure TForm1.QButtonClick(Sender: TObject);

type prec=^rec;

rec=record

x,y:tp;

p,n:prec;

end;

list=record

b,e:prec;

end;

var t,bb,ee:prec;

ll,gr,ls:list;


procedure cut(var l:list;t:prec);

begin

if t^.p<>nil then t^.p^.n:=t^.n

else l.b:=t^.n;

if t^.n<>nil then t^.n^.p:=t^.p

else l.e:=t^.p;

end;

procedure clr(var l:list);

begin

l.b:=nil;

l.e:=nil;

end;

procedure add(var l:list;var t:prec);

begin

t^.n:=nil;

if l.e<>nil then l.e^.n:=t;

t^.p:=l.e;

l.e:=t;

if l.b=nil then l.b:=t;

end;

procedure con(var l1,l2:list);

begin

if l2.b<>nil then l2.b^.p:=l1.e else exit;

if l1.b<>nil then l1.e^.n:=l2.b else

begin

l1:=l2;

exit;

end;

l1.e:=l2.e;

end;

procedure proc(var ls:list;b,e:prec);

var l1,l2:list;

r,t,m:prec;

begin

if ls.b=nil then exit;

t:=ls.b;

m:=t;

while t<>nil do

begin

if (b^.x-m^.x)*(b^.y+m^.y)+(m^.x-e^.x)*(e^.y+m^.y)<(b^.x-t^.x)*(b^.y+t^.y)+(t^.x-e^.x)*(e^.y+t^.y) then

m:=t;

t:=t^.n;

end;

cut(ls,m);

clr(l1);

t:=ls.b;

while t<>nil do

begin

r:=t^.n;

if (t^.x-b^.x)*(m^.y-b^.y)>(m^.x-b^.x)*(t^.y-b^.y) then

begin

cut(ls,t);

add(l1,t)

end;

t:=r;

end;

clr(l2);

t:=ls.b;

while t<>nil do

begin

r:=t^.n;

if (t^.x-e^.x)*(m^.y-e^.y)<(m^.x-e^.x)*(t^.y-e^.y) then

begin

cut(ls,t);

add(l2,t)

end;

t:=r;

end;

con(gr,ls);

proc(l1,b,m);

proc(l2,m,e);

ls:=l1;

add(ls,m);

con(ls,l2);

end;

begin

time:=now;

kkk:=0;

repeat


while sn<>nil do

begin

tt:=sn^.n;

dispose(sn);

sn:=tt;

end;

clr(ls);

clr(gr);

tt:=cn;

if tt=nil then exit;

while tt<>nil do

begin

new(t);

t^.x:=tt^.x;

t^.y:=tt^.y;

tt:=tt^.n;

add(ls,t);

end;


bb:=ls.b;

t:=ls.b;

while t<>nil do

begin

if (t^.x

then bb:=t;

t:=t^.n;

end;

cut(ls,bb);

t:=ls.b;

while (t<>nil) and ((t^.x=bb^.x)and(t^.y=bb^.y)) do

t:=t^.n;

ee:=t;

while t<>nil do

begin

if ((t^.x<>bb^.x)or(t^.y<>bb^.y)) and

(((t^.x-bb^.x)*(ee^.y-bb^.y)<(ee^.x-bb^.x)*(t^.y-bb^.y)) or

(((t^.x-bb^.x)*(ee^.y-bb^.y)=(ee^.x-bb^.x)*(t^.y-bb^.y))and(abs(ee^.x-bb^.x)+abs(ee^.y-bb^.y)

then ee:=t;

t:=t^.n;

end;

if (ee<>nil) and ((ee^.x<>bb^.x) or (ee^.y<>bb^.y)) then

begin

cut(ls,ee);

proc(ls,bb,ee);

clr(ll);

add(ll,bb);

con(ll,ls);

add(ll,ee);

ls:=ll;

end else

begin

clr(ls);

add(ls,bb);

dispose(ee);

end;

t:=ls.b;

while ls.b<>nil do

begin

if (t=ls.b)or(t=ls.e)or

((t^.x-t^.p^.x)*(t^.n^.y-t^.p^.y)<>(t^.n^.x-t^.p^.x)*(t^.y-t^.p^.y)) then writ(t^.x,t^.y);

t:=t^.n;

dispose(ls.b);

ls.b:=t;

end;

t:=gr.b;

while t<>gr.e do

begin

t:=t^.n;

dispose(t^.p);

end;

if t<>nil then dispose(t);

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.DiveRuleClick(Sender: TObject);

type

prec=^rec;

rec=record

a,x,y:tp;

p,n:prec;

end;


var r,t,ls,gs:prec;

procedure add(var l:prec;t:prec);

begin

if l=nil then

begin

l:=t;

t^.n:=l;

t^.p:=l

end else

begin

t^.n:=l;

t^.p:=l^.p;

l^.p^.n:=t;

l^.p:=t;

end;

end;

function arc(x,y:extended):extended;

begin

if abs(x)>abs(y) then

begin

if x>0 then

arc:=1+y/x

else

arc:=5+y/x;

end

else

begin

if y>0 then

arc:=3-x/y

else

begin

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

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

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

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