Path: news.mathworks.com!not-for-mail
From: "Bruno Luong" <b.luong@fogale.findmycountry>
Newsgroups: comp.soft-sys.matlab
Subject: Re: finding minimum distance in a set of points
Date: Fri, 1 Aug 2008 15:28:02 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 81
Message-ID: <g6va22$1vg$1@fred.mathworks.com>
References: <g6v8fd$ntc$1@fred.mathworks.com>
Reply-To: "Bruno Luong" <b.luong@fogale.findmycountry>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1217604482 2032 172.30.248.38 (1 Aug 2008 15:28:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 1 Aug 2008 15:28:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:483117



"Alan B" <monguin61@yahoo.com> wrote in message
<g6v8fd$ntc$1@fred.mathworks.com>...
> Is there a good way in Matlab to find the minimum
> point-point distance in a set of points? I've come up with a
> few methods, and the best I've figured out so far is this:
> 
> N=10; % probably will want bigger N
> 
> % generate N points in 2D
> p=rand(N,2);
> 
> % generate N*(N-1)/2 x 2 array of pair indices
> [x y]=meshgrid(1:N);
> i=find(triu(ones(N)-eye(N)));
> i=[x(i) y(i)];
> 
> % compute all pairwise distances
> d2=(p(i(:,1),1)-p(i(:,2),1)).^2 + ...
>    (p(i(:,1),2)-p(i(:,2),2)).^2;
> 
> % find minimum distance and corresponding points
> [d2min imin]=min(d2);
> dmin=sqrt(d2min)
> p1 = p(i(imin,1),:)
> p2 = p(i(imin,2),:)
> 
> This seems to work pretty well, it beats for loops for N>20
> or so on my computer, but it seems like there should be a
> better way. Also, I don't see a straightforward way to
> extend this to higher dimensions, which I would like to do.
> 
> I basically wrote for loops to do it, and then tried to come
> up with an array of the indices that the for loops would
> generate, in order to vectorize the operation. This is easy
> for 2D, using triu, but is there some way to generate a
> similar set of index pairs in higher dimensions? Or what if
> I wanted to generate index triplets? Or index M-tuplets in D
> dimensions? Are there any built-in functions that do this
> kind of thing?

Don't do that, use delaunay and delaunayn:

N=10000; % is it big enough?

% generate N points in 2D
p=rand(N,2);

tic
% generate N*(N-1)/2 x 2 array of pair indices
[x y]=meshgrid(1:N);
i=find(triu(ones(N)-eye(N)));
i=[x(i) y(i)];

% compute all pairwise distances
d2=(p(i(:,1),1)-p(i(:,2),1)).^2 + ...
   (p(i(:,1),2)-p(i(:,2),2)).^2;

% find minimum distance and corresponding points
[d2min imin]=min(d2);
dmin=sqrt(d2min) % 13.596138 seconds.
toc 

% Delaunay way:

tic
tri=delaunay(p(:,1),p(:,2));
d2fun = @(k,l) sum((p(k,:)-p(l,:)).^2,2);
d2tri = @(k) [d2fun(tri(k,1),tri(k,2)) ...
              d2fun(tri(k,2),tri(k,3)) ...
              d2fun(tri(k,3),tri(k,1))];
dtri=cell2mat(arrayfun(@(k) d2tri(k),...
              (1:size(tri,1))','UniformOutput',0));
d=sqrt(min(dtri(:))) % 1.002932 seconds 
toc

The effect may be even greater for higher dimensions.

Bruno