1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

classdef KDTree < handle 
    %UNTITLED Summary of this class goes here
    %   Detailed explanation goes here
    
    properties
        my_axis = 0
        point_data
        checked
        Left
        Right
        Parent
    end
    
    methods
        function t =  KDTree (data, axis )
            t.point_data = data;
            t.my_axis = axis;
        end
        
        
        function parent = find_parent(obj,node)
            next = obj;
            while(isscalar(next))
                split = next.my_axis  ;
                parent = next ;
                if(node(split) > next.point_data(split))
                    next = next.Right ;
                else
                    next = next.Left ;
                end
            end
        end
        
        
        function new_node = insert(obj,node)
            parent = find_parent(obj,node);
            
            if(isequal(node,parent.point_data))
                new_node = parent;
                return ;
            end
            
            
            my_size = size(node);
            new_axis = (mod(parent.my_axis +1, my_size(2)+1 ));
            if new_axis == 0
                new_axis = 1;
            end
            new_node = KDTree(node, new_axis) ;
            
            if(node(parent.my_axis) > parent.point_data(parent.my_axis))
                parent.Right = new_node ;
            else
                parent.Left = new_node ;
            end
            new_node.Parent = parent ;
        end
        
        
        
        
        
        
        function nearest_neighbour = find_nearest(obj,element)
            parent = obj.find_parent(element);
            
            my_size = size(element);
            my_size = my_size(2);
            d_min = 0;
            for i = 1: my_size
                d_min = d_min + (element(i) - parent.point_data(i))^2;
            end
            d_min = sqrt(d_min);
            
            nearest_neighbour = parent ;

            if(isequal(element, parent.point_data))
                return ;
            end

            nearest_neighbour = check_subtree(obj, element,d_min,nearest_neighbour);

            return;
        end

        function nearest_neighbour_list =  check_subtree(node, element,  distance, nearest_neighbour_list)
            
            if(~isscalar(node))
                return
            end
                        
            my_size = size(element);
            my_size = my_size(2);
            d = 0;
            for i = 1: my_size
                d = d + (element(i) - node.point_data(i))^2;
            end
            d = sqrt(d);
            
            
            if(d<distance)  
                
                distance = d;
                temp_size = size(nearest_neighbour_list);
                nearest_neighbour_list(temp_size(2)+1) = node;
            end
            dim = node.my_axis ;
            d= node.point_data(dim) - element(dim);

            if (d*d > distance) 
                if (node.point_data(dim) > element(dim))
                    nearest_neighbour_list  = check_subtree(node.Left, element,distance, nearest_neighbour_list);
                else
                    nearest_neighbour_list = check_subtree(node.Right, element,distance, nearest_neighbour_list);
                end    
            else 
                nearest_neighbour_list = check_subtree(node.Left, element, distance, nearest_neighbour_list);
                nearest_neighbour_list = check_subtree(node.Right, element, distance, nearest_neighbour_list);
            end
        end
        
        
        
        
        
    end
end