Distance between any combination of two points

Question

I have 100 coordinates in a variable x in MATLAB . How can I make sure that distance between all combinations of two points is greater than 1?

I voted down because the OP has shown no effort. I originally voted up because this was an interesting question, but when looking at the next question that the OP asked.. it again showed no effort, so I decided to downvote both questions to signal to the OP that he/she needs to correct the behaviour. — rayryeng, May 18 '15 at 08:10
@Adiel - Do you mean `pdist`? `dist` is part of the Neural Networks Toolbox, and I can't see how you'd use that function for this problem. — rayryeng, May 18 '15 at 08:11
Oh, Yes, you right. It's my mistake, I did mean `pdist` :) Too much time since used it... — Adiel, May 18 '15 at 12:24

score 4 · Accepted Answer · answered May 18 '15 at 05:16

4

You can do this in just one simple line, with the functions all and pdist:

if all(pdist(x)>1)
    ...
end

Best,

answered May 18 '15 at 05:16

Ratbert

5,463
2
18
37

*face palm*. Why didn't I think to use `pdist`?... well, the only solace I have is that I don't need the Stats toolbox for my answer. lol. – rayryeng May 18 '15 at 05:26
1

@DeepakKarunakaran - You can mark this answer as accepted which signifies to the StackOverflow community that you don't need any more help. That's done by going to the top of this post, and clicking on the checkmark that is to the left below the up and down voting buttons. – rayryeng May 18 '15 at 08:03

score 1 · Answer 2 · edited May 23 '17 at 12:15

First you'll need to generate a matrix that gives you all possible pairs of coordinates. This post can serve as inspiration:

Generate a matrix containing all combinations of elements taken from n vectors

I'm going to assume that your coordinates are stored such that the columns denote the dimensionality and the rows denote how many points you have. As such, for 2D, you would have a 100 x 2 matrix, and in 3D you would have a 100 x 3 matrix and so on.

Once you generate all possible combinations, you simply compute the distance... which I will assume it to be Euclidean here... of all points and ensure that all of them are greater than 1.

As such:

%// Taken from the linked post
vectors = { 1:100, 1:100 }; %// input data: cell array of vectors

n = numel(vectors); %// number of vectors
combs = cell(1,n); %// pre-define to generate comma-separated list
[combs{end:-1:1}] = ndgrid(vectors{end:-1:1}); %// the reverse order in these two
%// comma-separated lists is needed to produce the rows of the result matrix in
%// lexicographical order 
combs = cat(n+1, combs{:}); %// concat the n n-dim arrays along dimension n+1
combs = reshape(combs,[],n); %// reshape to obtain desired matrix

%// Index into your coordinates array
source_points = x(combs(:,1), :);
end_points = x(combs(:,2), :);

%// Checks to see if all distances are greater than 1
is_separated = all(sqrt(sum((source_points - end_points).^2, 2)) > 1);

is_separated will contain either 1 if all points are separated by a distance of 1 or greater and 0 otherwise. If we dissect the last line of code, it's a three step procedure:

sum((source_points - end_points).^2, 2) computes the pairwise differences between each component for each pair of points, squares the differences and then sums all of the values together.
sqrt(...(1)...) computes the square root which gives us the Euclidean distance.
all(...(2)... > 1) then checks to see if all of the distances computed in Step #2 were greater than 1 and our result thus follows.

Distance between any combination of two points

2 Answers2