wujiao.m

wujiao.m是五角星去交叉程序

function y=wujiao(tour)%五角星去叉程序
t=[1 6 4               
    2 0 4
    3 3 6
    4 5 0
    5 1 0]; %data att48
tour=[2 1 5 3 4];
subplot(1,2,1); % initial route
axis([-1 7 -1 7]);
hold on;
for i=1:4
    drawline(t(tour(i),2:3),t(tour(i+1),2:3));
end;
drawline(t(tour(5),2:3),t(tour(1),2:3));
hold off;

%eliminate cross
tour=[tour tour(1)];
for i=1:4
    for j=i+2:5
        if iscross(t(tour(i),2:3),t(tour(i+1),2:3),t(tour(j),2:3),t(tour(j+1),2:3))
            disp(tour(i)),disp(tour(i+1));disp(tour(j)),disp(tour(j+1));
            m=tour(i+1);tour(i+1)=tour(j);tour(j)=m;
            disp('tour='),disp(tour);
            
        end
    end
end

subplot(1,2,2); % initial route

axis([-1 7 -1 7]);
hold on;
for i=1:5
    drawline(t(tour(i),2:3),t(tour(i+1),2:3));
end;
%drawline(t(tour(5),2:3),t(tour(1),2:3));
hold off;
   

function y=iscross(x,y,z,w)
D=(y(1)-x(1))*(z(2)-w(2))-(z(1)-w(1))*(y(2)-x(2));
m=((z(1)-x(1))*(z(2)-w(2))-(z(1)-w(1))*(z(2)-x(2)))/D;
n=((y(1)-x(1))*(z(2)-x(2))-(z(1)-x(1))*(y(2)-x(2)))/D;
if x(1)==w(1)&x(2)==w(2)
    y=0;
elseif D==0
    y=0;
else 
    if m>=0&m<=1&n>=0&n<=1
      y=1;
   else y=0;
   end;
end;
%% 画出二维空间中以点 X 和点 Y 为端点的直线
function y=drawline(x,y)
delx=y(1)-x(1);
dely=y(2)-x(2);
if delx==0
    if dely==0
        error('the same point!');
    elseif dely>0
        t=x(2):dely/100:y(2);
        s=x(1)*ones(size(t));
        plot(s,t);
    else
        t=y(2):abs(dely/100):x(2);
        s=x(1)*ones(size(t));
        plot(s,t);
    end
elseif delx>0
    if dely==0
        s=x(1):delx/100:y(1);
        t=x(2)*ones(size(s));
        plot(s,t);
    else
        s=x(1):delx/100:y(1);
        t=dely/delx.*(s-x(1))+x(2);
        plot(s,t);
    end
else
    if dely==0
        s=y(1):delx/100:x(1);
        t=x(2)*ones(size(s));
        plot(s,t);
    else
        s=y(1):abs(delx/100):x(1);
        t=dely/delx.*(s-x(1))+x(2);
        plot(s,t);
    end
end