matlab实现kd_tree

用matlab实现kd_treed 代码，里面有详细的过程

function tree_output = kd_buildtree（Xplot_stuffparent_numbersplit_dimension）

% pramod vemulapalli 02/08/2010
% inspired by the work done by Jan Nunnink 2003.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% INPUTS
% X                --- contains the data （nxd） matrix  where n is the
%                      number of feature vectors and d is the dimensionality 
%                      of each feature vector 
% parent_number    --- Internal variable .... Donot Assign 
% split_dimension  --- Internal variable .... Donot Assign 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% OUTPUTS
% tree_output --- contains the a array of structs each struct is a node 
%                 node in the tree. The size of the array is equal to the 
%                 the number of feature vectors in the data matrix X 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% each struct in the output cell array contains the following information 
% left        -  （tree） left tree node location in the array 
% right       -  （tree） right tree node location in the array 
% numpoints   -  number of points in this node 
% nodevector  -  the median of the data along dimension that it is split 
% hyperrect   -  （2xd） hyperrectangle bounding the points 
% type        -  ‘leaf‘ = node is leaf
%                ‘node‘ = node has 2 children
% parent      -  the location of the parent of the current node in the
%                struct array 
% index       -  the index of the feature vector in the original matrix 
%                that was used to build the tree
% splitdim    -  the dimension along which the split is made 
% splitval    -  the value along that dimension in which the split is made 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

global tree_cell;
global node_number;
global safety_check;

if nargin ==2
    
    safety_check=0;
    
    % add the index values to the last column
    % easy way to keep track of them 
    [nd] = size（X）;
    X（:d+1）=1:n‘;
    node_number=1;
    split_dimension=0;
    parent_number=0;
    
    % intialize the node 
    Node.type=‘node‘; 
    Node.left=0;
    Node.right=0;
    Node.nodevector=zeros（1d）;
    Node.hyperrect=[zeros（1d）;zeros（1d）];
    Node.numpoints=0;
    Node.index=0;
    Node.parent=0;
    Node.splitval=0;
    
    % initilaze the tree 
    hold_cell_data（1:n）=Node;
    tree_cell=hold_cell_data;
    clear hold_cell_data;
    
else
    
    [nd] = size（X（:1:end-1））;
    node_number=node_number+1;
    split_dimension=split_dimension+1;
    
end

if （isempty（safety_check））    
    error （‘Some thing is wrong with the number of inout variables .... Please check‘）;
end 

if n==0 
    fprintf（‘Error: 0 points in node causing endless loop press ctrl-C.\n‘）; 
end

assigned_nn=node_number; % assigned node number for this particular iterat

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      57187  2010-02-11 17:05  kdtree_in_matlab\kdtree\example.jpg

     文件       6631  2010-02-17 20:10  kdtree_in_matlab\kdtree\kd_buildtree.m

     文件       2599  2010-02-17 19:07  kdtree_in_matlab\kdtree\kd_closestpointfast.m

     文件       3790  2010-02-17 19:08  kdtree_in_matlab\kdtree\kd_closestpointgood.m

     文件       2827  2010-02-17 21:40  kdtree_in_matlab\kdtree\kd_demo.m

     文件       6091  2010-02-17 21:40  kdtree_in_matlab\kdtree\kd_knn.m

     文件       2648  2010-02-07 14:25  kdtree_in_matlab\kdtree\kd_nclosestpoints.m

     文件       1443  2010-02-11 16:59  kdtree_in_matlab\kdtree\kd_plotbox.m

     文件       5296  2010-02-17 19:11  kdtree_in_matlab\kdtree\kd_rangequery.m

     文件       1566  2010-02-17 21:42  kdtree_in_matlab\license.txt

     目录          0  2010-02-17 21:42  kdtree_in_matlab\kdtree

     目录          0  2011-10-23 16:52  kdtree_in_matlab

----------- ---------  ---------- -----  ----

                90078                    12