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: Sat, 2 Aug 2008 09:20:03 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 40
Message-ID: <g718s3$40a$1@fred.mathworks.com>
References: <g6v8fd$ntc$1@fred.mathworks.com> <g6va22$1vg$1@fred.mathworks.com> <g6vaqe$ig5$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 1217668803 4106 172.30.248.38 (2 Aug 2008 09:20:03 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sat, 2 Aug 2008 09:20:03 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:483263



"Alan B" <monguin61@yahoo.com> wrote in message
<g6vaqe$ig5$1@fred.mathworks.com>...

> 
> 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. 

Alan, not yet my last word!!!

N=1000;

% 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) % 0.289896 seconds
toc 

% Delaunay way with array, even faster:
tic
tri=delaunay(p(:,1),p(:,2));
tri=tri(:,[1:end 1]);
dx = diff(reshape(p(tri,1),size(tri)),1,2);
dy = diff(reshape(p(tri,2),size(tri)),1,2);
dmin = sqrt(min(dx(:).^2+dy(:).^2)) % 0.093659 seconds
toc

% Bruno