1 %% Copyright (C) 2008-2012 David Legland <david.legland@grignon.inra.fr>
2 %% All rights reserved.
4 %% Redistribution and use in source and binary forms, with or without
5 %% modification, are permitted provided that the following conditions are met:
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.
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.
24 %% 2012 Adapted to Octave by Juan Pablo Carbajal <carbajal@ifi.uzh.ch>
27 %% @deftypefn {Function File} {@var{edges} = } knnGrpah (@var{nodes})
28 %% Create the k-nearest neighbors graph of a set of points
30 %% EDGES = knnGraph(NODES)
35 %% nodes = rand(10, 2);
36 %% edges = knnGraph(nodes);
37 %% drawGraph(nodes, edges);
43 function edges = knnGraph(nodes, varargin)
45 % get number of neighbors for each node
53 edges = zeros(k*n, 2);
57 dists = distancePoints(nodes(i,:), nodes);
58 [dists inds] = sort(dists); %#ok<ASGLU>
60 edges(k*(i-1)+j, :) = [i inds(j+1)];
65 edges = unique(sort(edges, 2), 'rows');
70 %! nodes = rand(10, 2);
71 %! edges = knnGraph(nodes);
72 %! drawGraph(nodes, edges);