octave_packages/geometry-1.5.0/graphs/knnGraph.m

   1 %% Copyright (C) 2008-2012 David Legland <david.legland@grignon.inra.fr>
   2 %% All rights reserved.
   3 %%
   4 %% Redistribution and use in source and binary forms, with or without
   5 %% modification, are permitted provided that the following conditions are met:
   6 %%
   7 %%   1 Redistributions of source code must retain the above copyright notice,
   8 %%   this list of conditions and the following disclaimer.
   9 %%   2 Redistributions in binary form must reproduce the above copyright
  10 %%   notice, this list of conditions and the following disclaimer in the
  11 %%   documentation and/or other materials provided with the distribution.
  12 %%
  13 %% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ''AS IS''
  14 %% AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15 %% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  16 %% ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR
  17 %% ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  18 %% DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  19 %% SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  20 %% CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  21 %% OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  22 %% OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  23 %%
  24 %% 2012 Adapted to Octave by Juan Pablo Carbajal <carbajal@ifi.uzh.ch>
  25
  26 %% -*- texinfo -*-
  27 %% @deftypefn {Function File} {@var{edges} = } knnGrpah (@var{nodes})
  28 %% Create the k-nearest neighbors graph of a set of points
  29 %%
  30 %% EDGES = knnGraph(NODES)
  31 %%
  32 %% Example
  33 %% @example
  34 %%
  35 %% nodes = rand(10, 2);
  36 %% edges = knnGraph(nodes);
  37 %% drawGraph(nodes, edges);
  38 %%
  39 %% @end example
  40 %%
  41 %% @end deftypefn
  42
  43 function edges = knnGraph(nodes, varargin)
  44
  45   % get number of neighbors for each node
  46   k = 2;
  47   if ~isempty(varargin)
  48   k = varargin{1};
  49   end
  50
  51   % init size of arrays
  52   n   = size(nodes, 1);
  53   edges = zeros(k*n, 2);
  54
  55   % iterate on nodes
  56   for i = 1:n
  57   dists = distancePoints(nodes(i,:), nodes);
  58   [dists inds]  = sort(dists); %#ok<ASGLU>
  59   for j = 1:k
  60     edges(k*(i-1)+j, :) = [i inds(j+1)];
  61   end
  62   end
  63
  64   % remove double edges
  65   edges = unique(sort(edges, 2), 'rows');
  66
  67 endfunction
  68
  69 %!demo
  70 %! nodes = rand(10, 2);
  71 %! edges = knnGraph(nodes);
  72 %! drawGraph(nodes, edges);
  73 %! axis tight