iscross

PURPOSE ^

ISCROSS - Finds whether pairs of lines cross each other

SYNOPSIS ^

function [is,S] = iscross(x1,y1,x2,y2,tol)

DESCRIPTION ^

ISCROSS - Finds whether pairs of lines cross each other

    [IS,S] = ISCROSS(X1,Y1,X2,Y2) where arguments X1, Y1,
    X2, Y2 are all 2 by N matrices are coordinates of
    ends of the pairs of line segments.
    Returns vector  IS (1 by N)  consisting of ones if 
    corresponding pairs cross each other, zeros if they 
    don't and .5 if an end of one line segment lies on
    another segment.
    Also returns a matrix  S (4 by N) with each row 
    consisting of cross products (double areas of 
    corresponding triangles) built on the following points:
    (X2(1,:),Y2(1,:)),(X1(1,:),Y1(1,:)),(X2(2,:),Y2(2,:)),
    (X2(1,:),Y2(1,:)),(X1(2,:),Y1(2,:)),(X2(2,:),Y2(2,:))
    (X1(1,:),Y1(1,:)),(X2(1,:),Y2(1,:)),(X1(2,:),Y1(2,:))
    (X1(1,:),Y1(1,:)),(X2(2,:),Y2(2,:)),(X1(2,:),Y1(2,:))
    The signs of these 4 areas can be used to determine
    whether these lines and their continuations cross each
    other.
    [IS,S] = ISCROSS(X1,Y1,X2,Y2,TOL) uses tolerance TOL
    for detecting the crossings (default is 0).

  Copyright (c) 1995 by Kirill K. Pankratov
       kirill@plume.mit.edu
       08/14/94, 05/18/95, 08/25/95

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function [is,S] = iscross(x1,y1,x2,y2,tol)
0002 %ISCROSS - Finds whether pairs of lines cross each other
0003 %
0004 %    [IS,S] = ISCROSS(X1,Y1,X2,Y2) where arguments X1, Y1,
0005 %    X2, Y2 are all 2 by N matrices are coordinates of
0006 %    ends of the pairs of line segments.
0007 %    Returns vector  IS (1 by N)  consisting of ones if
0008 %    corresponding pairs cross each other, zeros if they
0009 %    don't and .5 if an end of one line segment lies on
0010 %    another segment.
0011 %    Also returns a matrix  S (4 by N) with each row
0012 %    consisting of cross products (double areas of
0013 %    corresponding triangles) built on the following points:
0014 %    (X2(1,:),Y2(1,:)),(X1(1,:),Y1(1,:)),(X2(2,:),Y2(2,:)),
0015 %    (X2(1,:),Y2(1,:)),(X1(2,:),Y1(2,:)),(X2(2,:),Y2(2,:))
0016 %    (X1(1,:),Y1(1,:)),(X2(1,:),Y2(1,:)),(X1(2,:),Y1(2,:))
0017 %    (X1(1,:),Y1(1,:)),(X2(2,:),Y2(2,:)),(X1(2,:),Y1(2,:))
0018 %    The signs of these 4 areas can be used to determine
0019 %    whether these lines and their continuations cross each
0020 %    other.
0021 %    [IS,S] = ISCROSS(X1,Y1,X2,Y2,TOL) uses tolerance TOL
0022 %    for detecting the crossings (default is 0).
0023 %
0024 %  Copyright (c) 1995 by Kirill K. Pankratov
0025 %       kirill@plume.mit.edu
0026 %       08/14/94, 05/18/95, 08/25/95
0027 
0028  % Defaults and parameters .......................
0029 tol_dflt = 0; % Tolerance for area calculation
0030 is_chk = 1;   % Check input arguments
0031 
0032  % Handle input ..................................
0033 if nargin==0, help iscross, return, end
0034 if nargin<4           % Check if all 4 entered
0035   error('  Not enough input arguments')
0036 end
0037 if nargin<5, tol = tol_dflt; end
0038 if tol < 0, is_chk = 0; tol = 0; end
0039 
0040  % Check the format of arguments .................
0041 if is_chk
0042   [x1,y1,x2,y2] = linechk(x1,y1,x2,y2);
0043 end
0044 
0045 len = size(x1,2);
0046 o2 = ones(2,1);
0047 
0048  % Find if the ranges of pairs of segments intersect
0049 [isx,S,A] = interval(x1,x2);
0050 scx = diff(A);
0051 [isy,S,A] = interval(y1,y2);
0052 scy = diff(A);
0053 is = isx & isy;
0054 
0055  % If S values are not needed, extract only those pairs
0056  % which have intersecting ranges ..............
0057 if nargout < 2
0058   isx = find(is);  % Indices of pairs to be checked
0059                    % further
0060   x1 = x1(:,isx);
0061   x2 = x2(:,isx);
0062   y1 = y1(:,isx);
0063   y2 = y2(:,isx);
0064   is = is(isx);
0065   if isempty(is), is = zeros(1,len); return, end
0066   scx = scx(isx);
0067   scy = scy(isx);
0068 end
0069 
0070  % Rescale by ranges ...........................
0071 x1 = x1.*scx(o2,:);
0072 x2 = x2.*scx(o2,:);
0073 y1 = y1.*scy(o2,:);
0074 y2 = y2.*scy(o2,:);
0075 
0076 
0077  % Calculate areas .............................
0078 S = zeros(4,length(scx));
0079 S(1,:) = (x2(1,:)-x1(1,:)).*(y2(2,:)-y1(1,:));
0080 S(1,:) = S(1,:)-(x2(2,:)-x1(1,:)).*(y2(1,:)-y1(1,:));
0081 
0082 S(2,:) = (x2(1,:)-x1(2,:)).*(y2(2,:)-y1(2,:));
0083 S(2,:) = S(2,:)-(x2(2,:)-x1(2,:)).*(y2(1,:)-y1(2,:));
0084 
0085 S(3,:) = (x1(1,:)-x2(1,:)).*(y1(2,:)-y2(1,:));
0086 S(3,:) = S(3,:)-(x1(2,:)-x2(1,:)).*(y1(1,:)-y2(1,:));
0087 
0088 S(4,:) = (x1(1,:)-x2(2,:)).*(y1(2,:)-y2(2,:));
0089 S(4,:) = S(4,:)-(x1(2,:)-x2(2,:)).*(y1(1,:)-y2(2,:));
0090 
0091 
0092  % Find if they cross each other ...............
0093 is = (S(1,:).*S(2,:)<=0)&(S(3,:).*S(4,:)<=0);
0094 
0095 
0096  % Find very close to intersection
0097 isy = min(abs(S));
0098 ii = find(isy<=tol & is);
0099 is(ii) = .5*ones(size(ii));
0100 
0101  % Output
0102 if nargout < 2
0103   isy = zeros(1,len);
0104   isy(isx) = is;
0105   is = isy;
0106 
0107 else
0108   isy = scx.*scy;
0109   ii = find(~isy);
0110   isy(ii) = ones(size(ii));
0111   S = S./isy(ones(4,1),:);
0112 
0113 end
0114

Generated on Sun 29-Mar-2009 20:22:55 by m2html © 2003