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

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

if abs(y)=0 then

arc:=0

else

arc:=7-x/y;

end;

end;

end;

procedure con(var l1,l2:prec);

var t:prec;

begin

if l2=nil then exit;

if l1=nil then

begin

l1:=l2;

exit;

end;

l1^.p^.n:=l2;

l2^.p^.n:=l1;

t:=l1^.p;

l1^.p:=l2^.p;

l2^.p:=t;

end;


procedure cut(l1,l2:prec);

var t:prec;

begin

l1^.p^.n:=l2;

l2^.p^.n:=l1;

t:=l1^.p;

l1^.p:=l2^.p;

l2^.p:=t;

end;


procedure grah(var st:prec);

var r,t,d:prec;

f:integer;

begin

if st^.n=st^.p then exit;

r:=st;

t:=st;

f:=0;

while (f<=0) or (t<>r) do

begin

if t^.n=t^.p then break;

if ((t^.n^.x-t^.p^.x)*(t^.y-t^.p^.y)>(t^.x-t^.p^.x)*(t^.n^.y-t^.p^.y))

or (((t^.n^.x-t^.p^.x)*(t^.y-t^.p^.y)=(t^.x-t^.p^.x)*(t^.n^.y-t^.p^.y))

and (abs(t^.y-t^.p^.y)+abs(t^.y-t^.n^.y)=abs(t^.p^.y-t^.n^.y)) and(abs(t^.x-t^.p^.x)+abs(t^.x-t^.n^.x)=abs(t^.p^.x-t^.n^.x)))

then

begin

if t=r then

begin

dec(f);

r:=t^.n;

end;

d:=t;

t:=t^.n;

cut(t,d);

t:=t^.p;

con(gs,d);

end else

begin

t:=t^.n;

if t=r then inc(f);

end;

end;

st:=t;

end;

procedure proc(var ls:prec);

var t,l1,l2,r,l:prec;

x,y:tp;

f:boolean;

begin

if ls^.n=ls

then exit;


l1:=ls;

l2:=ls;

repeat

l1:=l1^.n;

l2:=l2^.p;

until (l1=l2) or (l1^.p=l2);

l1:=ls;

cut(l1,l2);

proc(l1);

proc(l2);

if l1^.n=l1 then

if l2^.n<>l2 then begin

t:=l1;

l1:=l2;

l2:=t;

end else

begin

l1^.n:=l2;

l1^.p:=l2;

l2^.n:=l1;

l2^.p:=l1;

ls:=l1;

exit;

end;


x:=(l1^.x+l1^.n^.x+l1^.n^.n^.x)/3;

y:=(l1^.y+l1^.n^.y+l1^.n^.n^.y)/3;


r:=l1;

r^.a:=arc((r^.x-x),(r^.y-y));

t:=l1;

repeat

t^.a:=arc((t^.x-x),(t^.y-y));

if (r^.a>t^.a) or ((r^.a=t^.a) and (abs(r^.x-x)+abs(r^.y-y)>abs(t^.x-x)+abs(t^.y-y))) then r:=t;

t:=t^.n;

until t=l1;

l1:=r;

l:=l2;

r:=l;

t:=r;

f:=false;

repeat

if (t.x-x)*(r^.y-y)>(r^.x-x)*(t.y-y) then r:=t;

if (t.x-x)*(l^.y-y)<(l^.x-x)*(t.y-y) then l:=t;

f:=f or((x-t^.p^.x)*(t^.y-t^.p^.y)>(t^.x-t^.p^.x)*(y-t^.p^.y));

t:=t^.n;

until (t=l2);


if (l^.x=x) and (l^.y=y) then r:=r^.n

else l:=l^.n;

if f then

begin

cut(l,r);

if l<>r then con(gs,l);

end;

l2:=r;


r:=l2;

r^.a:=arc((r^.x-x),(r^.y-y));

t:=l2;

repeat

t^.a:=arc((t^.x-x),(t^.y-y));

if (r^.a>t^.a) or ((r^.a=t^.a) and (abs(r^.x-x)+abs(r^.y-y)>abs(t^.x-x)+abs(t^.y-y))) then r:=t;

t:=t^.n;

until t=l2;

l2:=r;

l1^.p^.n:=nil;

l2^.p^.n:=nil;

r:=l1;

l:=l2;

