intersection points between two curves

9 views (last 30 days)
Prakash Chettri
Prakash Chettri on 29 Nov 2021
Edited: Prakash Chettri on 13 Dec 2021
Any suggestions would be greatly accepted. Thank you in advance.
  1 Comment
Chunru
Chunru on 29 Nov 2021
Can you make your code executable by including values for some variables?

Sign in to comment.

Answers (2)

KSSV
KSSV on 29 Nov 2021
To get area, pick the required points, arrange them in a order and use polyarea. Also have a look on trapz.

Chunru
Chunru on 29 Nov 2021
% These are the Input parameters used
w = 60;
h = 350;
T0 = 60;
rho = 600;
T= 3.175;
N= 8;
W = T*N;
X0 = w/2;
Y0 = 0;
We=50.9381;
T0R=62.2211;
T0L=58.0029;
% First curve
X01R= (X0+rho*cos(T0*pi/180)-(rho-W/2)*cos(T0R*pi/180))-We;
x01r=X01R; y01r=Y0; k=1;
while (x01r>=0) && (y01r<=h)
YR1(k)=Y0+(k-1)*h/500; y01r=YR1(k);
phy(k)= asind(y01r/(rho)+sin(T0R*pi/180));
XR1(k)=X01R-rho*(cos(phy(k)*pi/180)-cos(T0R*pi/180));
x01r=XR1(k); k=k+1;
end
plot(XR1,YR1, 'r')
Warning: Imaginary parts of complex X and/or Y arguments ignored.
%Second curve
a=1;
T1L= asind(rho*sin(T0*pi/180)/(rho+W/2-(a*T)));
X1L=X0+(rho*cos(T0*pi/180)-(rho+W/2-(a*T))*cos(T1L*pi/180));
x1l=X1L; y1l=Y0; m=1;
while (x1l>=0) && (y1l<=h)
Y1L(m)=Y0+(m-1)*h/500; y1l=Y1L(m);
phy(m)= asind(y1l/(rho)+sin(T1L*pi/180)); %% Fiber angle
XL1(m)=X1L-rho*(cos(phy(m)*pi/180)-cos(T1L*pi/180));
x1l=XL1(m); m=m+1;
end
hold on
plot(XL1,Y1L, '-y')
Warning: Imaginary parts of complex X and/or Y arguments ignored.
xlim([0 60])
% Check your program: The curve coordinates have complex number
% Use the fileexchange function to find the interaction points
[x0,y0] = intersections(real(XR1), real(YR1), real(XL1), real(Y1L));
plot(x0, y0, 'ro', 'MarkerFaceColor', 'r')
function [x0,y0,iout,jout] = intersections(x1,y1,x2,y2,robust)
%INTERSECTIONS Intersections of curves.
% Computes the (x,y) locations where two curves intersect. The curves
% can be broken with NaNs or have vertical segments.
%
% Example:
% [X0,Y0] = intersections(X1,Y1,X2,Y2,ROBUST);
%
% where X1 and Y1 are equal-length vectors of at least two points and
% represent curve 1. Similarly, X2 and Y2 represent curve 2.
% X0 and Y0 are column vectors containing the points at which the two
% curves intersect.
%
% ROBUST (optional) set to 1 or true means to use a slight variation of the
% algorithm that might return duplicates of some intersection points, and
% then remove those duplicates. The default is true, but since the
% algorithm is slightly slower you can set it to false if you know that
% your curves don't intersect at any segment boundaries. Also, the robust
% version properly handles parallel and overlapping segments.
%
% The algorithm can return two additional vectors that indicate which
% segment pairs contain intersections and where they are:
%
% [X0,Y0,I,J] = intersections(X1,Y1,X2,Y2,ROBUST);
%
% For each element of the vector I, I(k) = (segment number of (X1,Y1)) +
% (how far along this segment the intersection is). For example, if I(k) =
% 45.25 then the intersection lies a quarter of the way between the line
% segment connecting (X1(45),Y1(45)) and (X1(46),Y1(46)). Similarly for
% the vector J and the segments in (X2,Y2).
%
% You can also get intersections of a curve with itself. Simply pass in
% only one curve, i.e.,
%
% [X0,Y0] = intersections(X1,Y1,ROBUST);
%
% where, as before, ROBUST is optional.
% Version: 2.0, 25 May 2017
% Author: Douglas M. Schwarz
% Email: dmschwarz=ieee*org, dmschwarz=urgrad*rochester*edu
% Real_email = regexprep(Email,{'=','*'},{'@','.'})
% Theory of operation:
%
% Given two line segments, L1 and L2,
%
% L1 endpoints: (x1(1),y1(1)) and (x1(2),y1(2))
% L2 endpoints: (x2(1),y2(1)) and (x2(2),y2(2))
%
% we can write four equations with four unknowns and then solve them. The
% four unknowns are t1, t2, x0 and y0, where (x0,y0) is the intersection of
% L1 and L2, t1 is the distance from the starting point of L1 to the
% intersection relative to the length of L1 and t2 is the distance from the
% starting point of L2 to the intersection relative to the length of L2.
%
% So, the four equations are
%
% (x1(2) - x1(1))*t1 = x0 - x1(1)
% (x2(2) - x2(1))*t2 = x0 - x2(1)
% (y1(2) - y1(1))*t1 = y0 - y1(1)
% (y2(2) - y2(1))*t2 = y0 - y2(1)
%
% Rearranging and writing in matrix form,
%
% [x1(2)-x1(1) 0 -1 0; [t1; [-x1(1);
% 0 x2(2)-x2(1) -1 0; * t2; = -x2(1);
% y1(2)-y1(1) 0 0 -1; x0; -y1(1);
% 0 y2(2)-y2(1) 0 -1] y0] -y2(1)]
%
% Let's call that A*T = B. We can solve for T with T = A\B.
%
% Once we have our solution we just have to look at t1 and t2 to determine
% whether L1 and L2 intersect. If 0 <= t1 < 1 and 0 <= t2 < 1 then the two
% line segments cross and we can include (x0,y0) in the output.
%
% In principle, we have to perform this computation on every pair of line
% segments in the input data. This can be quite a large number of pairs so
% we will reduce it by doing a simple preliminary check to eliminate line
% segment pairs that could not possibly cross. The check is to look at the
% smallest enclosing rectangles (with sides parallel to the axes) for each
% line segment pair and see if they overlap. If they do then we have to
% compute t1 and t2 (via the A\B computation) to see if the line segments
% cross, but if they don't then the line segments cannot cross. In a
% typical application, this technique will eliminate most of the potential
% line segment pairs.
% Input checks.
if verLessThan('matlab','7.13')
error(nargchk(2,5,nargin)) %#ok<NCHKN>
else
narginchk(2,5)
end
% Adjustments based on number of arguments.
switch nargin
case 2
robust = true;
x2 = x1;
y2 = y1;
self_intersect = true;
case 3
robust = x2;
x2 = x1;
y2 = y1;
self_intersect = true;
case 4
robust = true;
self_intersect = false;
case 5
self_intersect = false;
end
% x1 and y1 must be vectors with same number of points (at least 2).
if sum(size(x1) > 1) ~= 1 || sum(size(y1) > 1) ~= 1 || ...
length(x1) ~= length(y1)
error('X1 and Y1 must be equal-length vectors of at least 2 points.')
end
% x2 and y2 must be vectors with same number of points (at least 2).
if sum(size(x2) > 1) ~= 1 || sum(size(y2) > 1) ~= 1 || ...
length(x2) ~= length(y2)
error('X2 and Y2 must be equal-length vectors of at least 2 points.')
end
% Force all inputs to be column vectors.
x1 = x1(:);
y1 = y1(:);
x2 = x2(:);
y2 = y2(:);
% Compute number of line segments in each curve and some differences we'll
% need later.
n1 = length(x1) - 1;
n2 = length(x2) - 1;
xy1 = [x1 y1];
xy2 = [x2 y2];
dxy1 = diff(xy1);
dxy2 = diff(xy2);
% Determine the combinations of i and j where the rectangle enclosing the
% i'th line segment of curve 1 overlaps with the rectangle enclosing the
% j'th line segment of curve 2.
% Original method that works in old MATLAB versions, but is slower than
% using binary singleton expansion (explicit or implicit).
% [i,j] = find( ...
% repmat(mvmin(x1),1,n2) <= repmat(mvmax(x2).',n1,1) & ...
% repmat(mvmax(x1),1,n2) >= repmat(mvmin(x2).',n1,1) & ...
% repmat(mvmin(y1),1,n2) <= repmat(mvmax(y2).',n1,1) & ...
% repmat(mvmax(y1),1,n2) >= repmat(mvmin(y2).',n1,1));
% Select an algorithm based on MATLAB version and number of line
% segments in each curve. We want to avoid forming large matrices for
% large numbers of line segments. If the matrices are not too large,
% choose the best method available for the MATLAB version.
if n1 > 1000 || n2 > 1000 || verLessThan('matlab','7.4')
% Determine which curve has the most line segments.
if n1 >= n2
% Curve 1 has more segments, loop over segments of curve 2.
ijc = cell(1,n2);
min_x1 = mvmin(x1);
max_x1 = mvmax(x1);
min_y1 = mvmin(y1);
max_y1 = mvmax(y1);
for k = 1:n2
k1 = k + 1;
ijc{k} = find( ...
min_x1 <= max(x2(k),x2(k1)) & max_x1 >= min(x2(k),x2(k1)) & ...
min_y1 <= max(y2(k),y2(k1)) & max_y1 >= min(y2(k),y2(k1)));
ijc{k}(:,2) = k;
end
ij = vertcat(ijc{:});
i = ij(:,1);
j = ij(:,2);
else
% Curve 2 has more segments, loop over segments of curve 1.
ijc = cell(1,n1);
min_x2 = mvmin(x2);
max_x2 = mvmax(x2);
min_y2 = mvmin(y2);
max_y2 = mvmax(y2);
for k = 1:n1
k1 = k + 1;
ijc{k}(:,2) = find( ...
min_x2 <= max(x1(k),x1(k1)) & max_x2 >= min(x1(k),x1(k1)) & ...
min_y2 <= max(y1(k),y1(k1)) & max_y2 >= min(y1(k),y1(k1)));
ijc{k}(:,1) = k;
end
ij = vertcat(ijc{:});
i = ij(:,1);
j = ij(:,2);
end
elseif verLessThan('matlab','9.1')
% Use bsxfun.
[i,j] = find( ...
bsxfun(@le,mvmin(x1),mvmax(x2).') & ...
bsxfun(@ge,mvmax(x1),mvmin(x2).') & ...
bsxfun(@le,mvmin(y1),mvmax(y2).') & ...
bsxfun(@ge,mvmax(y1),mvmin(y2).'));
else
% Use implicit expansion.
[i,j] = find( ...
mvmin(x1) <= mvmax(x2).' & mvmax(x1) >= mvmin(x2).' & ...
mvmin(y1) <= mvmax(y2).' & mvmax(y1) >= mvmin(y2).');
end
% Find segments pairs which have at least one vertex = NaN and remove them.
% This line is a fast way of finding such segment pairs. We take
% advantage of the fact that NaNs propagate through calculations, in
% particular subtraction (in the calculation of dxy1 and dxy2, which we
% need anyway) and addition.
% At the same time we can remove redundant combinations of i and j in the
% case of finding intersections of a line with itself.
if self_intersect
remove = isnan(sum(dxy1(i,:) + dxy2(j,:),2)) | j <= i + 1;
else
remove = isnan(sum(dxy1(i,:) + dxy2(j,:),2));
end
i(remove) = [];
j(remove) = [];
% Initialize matrices. We'll put the T's and B's in matrices and use them
% one column at a time. AA is a 3-D extension of A where we'll use one
% plane at a time.
n = length(i);
T = zeros(4,n);
AA = zeros(4,4,n);
AA([1 2],3,:) = -1;
AA([3 4],4,:) = -1;
AA([1 3],1,:) = dxy1(i,:).';
AA([2 4],2,:) = dxy2(j,:).';
B = -[x1(i) x2(j) y1(i) y2(j)].';
% Loop through possibilities. Trap singularity warning and then use
% lastwarn to see if that plane of AA is near singular. Process any such
% segment pairs to determine if they are colinear (overlap) or merely
% parallel. That test consists of checking to see if one of the endpoints
% of the curve 2 segment lies on the curve 1 segment. This is done by
% checking the cross product
%
% (x1(2),y1(2)) - (x1(1),y1(1)) x (x2(2),y2(2)) - (x1(1),y1(1)).
%
% If this is close to zero then the segments overlap.
% If the robust option is false then we assume no two segment pairs are
% parallel and just go ahead and do the computation. If A is ever singular
% a warning will appear. This is faster and obviously you should use it
% only when you know you will never have overlapping or parallel segment
% pairs.
if robust
overlap = false(n,1);
warning_state = warning('off','MATLAB:singularMatrix');
% Use try-catch to guarantee original warning state is restored.
try
lastwarn('')
for k = 1:n
T(:,k) = AA(:,:,k)\B(:,k);
[unused,last_warn] = lastwarn; %#ok<ASGLU>
lastwarn('')
if strcmp(last_warn,'MATLAB:singularMatrix')
% Force in_range(k) to be false.
T(1,k) = NaN;
% Determine if these segments overlap or are just parallel.
overlap(k) = rcond([dxy1(i(k),:);xy2(j(k),:) - xy1(i(k),:)]) < eps;
end
end
warning(warning_state)
catch err
warning(warning_state)
rethrow(err)
end
% Find where t1 and t2 are between 0 and 1 and return the corresponding
% x0 and y0 values.
in_range = (T(1,:) >= 0 & T(2,:) >= 0 & T(1,:) <= 1 & T(2,:) <= 1).';
% For overlapping segment pairs the algorithm will return an
% intersection point that is at the center of the overlapping region.
if any(overlap)
ia = i(overlap);
ja = j(overlap);
% set x0 and y0 to middle of overlapping region.
T(3,overlap) = (max(min(x1(ia),x1(ia+1)),min(x2(ja),x2(ja+1))) + ...
min(max(x1(ia),x1(ia+1)),max(x2(ja),x2(ja+1)))).'/2;
T(4,overlap) = (max(min(y1(ia),y1(ia+1)),min(y2(ja),y2(ja+1))) + ...
min(max(y1(ia),y1(ia+1)),max(y2(ja),y2(ja+1)))).'/2;
selected = in_range | overlap;
else
selected = in_range;
end
xy0 = T(3:4,selected).';
% Remove duplicate intersection points.
[xy0,index] = unique(xy0,'rows');
x0 = xy0(:,1);
y0 = xy0(:,2);
% Compute how far along each line segment the intersections are.
if nargout > 2
sel_index = find(selected);
sel = sel_index(index);
iout = i(sel) + T(1,sel).';
jout = j(sel) + T(2,sel).';
end
else % non-robust option
for k = 1:n
[L,U] = lu(AA(:,:,k));
T(:,k) = U\(L\B(:,k));
end
% Find where t1 and t2 are between 0 and 1 and return the corresponding
% x0 and y0 values.
in_range = (T(1,:) >= 0 & T(2,:) >= 0 & T(1,:) < 1 & T(2,:) < 1).';
x0 = T(3,in_range).';
y0 = T(4,in_range).';
% Compute how far along each line segment the intersections are.
if nargout > 2
iout = i(in_range) + T(1,in_range).';
jout = j(in_range) + T(2,in_range).';
end
end
% Plot the results (useful for debugging).
% plot(x1,y1,x2,y2,x0,y0,'ok');
end
function y = mvmin(x)
% Faster implementation of movmin(x,k) when k = 1.
y = min(x(1:end-1),x(2:end));
end
function y = mvmax(x)
% Faster implementation of movmax(x,k) when k = 1.
y = max(x(1:end-1),x(2:end));
end

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!