function layout = lineext(layout,blklocs,srcPort,dstPort)
%LINEEXT adds more "turns" on a existing connections such that there is
%   no cross block on the route of the connection line.
%   LAYOUT = LINEEXT(LAYOUT, BLKLOCS, SRCPORT DSTPORT)
%   extends the original connection LAYOUT to the output LAYOUT
%   such that the connection will avoid to cross blocks indicated
%   in BLKLOCS. Each block location take a row, which is represented
%   by BLKLOCS=[min_x min_y max_x max_y]. SRCPORT and DSTPORT carry 
%   the information of the port orientation, from port number and 
%   total port number in the block.

%   Copyright 1997-2000 The MathWorks, Inc.
%   $Revision: 1.9 $ $Date: 2000/06/14 16:11:59 $

   % The basic technique used in this function is to change
   % the orientation of each processing segment to have
   % direction of 0 or left to right ---> line. Then, use the
   % same procedure for all segment check up.
   % the direction of a line: 0> 1v 2< 3^

   [n_l,m_l] = size(layout); 	  		   % n_l: number of point; m_l==2
   if (n_l < 2)
      disp('There is no line segment available')
      disp('Error in calling linext')
      return
   end
   [n_b,m_b] = size(blklocs); 			   % n_b: number of block; m_b==4
   if (n_b < 1)
      %there is nothing we need to do
      return
   end
   if ((m_l ~= 2) | (m_b ~= 4) | (length(srcPort) ~= 3) | (length(dstPort) ~= 3))
      disp('Illegal length of input variable')
   end
   % get the cross points
   [x_min,x_max,y_min,y_max,to_do,n_be,n_en] = linemima(layout,blklocs);
   %
   % the iterative loop
   % set an iterative flag
   %
   flag = zeros(n_l,1);
   while (~isempty(to_do) & (n_l < 10))
      %
      % quit if there is block overlap
      %
      if (n_be == 1)
	 [tmp1,tmp2,tmp3,tmp4,tmp5] = linemima(layout(1:2,:),blklocs);
	 if (~isempty(tmp5))
	    if (((srcPort(1) == 0) & (tmp1 < layout(1,1)) & (tmp2 > layout(1,1)))...
		| ((srcPort(1) == 1) & (tmp3 < layout(1,2)) & (tmp4 > layout(1,2)))...
		| ((srcPort(1) == 2) & (tmp2 > layout(1,1)) & (tmp1 < layout(1,1)))...
		| ((srcPort(1) == 3) & (tmp4 > layout(1,2)) & (tmp3 < layout(1,2))))
	       warning('Block overlap, there is no way to avoid block crossing'); 
	       return
	    end
	 end
      end
      if (n_en == n_l-1)
	 [tmp1,tmp2,tmp3,tmp4,tmp5] = linemima(layout(n_en:n_l,:),blklocs);
	 if (~isempty(tmp5))
	    if (((dstPort(1) == 0) & (tmp1 < layout(n_l,1)) & (tmp2 > layout(n_l,1)))...
		| ((dstPort(1) == 1) & (tmp3 < layout(n_l,2)) & (tmp4 > layout(n_l,2)))...
		| ((dstPort(1) == 2) & (tmp2 > layout(n_l,1)) & (tmp1 < layout(n_l,1)))...
		| ((dstPort(1) == 3) & (tmp4 > layout(n_l,2)) & (tmp3 < layout(n_l,2))))
	       warning('Block overlap, there is no way to avoid block crossing'); 
	       return
	    end
	 end
      end
      %
      % logic search for straight condition
      %
      straight = 0;
      if ((n_be+1 == n_l) & (n_be == 1))
	 straight = 1;
      elseif (n_be+1 == n_l) 
	 if (max(abs(layout(n_be,:)-layout(n_be+1,:))) > ...
	     4*max(abs(layout(n_be,:)-layout(n_be-1,:))))
	    straight = 1;
	 end
      elseif ((n_be == 1) & (n_be+2 >= n_l))
	 if (max(abs(layout(n_be,:)-layout(n_be+1,:))) > ...
	     4*max(abs(layout(n_be+1,:)-layout(n_be+2,:))))
	    straight = 1;
	 end
      end
      if (straight)
	 %
	 % If there is no room for moving the existing line
	 % around, take a hard turn to avoid the cross
	 %
	 % in the case of brake to ___|     |_____
	 %
	 %make the line direction to be ---> direction 0
	 direct = linedir(layout(n_be:n_be+1,:));
	 if (direct < 0)
	    % I am not taking care of randon direction now
	    return;
	 end
	 if ((direct == 1) | (direct == 3))
	    % switch x and y
	    layout(:,1:2) = [-layout(:,2) layout(:,1)];
	    blklocs(:,1:4) = [-blklocs(:,4) blklocs(:,1) -blklocs(:,2) blklocs(:,3)];
	 end
	 if ((direct == 2) | (direct == 1))
	    %reverse direction
	    layout = -layout;
	    blklocs(:,1:4) = -blklocs(:,[3 4 1 2]);
	 end
	 % now everyone has direction 0
	 % calculate the minimum and maximum
	 [x_min,x_max,y_min,y_max] = linemima(layout(n_be:n_be+1,:),blklocs);
	 % make space for the new part
	 layout(n_be+5:n_l+4,:) = layout(n_be+1:n_l,:);
	 flag(n_be+5:n_l+4) = flag(n_be+1:n_l);
	 flag(n_be:n_be+4) = flag(n_be:n_be+4)*0;
	 n_l = n_l+4;
	 % make the layout extended
	 layout(n_be+1,1) = min((layout(n_be,1)+x_min)/2,x_min-10);
	 layout(n_be+4,1) = max((layout(n_be+5,1)+x_max)/2,x_max+10);
	 layout(n_be+1,2) = layout(n_be,2);
	 layout(n_be+4,2) = layout(n_be+5,2);
	 layout(n_be+2,1) = layout(n_be+1,1);
	 layout(n_be+3,1) = layout(n_be+4,1);
	 layout(n_be+2,2) = y_max+10;
	 layout(n_be+3,2) = y_max+10;
	 again = 1; 				   % flag for do it agin
	 odir = 0;  				   % flag for failed 
	 addir = 0; 				   % adding direction is right
	 sudir = 0; 				   % substracting direction is right
	 again = 0;
	 while (again <= 10)
	    again = again+1;
	    %
	    % go the upper direction
	    %
	    if (isempty(blkxchk(layout(n_be+1:n_be+2,:),blklocs)))
	       addir = 1;
	       if (isempty(blkxchk(layout(n_be+3:n_be+4,:),blklocs)))
		  [cros_inf,block_n] = blkxchk(layout(n_be+2:n_be+3,:),blklocs);
		  if (isempty(cros_inf))
		     % done
		     again = 11;
		     odir = 0;
		  else
		     % lower the floor
		     tmp_max = max(find(blklocs(block_n,4) == max(blklocs(block_n,4))));
		     tmp_max = blklocs(tmp_max,4);
		     layout(n_be+2,2) = tmp_max+10+abs(layout(n_be+2,1)-layout(n_be+3,1))/40;
		     layout(n_be+3,2) = layout(n_be+2,2);             
		  end
	       end
	    else
	       again = 11;
	       odir = 1;
	    end
	 end
	 again = 1;
	 if (odir)
	    %
	    % go the down direction
	    %
	    odir = 0;
	    layout(n_be+2,2) = y_min-10-abs(layout(n_be+2,1)-layout(n_be+3,1))/40;;
	    layout(n_be+3,2) = layout(n_be+2,2);
	    again = 0;
	    while (again <= 10)
	       again = again+1;
	       if (isempty(blkxchk(layout(n_be+1:n_be+2,:),blklocs)))
		  sudir = 1;
		  if (isempty(blkxchk(layout(n_be+3:n_be+4,:),blklocs)))
		     [cros_inf,block_n] = blkxchk(layout(n_be+2:n_be+3,:),blklocs);
		     if (isempty(cros_inf))
			% done
			again = 11; odir = 0;
		     else
			% lower the floor
			tmp_min = min(find(blklocs(block_n,2) == min(blklocs(block_n,2))));
			tmp_min = blklocs(tmp_min,2);
			layout(n_be+2,2) = tmp_min-10-abs(layout(n_be+2,1)-layout(n_be+3,1))/40;
			layout(n_be+3,2) = layout(n_be+2,2);           
		     end
		  end
	       else
		  again = 11;
		  odir = 1;
	       end
	    end          
	 end
	 if (odir == 1)
	    if (addir == 1)
	       layout(n_be+2,2) = y_max+10+abs(layout(n_be+2,1)-layout(n_be+3,1))/40;
	       layout(n_be+3,2) = layout(n_be+2,2);
	    elseif (sudir == 1)
	       layout(n_be+2,2) = y_min-10-abs(layout(n_be+2,1)-layout(n_be+3,1))/40;
	       layout(n_be+3,2) = layout(n_be+2,2);
	    else
	       % Sorry,I cannot do anything better
	       layout(n_be+1:n_l-4,:) = layout(n_be+5:n_l,:);
	       layout(n_l-3:n_l,:) = [];
	       flag(n_l-3:n_l) = [];
	       n_l = 11; 			   % set signal to stop.
	    end
	 end
	 % back to the original direction
	 if ((direct == 2) | (direct == 1))
	    layout  = -layout;
	    blklocs(:,1:4) = -blklocs(:,[3 4 1 2]);
	 end
	 if ((direct == 1) | (direct == 3))
	    % swirch x and y
	    layout(:,1:2) = [layout(:,2) -layout(:,1)];
	    blklocs(:,1:4) = [blklocs(:,2) -blklocs(:,3) blklocs(:,4) -blklocs(:,1)];
	 end
      elseif ((n_be > 1) & (n_be+1 < n_l) & (flag(n_be) < 1)) %if straight
	 %
	 % if the segment with cross is not the beginning
	 % or the end of the the connection segments, then
	 % go throught the following.
	 %
	 % -----|       ===>  ---------|   or   --|
	 %      |-----                 |--        |----------
	 %    (1)                 (2)              (3)
	 %
	 up = 1;
	 dn = 1;
	 % make layout(n_be-1:n_be,:) ---> direction
	 direct = linedir(layout(n_be-1:n_be,:));
	 if (direct < 0)
	    % I am not taking care of randon direction now
	    return
	 end
	 if ((direct == 1) | (direct == 3))
	    % switch x and y
	    layout(:,1:2) = [-layout(:,2) layout(:,1)];
	    blklocs(:,1:4) = [-blklocs(:,4) blklocs(:,1) -blklocs(:,2) blklocs(:,3)];
	 end
	 if ((direct == 2) | (direct == 1))
	    % reverse direction
	    layout = -layout;
	    blklocs(:,1:4) = -blklocs(:,[3 4 1 2]);
	 end
	 while (up)
	    % find the cross
	    [x_min,x_max,y_min,y_max,test] = linemima(layout(n_be:n_be+1,:),blklocs);
	    if (isempty(test))
	       dn = 0; % it is succesfull
	       up = 0;
	    else
	       % move up to position (2)
	       if (isempty(blkxchk([layout(n_be-1,:);x_max+10,layout(n_be,2)],blklocs)))
		  if (x_max < layout(n_be+1,1))
		     layout(n_be,1)   = x_max+10+abs(layout(n_be,2)-layout(n_be+1,2))/40;
		     layout(n_be+1,1) = layout(n_be,1);
		  elseif (n_be+1 ~= n_l)
		     layout(n_be,1)   = x_max+10+abs(layout(n_be,2)-layout(n_be+1,2))/40;
		     layout(n_be+1,1) = layout(n_be,1);
		  else
		     up = 0; % there is no way up
		  end
	       else
		  up = 0;  %there is no way to go up
	       end
	    end
	 end
	 while (dn)
	    % find the cross
	    [x_min,x_max,y_min,y_max,test] = linemima(layout(n_be:n_be+1,:),blklocs);
	    if (isempty(test))
	       dn = 0;
	       up = 0;
	    else
	       % move down to position (3)
	       if (isempty(blkxchk([layout(n_be-1,:);x_min-10,layout(n_be,2)],blklocs)))
		  if (x_max < layout(n_be+1,1))
		     layout(n_be,1)   = x_min-10-abs(layout(n_be,2)-layout(n_be+1,2))/40;
		     layout(n_be+1,1) = layout(n_be,1);
		  elseif (n_be+1 ~= n_l)
		     layout(n_be,1)   = x_min-10-abs(layout(n_be,2)-layout(n_be+1,2))/40;
		     layout(n_be+1,1) = layout(n_be,1);
		  else
		     dn = 0; 			   % there is no way dn
		  end
	       else
		  dn =0;  			   % there is no way to go dn
		  flag(n_be) = 1+flag(n_be);
	       end
	    end
	 end
	 % switch back to the direction
	 if ((direct == 2) | (direct == 1))
	    layout  = -layout;
	    blklocs(:,1:4) = -blklocs(:,[3 4 1 2]);
	 end
	 if ((direct == 1) | (direct == 3))
	    % swirch x and y
	    layout(:,1:2) = [layout(:,2) -layout(:,1)];
	    blklocs(:,1:4) = [blklocs(:,2) -blklocs(:,3) blklocs(:,4) -blklocs(:,1)];
	 end
      elseif (flag(n_be) < 10)
	 %                                _______|
	 % in the case of brake to ______|         seg1, seg2, seg3, seg4
	 % all of the cases, brake layout(n_be:  n_be+1, :)
	 % and                     layout(n_be+1:n_be+2, :)
	 % except for the case of n_be+1 == n_en when the 
	 % connection lines will be go a reverse way to match the requirement
	 %in case of need to reverse
	 revers = 0;
	 if (n_be+1 == n_l)
	    revers = 1;
	    layout(:,1:2) = layout(:,[2 1]);
	    n_be = 1; n_en = 2;
	 end
	 % make all of the begining line to be left-->right direction
	 direct = linedir(layout(n_be:n_be+1,:));
	 if (direct < 0)
	    % I am not taking care of randon direction now
	    return
	 end
	 if ((direct == 1) | (direct == 3))
	    % switch x and y
	    layout(:,1:2) = [-layout(:,2) layout(:,1)];
	    blklocs(:,1:4) = [-blklocs(:,4) blklocs(:,1) -blklocs(:,2) blklocs(:,3)];
	 end
	 if ((direct == 2) | (direct == 1))
	    % reverse direction
	    layout = -layout;
	    blklocs(:,1:4) = -blklocs(:,[3 4 1 2]);
	 end
	 % now everyone has direction 0      
	 % calculate the minimum and maximum
	 [x_min,x_max,y_min,y_max] = linemima(layout(n_be:n_be+1,:),blklocs);
	 % direction of the second line
	 direct2 = linedir(layout(n_be+1:n_be+2,:));
	 % by our setup, direct2 should be either 1 or 3
	 % make space for the new part, enlarge two points
	 layout(n_be+3:n_l+2,:) = layout(n_be+1:n_l,:);
	 flag(n_be+3:n_l+2) = flag(n_be+1:n_l);
	 flag(n_be+1:n_be+2) = flag(n_be+1:n_be+2)*0;
	 n_l = n_l+2;
	 % braking n_be:n_be+1 line
	 layout(n_be+1,1) = min((layout(n_be,1)+x_min)/2,x_min-10);
	 layout(n_be+2,1) = layout(n_be,1);
	 if (direct2 == 1)
	    layout(n_be+3,2) = max((layout(n_be+3,2)+y_max)/2,y_max+10);
	 else
	    layout(n_be+3,2) = min((layout(n_be+3,2)+y_min)/2,y_min-10);
	 end
	 layout(n_be+2,1) = layout(n_be+1,1);
	 layout(n_be+2,2) = layout(n_be+3,2);
	 odir = 0;  				   % flag for failed 
	 addir = 0; 				   % first section is fixed
	 sudir = 0; 				   % second section is fixed
	 thdir = 0; 				   % third section is fixed
	 frdir = 0; 				   % fourth section is fixed
	 again = 1;
	 test = 0;
	 while (again & (test < 10))
	    test = test+1;
	    if (addir == 0) 			   % seg1
	       % Need to check up or fix
	       [tmp_x_min,tmp_x_max,tmp_y_min,tmp_y_max,tmp_x] = ...
		   linemima(layout(n_be:n_be+1,:),blklocs);
	       addir = 1;
	       if (~isempty(tmp_x))
		  if (tmp_x_max < x_min)     	   % not cross the old limit
		     layout(n_be+1,1) = (x_min+tmp_x_max)/2;
		     sudir = 0;             	   % seg2 relocated
		  elseif (tmp_x_min > layout(n_be,1))       % not change the seg1 direction.
		     layout(n_be+1,1) = min((layout(n_be,1)+tmp_x_min)/2,tmp_x_min-10);
		     thdir = 0; sudir = 0;         % seg2 relocated; seg3 extended
		  else
		     % need to reduce the length of seg2
		     odir = 1; addir = 0; sudir = 0; again = 0;
		  end
		  layout(n_be+2,1) = layout(n_be+1,1);
	       end
	    end
	    if (sudir == 0) %seg2
	       % Need to checkup or fix
	       [tmp_x_min,tmp_x_max,tmp_y_min,tmp_y_max,tmp_x] = ...
		   linemima(layout(n_be+1:n_be+2,:),blklocs);
	       sudir = 1;
	       if (~isempty(tmp_x))
		  if (tmp_x_max < x_min)                      % still have space for pass
		     layout(n_be+2,1) = (tmp_x_max+x_min)/2;
		  elseif ((tmp_y_min > y_max) & (direct2 == 1)) % still have space for pass
		     layout(n_be+2,2) = (tmp_y_min+y_max)/2;
		     thdir = 0;                                % seg3 moved
		     frdir = 0;                                % seg4 extended
		  elseif ((tmp_y_max < y_min) & (direct2 == 3)) % still have space for pass
		     layout(n_be+2,2) = (tmp_y_max+y_min)/2;
		     thdir = 0;                                % seg3 moved
		     frdir = 0;                                % seg4 extended
		  elseif (tmp_x_min > layout(n_be,1))        % horizontal move
		     layout(n_be+2,1) = min((tmp_x_min+layout(n_be,1))/2,tmp_x_min-10);
		     sudir = 0;                                % seg2 moved
		     thdir = 0;                                % seg3 moved
		  else
		     % there is no way to move
		     sudir = 0;
		     odir = 1;
		     again = 0;
		  end
	       end
	       % adjust the points
	       layout(n_be+3,2) = layout(n_be+2,2);
	       layout(n_be+1,1) = layout(n_be+2,1);
	    end
	    if (thdir == 0)
	       % Need to checkup or fix
	       [tmp_x_min,tmp_x_max,tmp_y_min,tmp_y_max,tmp_x] = ...
		     linemima(layout(n_be+2:n_be+3,:),blklocs);
	       thdir = 1;
	       if (~isempty(tmp_x))
		  if (tmp_x_max < x_min)
		     layout(n_be+2,1) = (tmp_x_max+x_min)/2;
		     sudir = 0;
		  elseif ((tmp_y_max > y_max) & (tmp_y_max < layout(n_be+4,2)) & (direct2 == 1))
		     % still have space for pass
		     layout(n_be+3,2) = max((tmp_x_max+layout(n_be+4,2))/2,tmp_x_max);
		     sudir = 0; 
		     thdir = 0;
		  elseif ((tmp_y_min < y_min) & (tmp_y_min > layout(n_be+4,2)) & (direct2 == 3))
		     % still have space for pass
		     layout(n_be+3,2) = min((tmp_x_min+layout(n_be+4,2))/2,tmp_x_min-10);
		     sudir = 0; 
		     thdir = 0;
		  elseif ((tmp_y_min > layout(n_be+4,2)) & (direct2 == 3))
		     layout(n_be+3,2) = (tmp_y_min > layout(n_be+4,2))/2;
		  elseif ((tmp_y_max < layout(n_be+4,2)) & (direct2 == 13))
		     layout(n_be+3,2) = (tmp_y_max > layout(n_be+4,2))/2;
		  else
		     % there is no way to move
		     sudir = 0;
		     odir = 1;
		     again = 0;
		  end
		  layout(n_be+2,2) = layout(n_be+3,2);
		  layout(n_be+1,1) = layout(n_be+2,1);
	       end
	    end
	    if (frdir == 0)
	       %
	       [tmp_x_min,tmp_x_max,tmp_y_min,tmp_y_max,tmp_x] = ...
		   linemima(layout(n_be+3:n_be+4,:),blklocs);
	       thdir = 1;
	       if (~isempty(tmp_x))
		  if ((tmp_y_max < layout(n_be+4,2)) & (direct2 == 1))
		     layout(n_be+3,2) = max((layout(n_be+4,2)+tmp_y_max)/2,tmp_y_max+10);
		     thdir = 0;
		  elseif ((tmp_y_min > layout(n_be+4,2)) & (direct2 == 3))
		     layout(n_be+3,2) = min((layout(n_be+4,2)+tmp_y_min)/2,tmp_y_min-10);
		     thdir = 0;
		  else
		     thdir = 0; odir = 0; %wait for next around
		     again = 0;
		  end
		  layout(n_be+2,2) = layout(n_be+3,2);
	       end
	    end
	 end
	 % back to the original direction
	 if ((direct == 2) | (direct == 1))
	    layout  = -layout;
	    blklocs(:,1:4) = -blklocs(:,[3 4 1 2]);
	 end
	 if ((direct == 1) | (direct == 3))
	    % swirch x and y
	    layout(:,1:2) = [layout(:,2) -layout(:,1)];
	    blklocs(:,1:4) = [blklocs(:,2) -blklocs(:,3) blklocs(:,4) -blklocs(:,1)];
	 end
	 if (revers)
	    layout(:,1:2) = layout(:,[2 1]);
	    revers = 0;
	 end
      else
	 n_l = 11; 				   % I cannot do anything better
      end 					   % if straight
      % test if there is anything to be done
      [x_min,x_max,y_min,y_max,to_do,n_be,n_en] = linemima(layout,blklocs);
   end  					   % while
   % check if we could reduce some redundent segment
   for (j = 1:3)
      [n_l,m_l] = size(layout);
      if (n_l > 5)
	 tmp = [];
	 i = 1;
	 while (i < n_l-3)
	    i = i+1;
	    tmp(1,:) = layout(i-1,:);
	    tmp(3,:) = layout(i+2,:);
	    if (rem(i,2) == 0)
	       tmp(2,2) = layout(i-1,2);
	       tmp(2,1) = layout(i+2,1);
	    else
	       tmp(2,1) = layout(i-1,1);
	       tmp(2,2) = layout(i+2,2);
	    end
	    if (isempty(blkxchk(tmp(1:2,:),blklocs)))
	       if (isempty(blkxchk(tmp(2:3,:),blklocs)))
		  layout(i,:) = tmp(2,:);
		  layout(i+1:i+2,:) = [];
		  n_l = n_l-2;
	       end
	    end
	 end
      end
   end
   % simplify: check if the lines can be simplified be combining some of them
   return					   % Last card of LINEEXT