ls:=nil;

while (r<>nil) and (l<>nil) do

begin

if (r^.a

begin

t:=r;

r:=r^.n;

if r<>nil then r^.p:=t^.p;

add(ls,t);

end else

begin

t:=l;

l:=l^.n;

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

add(ls,t);

end;

end;

if r<>nil then

begin

r^.p^.n:=r;

con(ls,r);

end;

if l<>nil then

begin

l^.p^.n:=l;

con(ls,l);

end;

grah(ls);

end;

begin

time:=now;

kkk:=0;

repeat


while sn<>nil do

begin

tt:=sn^.n;

dispose(sn);

sn:=tt;

end;

ls:=nil;

gs:=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;

add(ls,t);

end;

proc(ls);

t:=ls;

if t<>nil then

repeat

r:=t;

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

t:=t^.n;

dispose(r);

until t=ls;

t:=gs;

if t<>nil then

repeat

r:=t;

t:=t^.n;

dispose(r);

until t=gs;

inc(kkk);

until now-time>timew;

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

TimeL.Caption:=strr+'s';

PaintBox1.Refresh;

end;

{Div end}

procedure TForm1.CircleClick(Sender: TObject);

var

i:integer;

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:=0;

my:=0;

for i:=1 to QRandom.Value do

begin

new(t);

t^.n:=cn;

cn:=t;

t^.x:=Range.Value*sin(i);

t^.y:=Range.Value*cos(i);

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;

{ online}

procedure TForm1.Button2Click(Sender: TObject);

label onend;

type

prec=^TTree;

TTree=record

x,y:tp;

l,r,u,n,p,gr:prec;

kl,kr:integer;

end;

var ls,t,p,n,gr:prec;

procedure disp(t:prec);

begin

if t=nil then exit;

disp(t^.l);

disp(t^.r);

dispose(t);

end;

function max(a,b:integer):integer;

begin

if a>b then max:=a

else max:=b;

end;

procedure getleft(m,n:prec;var l:prec);

var fm,fn,f:boolean;

begin

l:=nil;

if ((p^.x=m^.x) and (p^.y=m^.y)) or ((p^.x=n^.x) and (p^.y=n^.y)) then exit;

if ((p^.x=m^.n^.x) and (p^.y=m^.n^.y)) or ((p^.x=n^.n^.x) and (p^.y=n^.n^.y)) then exit;

if (m^.n=m) or

(((m^.n^.x-p^.x)*(m^.y-p^.y)=(m^.x-p^.x)*(m^.n^.y-p^.y)) and (abs(m^.x-p^.x)=abs(m^.n^.x-p^.x)+abs(m^.n^.x-m^.x)) and (abs(m^.y-p^.y)=abs(m^.n^.y-p^.y)+abs(m^.n^.y-m^.y))) or

(((m^.p^.x-p^.x)*(m^.y-p^.y)>(m^.x-p^.x)*(m^.p^.y-p^.y)) and ((m^.n^.x-p^.x)*(m^.y-p^.y)>(m^.x-p^.x)*(m^.n^.y-p^.y)))

then

begin

l:=m;

exit;

end;

if (n^.n=n) or

(((n^.n^.x-p^.x)*(n^.y-p^.y)=(n^.x-p^.x)*(n^.n^.y-p^.y)) and (abs(n^.x-p^.x)=abs(n^.n^.x-p^.x)+abs(n^.n^.x-n^.x)) and (abs(n^.y-p^.y)=abs(n^.n^.y-p^.y)+abs(n^.n^.y-n^.y))) or

(((n^.p^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(n^.p^.y-p^.y)) and ((n^.n^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(n^.n^.y-p^.y)))

then

begin

l:=n;

exit;

end;

if m^.n<>m then

begin

fm:=((m^.n^.x-p^.x)*(m^.y-p^.y)>(m^.x-p^.x)*(m^.n^.y-p^.y)) or

((m^.p^.x-p^.x)*(m^.y-p^.y)<(m^.x-p^.x)*(m^.p^.y-p^.y));

fn:=((n^.n^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(n^.n^.y-p^.y)) or

((n^.p^.x-p^.x)*(n^.y-p^.y)<(n^.x-p^.x)*(n^.p^.y-p^.y));

f:=(m^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(m^.y-p^.y);


if (m^.l<>nil)

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

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

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

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