


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

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