function [x_min,x_max,y_min,y_max,to_do,n_be,n_en] = linemima(layout,blklocs)
%LINEMIMA finds the minimum and maximum of the first cross.
%   LINEMIMA is a utility function, called by AUTOLINE and LINEEXT.


   [n_l,m_l] = size(layout);
   block_n = [];
   to_do = [];
   for (i = n_l-1:-1:1)
      [tmpx,tmpy] = blkxchk(layout(i:i+1,:),blklocs);
      if (~isempty(tmpx))
	 to_do = [i to_do];
	 cros_inf = tmpx;
	 block_n  = tmpy;
      end
   end
   n_be = min(to_do);
   n_en = max(to_do);
   % Cros_inf & block_n keeps the cross information of layout(n_be:n_be+1,:)
   if (isempty(block_n))
      x_min = max(blklocs(:,3));
      x_max = min(blklocs(:,1));
      y_min = max(blklocs(:,4));
      y_max = min(blklocs(:,2));
   else
      x_min = min(find(blklocs(block_n,1) == min(blklocs(block_n,1))));
      x_max = max(find(blklocs(block_n,3) == max(blklocs(block_n,3))));
      y_min = min(find(blklocs(block_n,2) == min(blklocs(block_n,2))));
      y_max = max(find(blklocs(block_n,4) == max(blklocs(block_n,4))));
      x_min = blklocs(block_n(x_min),1);
      x_max = blklocs(block_n(x_max),3);
      y_min = blklocs(block_n(y_min),2);
      y_max = blklocs(block_n(y_max),4);
   end
   return					   % End of LINEMIMA

