Path: news.mathworks.com!not-for-mail
From: "Alan B" <monguin61@yahoo.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: finding minimum distance in a set of points
Date: Fri, 1 Aug 2008 15:41:02 +0000 (UTC)
Organization: UT
Lines: 89
Message-ID: <g6vaqe$ig5$1@fred.mathworks.com>
References: <g6v8fd$ntc$1@fred.mathworks.com> <g6va22$1vg$1@fred.mathworks.com>
Reply-To: "Alan B" <monguin61@yahoo.com>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1217605262 18949 172.30.248.37 (1 Aug 2008 15:41:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 1 Aug 2008 15:41:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1446885
Xref: news.mathworks.com comp.soft-sys.matlab:483127



"Bruno Luong" <b.luong@fogale.findmycountry> wrote in
message <g6va22$1vg$1@fred.mathworks.com>...
> "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
> 
> 
> 

Thanks, Bruno. Actually, the first method seems to be faster
than the delaunay method for me, for N<1000, which is big
enough for me. I guess your method uses less memory though,
and it looks like I can extend it to 3D, with delaunay3,
which is basically what I want.