nndist

NNDIST Nearest-neighbor distances of each point in a set.

   DISTS = nndist(POINTS)
   Returns the distance to the nearest neighbor of each point in an array
   of points.
   POINTS is an array of points, NP-by-ND.
   DISTS is a NP-by-1 array containing the distances to the nearest
   neighbor.

   This functions first computes the Delaunay triangulation of the set of
   points, then search for nearest distance in the set of each vertex
   neighbors. This reduces the overall complexity, but difference was
   noticed only for large sets (>10000 points)

   Example
     % Display Stienen diagram of a set of random points in unit square
     pts = rand(100, 2);
     [dists, inds] = nndist(pts);
     figure; drawPoint(pts, 'k.');
     hold on; drawCircle([pts dists/2], 'b');
     axis equal; axis([-.1 1.1 -.1 1.1]);
     % also display edges
     drawEdge([pts pts(inds, :)], 'b');

   See also
     points2d, distancePoints, minDistancePoints, findPoint

0001 function [dists, neighInds] = nndist(points)
0002 %NNDIST Nearest-neighbor distances of each point in a set.
0003 %
0004 %   DISTS = nndist(POINTS)
0005 %   Returns the distance to the nearest neighbor of each point in an array
0006 %   of points.
0007 %   POINTS is an array of points, NP-by-ND.
0008 %   DISTS is a NP-by-1 array containing the distances to the nearest
0009 %   neighbor.
0010 %
0011 %   This functions first computes the Delaunay triangulation of the set of
0012 %   points, then search for nearest distance in the set of each vertex
0013 %   neighbors. This reduces the overall complexity, but difference was
0014 %   noticed only for large sets (>10000 points)
0015 %
0016 %   Example
0017 %     % Display Stienen diagram of a set of random points in unit square
0018 %     pts = rand(100, 2);
0019 %     [dists, inds] = nndist(pts);
0020 %     figure; drawPoint(pts, 'k.');
0021 %     hold on; drawCircle([pts dists/2], 'b');
0022 %     axis equal; axis([-.1 1.1 -.1 1.1]);
0023 %     % also display edges
0024 %     drawEdge([pts pts(inds, :)], 'b');
0025 %
0026 %   See also
0027 %     points2d, distancePoints, minDistancePoints, findPoint
0028 %
0029 
0030 % ------
0031 % Author: David Legland
0032 % e-mail: david.legland@inra.fr
0033 % Created: 2011-12-01,    using Matlab 7.9.0.529 (R2009b)
0034 % Copyright 2011 INRA - Cepia Software Platform.
0035 
0036 % number of points
0037 n = size(points, 1);
0038 
0039 % allocate memory
0040 dists = zeros(n, 1);
0041 neighInds = zeros(n, 1);
0042 
0043 % in case of few points, use direct computation
0044 if n < 3
0045     inds = 1:n;
0046     for i = 1:n
0047         % compute minimal distance
0048         [dists(i), indN] = minDistancePoints(points(i,:), points(inds~=i, :));
0049         if indN >= i
0050             neighInds(i) = inds(indN) + 1;
0051         else
0052             neighInds(i) = inds(indN);
0053         end
0054     end
0055     return;
0056 end
0057 
0058 % use Delaunay Triangulation to facilitate computations
0059 DT = delaunay (points);
0060 
0061 % compute distance to nearest neighbor of each point in the pattern
0062 for i = 1:n
0063     % find indices of neighbor vertices in Delaunay Triangulation.
0064     % this set contains the nearest neighbor
0065     inds = unique(DT(sum(DT == i, 2) > 0, :));
0066     inds = inds(inds~=i);
0067     
0068     % compute minimal distance
0069     [dists(i), indN] = min(distancePoints(points(i,:), points(inds, :)));
0070     neighInds(i) = inds(indN);
0071 end