function [cros_inf,block_n] = blkxchk(layout,blklocs)
%BLKXCHK checks whether a line segment crosses a block.
%   [CORS_INF, BLOCK_N] = BLKXCHK(LAYOUT, BLKLOCS) checks if a line
%   segment in LAYOUT = [x1,y1;x2,y2] has crossed any block listed
%   in BLOCKS. BLOCKS is a nx4 matrix with each row of the matrix
%   representing a location of a block. CROS_INF provides the 
%   cross information:
%     cros_inf = 1 --> or <-- partial invate.
%     cros_inf = 2 >----< or <-------->
%     cros_inf = 3 turn 90 degree of cros_inf = 1
%     cros_inf = 4 turn 90 degree of cros_inf = 2
%     cros_inf = 6 crosed, none of the above listed direction.
%   BLOCK_N provides the crossed block number (row in BLKLOC). When
%   there is no cross, CROS_INF and BLOCK_N are empty. When the line
%   segment across more than one block, both CROS_INF and BLOCK_N
%   are vectors.

   cros_inf = [];
   block_n = [];
   k = 0;
   x = zeros(4,1);
   a = [min(layout);max(layout)];
   if (~isempty(blklocs))
      [tmp1,tmp2] = size(blklocs);
      for (i = 1:tmp1)
	 b = blklocs(i,:);
	 x(1) = ((a(1,1) <= b(1)) & (a(2,1) >= b(1))) & ~(a(1,2) > b(4) | a(2,2) < b(2));
	 x(2) = ((a(1,1) <= b(3)) & (a(2,1) >= b(3))) & ~(a(1,2) > b(4) | a(2,2) < b(2));
	 x(3) = ((a(1,2) <= b(2)) & (a(2,2) >= b(2))) & ~(a(1,1) > b(3) | a(2,1) < b(1));
	 x(4) = ((a(1,2) <= b(4)) & (a(2,2) >= b(4))) & ~(a(1,1) > b(3) | a(2,1) < b(1));
	 % Add a condition of line seg is within the block
	 x(5) = ((a(1,1) >= b(1)) & (a(2,1) <= b(3))) & ~(a(1,2) > b(4) | a(2,2) < b(2));
	 x(6) = ((a(1,2) >= b(2)) & (a(2,2) <= b(4))) & ~(a(1,1) > b(3) | a(2,1) < b(1));
	 if (sum(x))
	    % there is a corss
	    k = k+1;
	    block_n(k) = i;
	    z = find(x == 1);
	    if (length(z) <= 1)
	       cros_inf(k) = 1;
	       if (z <= 2)
		  cros_inf(k) = 3;		   % cross vertical
	       end
	    elseif (z(1) >= 3)      		   % cross horizental
	       cros_inf(k) = 2;
	    elseif (z(2) <= 2)   		   % cross vertical
	       cros_inf(k) = 4;
	    else              		   	   % in this case layout is not a straight line
	       cros_inf(k) = 6;
	    end
	 end
      end
   end
   return					   % Last card of BLKXCHK
   
function direct = linedir(layout)
%LINEDIR finds the direction of a line segment
%   layout = [x1,y1; x2.y2;...]
%   direct = 0>, 1v, 2<, 3^ 
%   direct = -1 if it is not a straight line

   if (layout(1,2) == layout(2,2))
      % Horizontal
      if (layout(1,1) < layout(2,1))
	 direct = 0;
      else
	 direct = 2;
      end
   elseif (layout(1,1) == layout(2,1))
      % Verticle
      if (layout(1,2) < layout(2,2))
	 direct = 1;
      else
	 direct = 3;
      end
   else
      % In the case of not a straight line
      direct = -1;
   end
   return					   % Last card of LINEDIR

