Max. distance in a bidimensionnal vector

Hi everybody, I'm looking for a solution to find efficiently the longest distance between two elements in a vector, without having to calculate the distance between each element if possible. The vectors are the coordinate on a 2D plan of lines on an image.

I hope I've been clear enough

Thanks

[Jan]

This is not clear enough. Please specify what "distance between elements in a vector" means. And how can it be possible to find the larges distance without calculating all distances??

[Matt Tearle]

Also, how can you have a vector of 2D coordinates? Do you have a 1D cell array of vectors? Or a matrix, or...?

Answer 1

[Bruno Luong]

Here is something I wrote for my own use. The code is to prototype an algorithm which I did in C. S it is not speed optimized, but it gives you an idea:

function [d imax jmax] = dmax(X)
% [d imax jmax] = dmax(X)
%
% Compute the largest euclidian distance of a set 2D points
%
% INPUT: X is (npnt x 2)
% OUTPUT: d, largest distance
%         imax, jmax, index of two fathest points

MATLABflag=0;

K = myconvhull(X);

X = X(K,:);
npnt = size(X,1);

DX = bsxfun(@minus,X,X(1,:));
dx2 = sum(DX.^2,2);
[dmax2 jmax] = max(dx2);

IMAX = 1;
JMAX = jmax;

nextwrap = [2:npnt 1];
% plot(X([1 jmax],1),X([1 jmax],2),'r');

for i=2:jmax
    Xi = X(i,:);
    d2 = sum((X(jmax,:)-Xi).^2,2);
    while true
        next = nextwrap(jmax);
        dnext = sum((X(next,:)-Xi).^2,2);
        if dnext > d2
            d2 = dnext;
            jmax = next;
        else
            break
        end
    end % while loop
    % Keep track of the largest distance
    if (d2 > dmax2)
        dmax2 = d2;
        IMAX = i;
        JMAX = jmax;
    end
end % for-loop

d = sqrt(dmax2);
imax = K(IMAX);
jmax = K(JMAX);

end % dmax
function K = myconvhull(X)

     K = convhull(X);
     K(end) = []; % no repeated elements

[Jan]

If this efficient method really solves the OP's fuzzy formulated problem, you revealed that your crystal ball has magic power.

Answer 2

[Matt Tearle]

If Bruno's solution is what you want, and you have Statistics Toolbox, you can use pdist to calculate all the pairwise distances, then max to find the biggest (and indexing to find the locations).