# Visualisation of non overlapping code

3 views (last 30 days)
Shubham on 25 Apr 2023
Answered: Ishu on 8 Sep 2023
Following is a code which is based on a vector based approch and is used to check overlap between two ellipses. I am not able to visualise the algorithm. I want you to help me visualise this. Why tangent at every point then why diff tan > 90 is choosed etc.
It will be very helpful if someone can add plots to help me visualise the algorithm
t = linspace(0, 2*pi, 100);
x0 = 5;
y0 = 5;
a0 = 10;
b0 = 5;
theta0 = pi/4;
x1 = 8;
y1 = 8;
a1 = 8;
b1 = 4;
theta1 = pi/2;
% Ellipse 1
x = a0*cos(t);
y = b0*sin(t);
X0 = cos(theta0)*x - sin(theta0)*y;
Y0 = sin(theta0)*x + cos(theta0)*y;
X0 = X0 + x0;
Y0 = Y0 + y0;
% Ellipse 2
x = a1*cos(t);
y = b1*sin(t);
X1 = cos(theta1)*x - sin(theta1)*y;
Y1 = sin(theta1)*x + cos(theta1)*y;
X1 = X1 + x1;
Y1 = Y1 + y1;
overlap = overlap_ellipses(x0,y0,a0,b0,theta0,x1,y1,a1,b1,theta1)
%%%%%%%%%%%%%% Functions %%%%%%%%%%%%%
function overlap = overlap_ellipses(x0,y0,a0,b0,theta0,x1,y1,a1,b1,theta1)
overlap = -1;
NOP = 2^(5);
THETA=linspace(0,2*pi,NOP);
x = a0*cos(THETA);
y = b0*sin(THETA);
X0 = cos(theta0)*x - sin(theta0)*y;
Y0 = sin(theta0)*x + cos(theta0)*y;
X0 = X0 + x0;
Y0 = Y0 + y0;
x = a1*cos(THETA);
y = b1*sin(THETA);
X1 = cos(theta1)*x - sin(theta1)*y;
Y1 = sin(theta1)*x + cos(theta1)*y;
X1 = X1 + x1;
Y1 = Y1 + y1;
figure; hEllipse = plot(X0,Y0,'--'); axis equal; hold on; hEllipse = plot(X1,Y1,'--'); axis equal;
%% Third ellipse overlap check
% First, only use points on the ellipses that can possibly overlap. This
% works for most ellipses, but there may still be a few bugs (that will be
% corrected later). For each of these points, the closest point on the
% other ellipse is calculated. Then, using a vector-based criterion for
% each point, the overlap is calculated.
if overlap == -1
% Only use points that could possibly overlap
Ys = (Y1-y0); s = Ys == 0; Ys(s) = 0.01;
TAN = atan((X1-x0)./Ys);
if max(abs(diff(TAN))) > pi/2
m = sort(diff(TAN),'descend');
n = find(diff(TAN)==m(1));
o = find(diff(TAN)==m(end));
if o<n; p = o+1:n; TAN(p) = TAN(p)+pi; end
if o>n; p = n+1:o; TAN(p) = TAN(p)+pi; end
end
if length(n)>length(m); n=m; end;
X1 = X1(n); Y1=Y1(n);
% Only use points that could possibly overlap
Ys = (Y0-y1); s = Ys == 0; Ys(s) = 0.01;
TAN = atan((X0-x1)./Ys);
if max(abs(diff(TAN))) > pi/2
m = sort(diff(TAN),'descend');
n = find(diff(TAN)==m(1));
o = find(diff(TAN)==m(end));
if o<n; p = o+1:n; TAN(p) = TAN(p)+pi; end
if o>n; p = n+1:o; TAN(p) = TAN(p)-pi; end
end
if length(n)>length(m); n=m; end;
X0 = X0(n); Y0=Y0(n);
figure; hEllipse = plot(X0,Y0,'bo'); axis equal; hold on; hEllipse = plot(X1,Y1,'ro'); axis equal;
% Only check point with shortest distance away
clear CLOSE;
j = length(X0);
CLOSE(1:length(X0),1:3) = 0;
for i = 1:length(X0)
DIST = [X0(i)-X1;Y0(i)-Y1]';
NORM = sqrt(DIST(:,1).^2+DIST(:,2).^2);
n = find(NORM == min(NORM));
if length(n) == 1
CLOSE(i,1) = sort(NORM(n));
CLOSE(i,2) = i;
CLOSE(i,3) = n;
elseif length(n) == 2
CLOSE(i,1) = NORM(n(1));
CLOSE(i,2) = i;
CLOSE(i,3) = n(1);
j = j + 1;
CLOSE(j,1) = NORM(n(2));
CLOSE(j,2) = i;
CLOSE(j,3) = n(2);
end
end
% Weed out points that are furthest away
n = ceil(length(X0)/2);
if n > 2;
CLOSE_sort = sort(CLOSE); m = CLOSE_sort(n);
o = CLOSE(:,1) > m; CLOSE(o,:) = [];
end
if size(CLOSE,1) < 3;
overlap = 1; % Something screwy going on - REJECT
else
for ii = 1:size(CLOSE,1)
i = CLOSE(ii,2);
if i == 1; j = 1; else j=i-1; end;
if i == length(X0); k = length(X0); else k=i+1; end;
r12 = [X0(k)-X0(j) Y0(k)-Y0(j)];
r1 = [r12(2) -r12(1)]; %normal to ellipse
rc = [x0-X0(i) y0-Y0(i)];
n = dot(r1,rc);
if n < 0; r1 = -r1; end;
j = CLOSE(ii,3);
r2 = [X1(j)-X0(i) Y1(j)-Y0(i)];
n = dot(r1,r2);
if n > 0; overlap = 1; break; end;
if overlap == 1; break;end
end
end
end
%% Last overlap step
% Last, if none of the checks found an overlap between the two ellipses,
% then the overlap is 0.
if overlap == -1;
overlap = 0;
end
end

Ishu on 8 Sep 2023
Hi Shubham,
As you want to calculate if two ellipses are overlapping or not and your code initializes the variables 'x0', 'y0', 'a0', 'b0', 'theta0' for the first ellipse, and 'x1', 'y1', 'a1', 'b1', 'theta1' for the second ellipse.
1. The code first generates points on the first ellipse using the parameters 'a0', 'b0', and 'theta0'. Similarly, it generates points on the second ellipse using the parameters 'a1', 'b1', and 'theta1'.
2. The function then selects points on the ellipses that could possibly overlap based on their orientations.
3. It then calculates the closest point on each ellipse for each selected point.
4. The function checks if any points on the second ellipse fall inside the first ellipse using a vector-based criterion.
5. If there is an overlap, the variable overlap is set to 1; otherwise, it remains 0.
The tangent at each point on the ellipse is calculated to determine the orientation of the ellipse. And the reason for checking if the difference in tangent angles is greater than 90 degrees "diff(TAN) > pi/2" is to handle cases where the ellipses have a non-monotonic change in the tangent angle.
When the tangent angle changes rapidly, it indicates a change in the orientation of the ellipse. In such cases, there might be a possibility of the ellipse overlapping with itself due to a sharp change in its shape .
For the better visualization of overlapping you can plot "both the ellipses" and "the points that could possibly overlap" on the same figure, not the different ones.
Hope it helps!