How to find the longest distance normal to line from the dataplot?

I am actually trying to reproduce the epsilon value for DBSCAN, The reason being that when i use built-in function, MATLAB gives an error that the dataset are too big to be accommodated in the memory. So I want into the documentation and attempted to make the graph myself.

So, I want to carry out the estimation psuedo-manually. For that I have the elbow plot as shown in the data.

load("array.mat")
plot(array)
hold on
plot([1 length(array)], [array(1) array(end)], '--', Color='k')

Now, I am trying to find the maximum normal distance and the index of that index to find the value where the y value changes abruptly with x. In my calculation, it comes out to be roughly 0.034. I cannot figure out how to find the "furthest pooint from the dashed line" which is calculated by drawing a line normal to the dashed line and intersects with the "array" line (reference to first figure).

I have attempted using the gradient tool, but it didn't help. I tried to divide the diagonal line into the number of points equal to the number of points, and then finding the point distance, from the array line. But I was not successful because the factore of "normal" could not be accommodated in it.

Your Help will be much appreciated. Have a good day.

Answer 1

[Jan]

If you rotate the X and Y coordinates of the graph such that the connection between start and end point is parallel the X axis, the minumum value is the point with the biggest distance.

x = linspace(0, 2.5, 100);
y = x.^2 + 1;

m     = (y(end) - y(1)) / (x(end) - x(1));
alpha = atan(m);
R     = [cos(alpha), sin(alpha); -sin(alpha), cos(alpha)];
rotXY = R * [x; y];
xr    = rotXY(1, :);
yr    = rotXY(2, :);

plot(x, y, 'r'); hold('on');
plot(x([1, end]), y([1, end]), 'r--');
plot(xr, yr, 'b')
plot(xr([1, end]), yr([1, end]), 'b--')
[yr_min, ind] = min(yr);
xr_min        = xr(ind);
plot(xr_min, yr_min, 'bo');

Now you can rotate [x_min; y_min] backwards using R.' to find the point on the original curve.

pmin = R.' * [xr_min; yr_min];
plot(pmin(1), pmin(2), 'ro')

Of cousre this can be simplified, but this method is easy to remember.

[UH]

Thanks Jan. This is a very intuitive way.

After asking question, I made another line with negative slope and then moved it along the first diagonal line while using the polyxpoly to find intersection. It was a long loop (still running). It somehow works but takes a lot of time. I will apply your approach, maybe it will save time. Thank you for a detailed explanation.

[Jan]

@UH: A direct approach:

% The curve:
x = linspace(0, 2.5, 100);
y = x.^2 + 1;
r = [x; y];

% The line from P to Q - need not be from start to end point:
P = r(:, 1);
Q = r(:, end);

N    = (Q - P) / norm(Q - P);  % Normal vector along line
NPQ  = N.' * (r - P);          % Dot product between N and line
S    = P + NPQ .* N;           % Point on line
Dist = vecnorm(S - r, 2, 1);   % Distance between corresponding points
[maxDist, ind] = max(Dist);    % Largest distance and its index

plot(x, y, 'r'); hold('on'); axis('equal');  % Visualization
plot(x([1, end]), y([1, end]), 'r--');
plot(x(ind), y(ind), 'bo');
plot(S(1, ind), S(2, ind), 'b+');