Visualisation of non overlapping code

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
    n = find(gradient(TAN)>0); m = find(gradient(TAN)<0); 
    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
    n = find(gradient(TAN)>0); m = find(gradient(TAN)<0); 
    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

Answer 1

[Ishu]

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.

For more information you can refer these documentations:

https://www.mathworks.com/help/matlab/ref/plot.html?searchHighlight=plot&s_tid=srchtitle_support_results_1_plot

https://www.mathworks.com/help/matlab/creating_plots/combine-multiple-plots.html?searchHighlight=plot&s_tid=srchtitle_support_results_4_plot

Hope it helps!