kdtree.show() - Code Metrics - Inspection of "[publish][.] Merge 0.7.dev" - annoviko/pyclustering - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 55f4eb...4814fa )

by Andrei

created 2017-11-02 15:40 UTC

kdtree.show() B

↳ Parent: kdtree

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	5
dl	0
loc	24
rs	8.1671
c	0
b	0
f	0

"""!

@brief Data Structure: KD-Tree
@details Based on book description:
         - M.Samet. The Design And Analysis Of Spatial Data Structures. 1994.

@authors Andrei Novikov ([email protected])
@date 2014-2017
@copyright GNU Public License

@cond GNU_PUBLIC_LICENSE
    PyClustering is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
    
    PyClustering is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    
    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
@endcond

"""


from pyclustering.utils import euclidean_distance_sqrt;


class kdtree_text_visualizer:
    """!
    @brief KD-tree text visualizer that provides service to diplay tree structure using text representation.
    
    """

    def __init__(self, kdtree_instance):
        """!
        @brief Initialize KD-tree text visualizer.
        
        @param[in] kdtree_instance (kdtree): Instance of KD-Tree that should be visualized.
        
        """
        self.__kdtree_instance = kdtree_instance;
        
        self.__tree_level_text  = "";
        self.__tree_text        = "";

    def visualize(self, display=True):
        """!
        @brief Display KD-tree to console.
        
        @param[in] display (bool): If 'True' then tree will be shown in console.
        
        @return (string) Text representation of the KD-tree.
        
        """
        
        nodes = self.__get_nodes();
        level = nodes[0];
        
        for node in nodes:
param = 5

class Foo:
    def __init__(self, param):   # "param" would be flagged here
        self.param = param
            self.__print_node(level, node)

        self.__tree_text += self.__tree_level_text;
        if (display is True):
            print(self.__tree_text);
        
        return self.__tree_text;


    def __print_node(self, level, node):
param = 5

class Foo:
    def __init__(self, param):   # "param" would be flagged here
        self.param = param
        if (level == node[0]):
            self.__tree_level_text += str(node[1]) + "\t";

        else:
            self.__tree_text += self.__tree_level_text + "\n";
            level = node[0];
            self.__tree_level_text = str(node[1]) + "\t";


    def __get_nodes(self):
        nodes = self.__kdtree_instance.traverse();
        if (nodes == []):
            return;
        
        nodes.sort(key = lambda item: item[0]);
        return nodes;



class node:
    """!
    @brief Represents node of KD-Tree.
    
    """
    
    def __init__(self, data = None, payload = None, left = None, right = None, disc = None, parent = None):
        """!
        @brief 
        
        @param[in] data (list): Data point that is presented as list of coodinates.
        @param[in] payload (*): Payload of node (pointer to essense that is attached to this node).
        @param[in] left (node): Node of KD-Tree that is represented left successor.
        @param[in] right (node): Node of KD-Tree that is represented right successor.
        @param[in] disc (uint): Index of dimension of that node.
        @param[in] parent (node): Node of KD-Tree that is represented parent.
        
        """
        
        ## Data point that is presented as list of coodinates.
        self.data = data;
        
        ## Payload of node that can be used by user for storing specific information in the node.
        self.payload = payload;
        
        ## Left node successor of the node.
        self.left = left;
        
        ## Right node successor of the node.
        self.right = right;
        
        ## Index of dimension.
        self.disc = disc;
        
        ## Parent node of the node.
        self.parent = parent;


    def __repr__(self):
        """!
        @return (string) Default representation of the node.
        
        """
        left = None; 
        right = None; 
        
        if (self.left is not None):
            left = self.left.data;
            
        if (self.right is not None):
            right = self.right.data;
        
        return "(%s: [L:'%s', R:'%s'])" % (self.data, left, right);
    
    def __str__(self):
        """!
        @return (string) String representation of the node.
        
        """
        return self.__repr__();


class kdtree:
    """!
    @brief Represents KD Tree that is a space-partitioning data structure for organizing points in a k-dimensional space.
    
    Examples:
    @code
        # Import required modules
        from pyclustering.samples.definitions import SIMPLE_SAMPLES;
        from pyclustering.container.kdtree import kdtree;
        from pyclustering.utils import read_sample;
        
        # Read data from text file
        sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3);
        
        # Create instance of KD-tree and initialize (fill) it by read data.
        tree_instance = kdtree(sample);
        
        # Search for nearest point
        search_distance = 0.3;
        nearest_node = tree_instance.find_nearest_dist_node([1.12, 4.31], search_distance);
        
        # Search for nearest point in radius 0.3
        nearest_nodes = tree_instance.find_nearest_dist_nodes([1.12, 4.31], search_distance);
        print("Nearest nodes:", nearest_nodes);
    @endcode
    
    """
    
    def __init__(self, data_list = None, payload_list = None):
        """!
        @brief Create kd-tree from list of points and from according list of payloads.
        @details If lists were not specified then empty kd-tree will be created.
        
        @param[in] data_list (list): Insert points from the list to created KD tree.
        @param[in] payload_list (list): Insert payload from the list to created KD tree, length should be equal to length of data_list if it is specified.
        
        """
        
        self.__root = None;
        self.__dimension = None;
        
        if (data_list is None):
            return; # Just return from here, tree can be filled by insert method later
        
        if (payload_list is None):
            # Case when payload is not specified.
            for index in range(0, len(data_list)):
                self.insert(data_list[index], None);
        else:
            # Case when payload is specified.
            for index in range(0, len(data_list)):
                self.insert(data_list[index], payload_list[index]);


    def insert(self, point, payload):
        """!
        @brief Insert new point with payload to kd-tree.
        
        @param[in] point (list): Coordinates of the point of inserted node.
        @param[in] payload (*): Payload of inserted node.
        
        """
        
        if (self.__root is None):
            self.__dimension = len(point);
            self.__root = node(point, payload, None, None, 0);
            return self.__root;
        
        cur_node = self.__root;
        
        while True:
            if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
                # If new node is greater or equal than current node then check right leaf
                if (cur_node.right is None):
                    discriminator = cur_node.disc + 1;
                    if (discriminator >= self.__dimension):
                        discriminator = 0;
                        
                    cur_node.right = node(point, payload, None, None, discriminator, cur_node);
                    return cur_node.right;
                else: 
                    cur_node = cur_node.right;
            
            else:
                # If new node is less than current then check left leaf
                if (cur_node.left is None):
                    discriminator = cur_node.disc + 1;
                    if (discriminator >= self.__dimension):
                        discriminator = 0;
                        
                    cur_node.left = node(point, payload, None, None, discriminator, cur_node);
                    return cur_node.left;
                else:
                    cur_node = cur_node.left;
    
    
    def remove(self, point):
        """!
        @brief Remove specified point from kd-tree.
        
        @param[in] point (list): Coordinates of the point of removed node.
        
        @return (node) Root if node has been successfully removed, otherwise None.
        
        """
        
        # Get required node
        node_for_remove = self.find_node(point);
        if (node_for_remove is None):
            return None;
        
        parent = node_for_remove.parent;
        minimal_node = self.__recursive_remove(node_for_remove);
        if (parent is None):
            self.__root = minimal_node;
            
            # If all k-d tree was destroyed
            if (minimal_node is not None):
                minimal_node.parent = None;
        else:
            if (parent.left is node_for_remove):
                parent.left = minimal_node;
            elif (parent.right is node_for_remove):
                parent.right = minimal_node;
        
        return self.__root;
    
    
    def __recursive_remove(self, node_removed):
        """!
        @brief Delete node and return root of subtree.
        
        @param[in] node_removed (node): Node that should be removed.
        
        @return (node) Minimal node in line with coordinate that is defined by descriminator.
        
        """
                
        # Check if it is leaf
        if ( (node_removed.right is None) and (node_removed.left is None) ):
            return None;
        
        discriminator = node_removed.disc;
        
        # Check if only left branch exist
        if (node_removed.right is None):
            node_removed.right = node_removed.left;
            node_removed.left = None;
        
        # Find minimal node in line with coordinate that is defined by discriminator
        minimal_node = self.find_minimal_node(node_removed.right, discriminator);
        parent = minimal_node.parent;
        
        if (parent.left is minimal_node):
            parent.left = self.__recursive_remove(minimal_node);
        elif (parent.right is minimal_node):
            parent.right = self.__recursive_remove(minimal_node);
        
        minimal_node.parent = node_removed.parent;
        minimal_node.disc = node_removed.disc;
        minimal_node.right = node_removed.right;
        minimal_node.left = node_removed.left;
        
        # Update parent for successors of previous parent.
        if (minimal_node.right is not None):
            minimal_node.right.parent = minimal_node;
             
        if (minimal_node.left is not None):
            minimal_node.left.parent = minimal_node;
        
        return minimal_node;


    def find_minimal_node(self, node_head, discriminator):
        """!
        @brief Find minimal node in line with coordinate that is defined by discriminator.
        
        @param[in] node_head (node): Node of KD tree from that search should be started.
        @param[in] discriminator (uint): Coordinate number that is used for comparison.
        
        @return (node) Minimal node in line with descriminator from the specified node.
        
        """
        
        min_key = lambda cur_node: cur_node.data[discriminator];
        stack = [];
        candidates = [];
        isFinished = False;
        while isFinished is False:
            if node_head is not None:
                stack.append(node_head);
                node_head = node_head.left;
            else:
                if len(stack) != 0:
                    node_head = stack.pop();
                    candidates.append(node_head);
                    node_head = node_head.right;
                else:
                    isFinished = True;

        return min(candidates, key = min_key);
    
    
    def find_node(self, point, cur_node = None):
        """!
        @brief Find node with coordinates that are defined by specified point.
        @details If node does not exist then None will be returned. Otherwise required node will be returned.
        
        @param[in] point (list): Coordinates of the point whose node should be found.
        @param[in] cur_node (node): Node from which search should be started.
        
        @return (node) Node in case of existance of node with specified coordinates, otherwise it return None.
        
        """
        
        req_node = None;
        
        if (cur_node is None):
            cur_node = self.__root;
        
        while True:
            if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
                # Check if it's required node
                if (cur_node.data == point):
                    req_node = cur_node;
                    break;
                
                if (cur_node.right is not None):
                    cur_node = cur_node.right;
            
            else:
                if (cur_node.left is not None):
                    cur_node = cur_node.left;
                
        return req_node;
    
    
    
    def find_nearest_dist_node(self, point, distance, retdistance = False):
        """!
        @brief Find nearest neighbor in area with radius = distance.
        
        @param[in] point (list): Maximum distance where neighbors are searched.
        @param[in] distance (double): Maximum distance where neighbors are searched.
        @param[in] retdistance (bool): If True - returns neighbors with distances to them, otherwise only neighbors is returned.
        
        @return (node|list) Nearest neighbor if 'retdistance' is False and list with two elements [node, distance] if 'retdistance' is True,
                 where the first element is pointer to node and the second element is distance to it.
        
        """
        
        best_nodes = self.find_nearest_dist_nodes(point, distance);
            
        if (best_nodes == []): 
            return None;
        
        nearest = min(best_nodes, key = lambda item: item[0]);
        
        if (retdistance == True):
            return nearest;
        else:
            return nearest[1];
    
    
    def find_nearest_dist_nodes(self, point, distance):
        """!
        @brief Find neighbors that are located in area that is covered by specified distance.
        
        @param[in] point (list): Coordinates that is considered as centroind for searching.
        @param[in] distance (double): Distance from the center where seaching is performed.
        
        @return (list) Neighbors in area that is specified by point (center) and distance (radius).
        
        """

        best_nodes = [];
        if (self.__root is not None):
            self.__recursive_nearest_nodes(point, distance, distance ** 2, self.__root, best_nodes);

        return best_nodes;


    def __recursive_nearest_nodes(self, point, distance, sqrt_distance, node_head, best_nodes):
        """!
        @brief Returns list of neighbors such as tuple (distance, node) that is located in area that is covered by distance.
        
        @param[in] point (list): Coordinates that is considered as centroind for searching
        @param[in] distance (double): Distance from the center where seaching is performed.
        @param[in] sqrt_distance (double): Square distance from the center where searching is performed.
        @param[in] node_head (node): Node from that searching is performed.
        @param[in|out] best_nodes (list): List of founded nodes.
        
        """

        if (node_head.right is not None):
            minimum = node_head.data[node_head.disc] - distance;
            if (point[node_head.disc] >= minimum):
                self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.right, best_nodes);
        
        if (node_head.left is not None):
            maximum = node_head.data[node_head.disc] + distance;
            if (point[node_head.disc] < maximum):
                self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.left, best_nodes);
        
        candidate_distance = euclidean_distance_sqrt(point, node_head.data);
        if (candidate_distance <= sqrt_distance):
            best_nodes.append( (candidate_distance, node_head) );


    def children(self, node_parent):
        """!
        @brief Returns list of children of node.
        
        @param[in] node_parent (node): Node whose children are required. 
        
        @return (list) Children of node. If node haven't got any child then None is returned.
        
        """
        
        if (node_parent.left is not None):
            yield node_parent.left;
        if (node_parent.right is not None):
            yield node_parent.right;


    def traverse(self, start_node = None, level = None):
        """!
        @brief Traverses all nodes of subtree that is defined by node specified in input parameter.
        
        @param[in] start_node (node): Node from that travering of subtree is performed.
        @param[in, out] level (uint): Should be ignored by application.
        
        @return (list) All nodes of the subtree.
        
        """
        
        if (start_node is None):
            start_node  = self.__root;
            level = 0;
        
        if (start_node is None):
            return [];
        
        items = [ (level, start_node) ];
        for child in self.children(start_node):
            if child is not None:
                items += self.traverse(child, level + 1);
        
        return items;


1			"""!
2
3			@brief Data Structure: KD-Tree
4			@details Based on book description:
5			- M.Samet. The Design And Analysis Of Spatial Data Structures. 1994.
6
7			@authors Andrei Novikov ([email protected])
8			@date 2014-2017
9			@copyright GNU Public License
10
11			@cond GNU_PUBLIC_LICENSE
12			PyClustering is free software: you can redistribute it and/or modify
13			it under the terms of the GNU General Public License as published by
14			the Free Software Foundation, either version 3 of the License, or
15			(at your option) any later version.
16
17			PyClustering is distributed in the hope that it will be useful,
18			but WITHOUT ANY WARRANTY; without even the implied warranty of
19			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20			GNU General Public License for more details.
21
22			You should have received a copy of the GNU General Public License
23			along with this program. If not, see <http://www.gnu.org/licenses/>.
24			@endcond
25
26			"""
27
28
29			from pyclustering.utils import euclidean_distance_sqrt;
30
31
32			class kdtree_text_visualizer:
33			"""!
34			@brief KD-tree text visualizer that provides service to diplay tree structure using text representation.
35
36			"""
37
38			def __init__(self, kdtree_instance):
39			"""!
40			@brief Initialize KD-tree text visualizer.
41
42			@param[in] kdtree_instance (kdtree): Instance of KD-Tree that should be visualized.
43
44			"""
45			self.__kdtree_instance = kdtree_instance;
46
47			self.__tree_level_text = "";
48			self.__tree_text = "";
49
50			def visualize(self, display=True):
51			"""!
52			@brief Display KD-tree to console.
53
54			@param[in] display (bool): If 'True' then tree will be shown in console.
55
56			@return (string) Text representation of the KD-tree.
57
58			"""
59
60			nodes = self.__get_nodes();
61			level = nodes[0];
62
63			for node in nodes:
			0 ignored issues – show Comprehensibility Bug introduced 2017-10-23 12:23 UTC by Report Bug Copy Issue Report `node` is re-defining a name which is already available in the outer-scope (previously defined on line `93`). It is generally a bad practice to shadow variables from the outer-scope. In most cases, this is done unintentionally and might lead to unexpected behavior: param = 5 class Foo: def __init__(self, param): # "param" would be flagged here self.param = param Loading history...
64			self.__print_node(level, node)
65
66			self.__tree_text += self.__tree_level_text;
67			if (display is True):
68			print(self.__tree_text);
69
70			return self.__tree_text;
71
72
73			def __print_node(self, level, node):
			0 ignored issues – show Comprehensibility Bug introduced 2017-10-23 12:23 UTC by Report Bug Copy Issue Report `node` is re-defining a name which is already available in the outer-scope (previously defined on line `93`). It is generally a bad practice to shadow variables from the outer-scope. In most cases, this is done unintentionally and might lead to unexpected behavior: param = 5 class Foo: def __init__(self, param): # "param" would be flagged here self.param = param Loading history...
74			if (level == node[0]):
75			self.__tree_level_text += str(node[1]) + "\t";
76
77			else:
78			self.__tree_text += self.__tree_level_text + "\n";
79			level = node[0];
80			self.__tree_level_text = str(node[1]) + "\t";
81
82
83			def __get_nodes(self):
84			nodes = self.__kdtree_instance.traverse();
85			if (nodes == []):
86			return;
87
88			nodes.sort(key = lambda item: item[0]);
89			return nodes;
90
91
92
93			class node:
94			"""!
95			@brief Represents node of KD-Tree.
96
97			"""
98
99			def __init__(self, data = None, payload = None, left = None, right = None, disc = None, parent = None):
100			"""!
101			@brief
102
103			@param[in] data (list): Data point that is presented as list of coodinates.
104			@param[in] payload (*): Payload of node (pointer to essense that is attached to this node).
105			@param[in] left (node): Node of KD-Tree that is represented left successor.
106			@param[in] right (node): Node of KD-Tree that is represented right successor.
107			@param[in] disc (uint): Index of dimension of that node.
108			@param[in] parent (node): Node of KD-Tree that is represented parent.
109
110			"""
111
112			## Data point that is presented as list of coodinates.
113			self.data = data;
114
115			## Payload of node that can be used by user for storing specific information in the node.
116			self.payload = payload;
117
118			## Left node successor of the node.
119			self.left = left;
120
121			## Right node successor of the node.
122			self.right = right;
123
124			## Index of dimension.
125			self.disc = disc;
126
127			## Parent node of the node.
128			self.parent = parent;
129
130
131			def __repr__(self):
132			"""!
133			@return (string) Default representation of the node.
134
135			"""
136			left = None;
137			right = None;
138
139			if (self.left is not None):
140			left = self.left.data;
141
142			if (self.right is not None):
143			right = self.right.data;
144
145			return "(%s: [L:'%s', R:'%s'])" % (self.data, left, right);
146
147			def __str__(self):
148			"""!
149			@return (string) String representation of the node.
150
151			"""
152			return self.__repr__();
153
154
155			class kdtree:
156			"""!
157			@brief Represents KD Tree that is a space-partitioning data structure for organizing points in a k-dimensional space.
158
159			Examples:
160			@code
161			# Import required modules
162			from pyclustering.samples.definitions import SIMPLE_SAMPLES;
163			from pyclustering.container.kdtree import kdtree;
164			from pyclustering.utils import read_sample;
165
166			# Read data from text file
167			sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3);
168
169			# Create instance of KD-tree and initialize (fill) it by read data.
170			tree_instance = kdtree(sample);
171
172			# Search for nearest point
173			search_distance = 0.3;
174			nearest_node = tree_instance.find_nearest_dist_node([1.12, 4.31], search_distance);
175
176			# Search for nearest point in radius 0.3
177			nearest_nodes = tree_instance.find_nearest_dist_nodes([1.12, 4.31], search_distance);
178			print("Nearest nodes:", nearest_nodes);
179			@endcode
180
181			"""
182
183			def __init__(self, data_list = None, payload_list = None):
184			"""!
185			@brief Create kd-tree from list of points and from according list of payloads.
186			@details If lists were not specified then empty kd-tree will be created.
187
188			@param[in] data_list (list): Insert points from the list to created KD tree.
189			@param[in] payload_list (list): Insert payload from the list to created KD tree, length should be equal to length of data_list if it is specified.
190
191			"""
192
193			self.__root = None;
194			self.__dimension = None;
195
196			if (data_list is None):
197			return; # Just return from here, tree can be filled by insert method later
198
199			if (payload_list is None):
200			# Case when payload is not specified.
201			for index in range(0, len(data_list)):
202			self.insert(data_list[index], None);
203			else:
204			# Case when payload is specified.
205			for index in range(0, len(data_list)):
206			self.insert(data_list[index], payload_list[index]);
207
208
209			def insert(self, point, payload):
210			"""!
211			@brief Insert new point with payload to kd-tree.
212
213			@param[in] point (list): Coordinates of the point of inserted node.
214			@param[in] payload (*): Payload of inserted node.
215
216			"""
217
218			if (self.__root is None):
219			self.__dimension = len(point);
220			self.__root = node(point, payload, None, None, 0);
221			return self.__root;
222
223			cur_node = self.__root;
224
225			while True:
226			if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
227			# If new node is greater or equal than current node then check right leaf
228			if (cur_node.right is None):
229			discriminator = cur_node.disc + 1;
230			if (discriminator >= self.__dimension):
231			discriminator = 0;
232
233			cur_node.right = node(point, payload, None, None, discriminator, cur_node);
234			return cur_node.right;
235			else:
236			cur_node = cur_node.right;
237
238			else:
239			# If new node is less than current then check left leaf
240			if (cur_node.left is None):
241			discriminator = cur_node.disc + 1;
242			if (discriminator >= self.__dimension):
243			discriminator = 0;
244
245			cur_node.left = node(point, payload, None, None, discriminator, cur_node);
246			return cur_node.left;
247			else:
248			cur_node = cur_node.left;
249
250
251			def remove(self, point):
252			"""!
253			@brief Remove specified point from kd-tree.
254
255			@param[in] point (list): Coordinates of the point of removed node.
256
257			@return (node) Root if node has been successfully removed, otherwise None.
258
259			"""
260
261			# Get required node
262			node_for_remove = self.find_node(point);
263			if (node_for_remove is None):
264			return None;
265
266			parent = node_for_remove.parent;
267			minimal_node = self.__recursive_remove(node_for_remove);
268			if (parent is None):
269			self.__root = minimal_node;
270
271			# If all k-d tree was destroyed
272			if (minimal_node is not None):
273			minimal_node.parent = None;
274			else:
275			if (parent.left is node_for_remove):
276			parent.left = minimal_node;
277			elif (parent.right is node_for_remove):
278			parent.right = minimal_node;
279
280			return self.__root;
281
282
283			def __recursive_remove(self, node_removed):
284			"""!
285			@brief Delete node and return root of subtree.
286
287			@param[in] node_removed (node): Node that should be removed.
288
289			@return (node) Minimal node in line with coordinate that is defined by descriminator.
290
291			"""
292
293			# Check if it is leaf
294			if ( (node_removed.right is None) and (node_removed.left is None) ):
295			return None;
296
297			discriminator = node_removed.disc;
298
299			# Check if only left branch exist
300			if (node_removed.right is None):
301			node_removed.right = node_removed.left;
302			node_removed.left = None;
303
304			# Find minimal node in line with coordinate that is defined by discriminator
305			minimal_node = self.find_minimal_node(node_removed.right, discriminator);
306			parent = minimal_node.parent;
307
308			if (parent.left is minimal_node):
309			parent.left = self.__recursive_remove(minimal_node);
310			elif (parent.right is minimal_node):
311			parent.right = self.__recursive_remove(minimal_node);
312
313			minimal_node.parent = node_removed.parent;
314			minimal_node.disc = node_removed.disc;
315			minimal_node.right = node_removed.right;
316			minimal_node.left = node_removed.left;
317
318			# Update parent for successors of previous parent.
319			if (minimal_node.right is not None):
320			minimal_node.right.parent = minimal_node;
321
322			if (minimal_node.left is not None):
323			minimal_node.left.parent = minimal_node;
324
325			return minimal_node;
326
327
328			def find_minimal_node(self, node_head, discriminator):
329			"""!
330			@brief Find minimal node in line with coordinate that is defined by discriminator.
331
332			@param[in] node_head (node): Node of KD tree from that search should be started.
333			@param[in] discriminator (uint): Coordinate number that is used for comparison.
334
335			@return (node) Minimal node in line with descriminator from the specified node.
336
337			"""
338
339			min_key = lambda cur_node: cur_node.data[discriminator];
340			stack = [];
341			candidates = [];
342			isFinished = False;
343			while isFinished is False:
344			if node_head is not None:
345			stack.append(node_head);
346			node_head = node_head.left;
347			else:
348			if len(stack) != 0:
349			node_head = stack.pop();
350			candidates.append(node_head);
351			node_head = node_head.right;
352			else:
353			isFinished = True;
354
355			return min(candidates, key = min_key);
356
357
358			def find_node(self, point, cur_node = None):
359			"""!
360			@brief Find node with coordinates that are defined by specified point.
361			@details If node does not exist then None will be returned. Otherwise required node will be returned.
362
363			@param[in] point (list): Coordinates of the point whose node should be found.
364			@param[in] cur_node (node): Node from which search should be started.
365
366			@return (node) Node in case of existance of node with specified coordinates, otherwise it return None.
367
368			"""
369
370			req_node = None;
371
372			if (cur_node is None):
373			cur_node = self.__root;
374
375			while True:
376			if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
377			# Check if it's required node
378			if (cur_node.data == point):
379			req_node = cur_node;
380			break;
381
382			if (cur_node.right is not None):
383			cur_node = cur_node.right;
384
385			else:
386			if (cur_node.left is not None):
387			cur_node = cur_node.left;
388
389			return req_node;
390
391
392
393			def find_nearest_dist_node(self, point, distance, retdistance = False):
394			"""!
395			@brief Find nearest neighbor in area with radius = distance.
396
397			@param[in] point (list): Maximum distance where neighbors are searched.
398			@param[in] distance (double): Maximum distance where neighbors are searched.
399			@param[in] retdistance (bool): If True - returns neighbors with distances to them, otherwise only neighbors is returned.
400
401			@return (node\|list) Nearest neighbor if 'retdistance' is False and list with two elements [node, distance] if 'retdistance' is True,
402			where the first element is pointer to node and the second element is distance to it.
403
404			"""
405
406			best_nodes = self.find_nearest_dist_nodes(point, distance);
407
408			if (best_nodes == []):
409			return None;
410
411			nearest = min(best_nodes, key = lambda item: item[0]);
412
413			if (retdistance == True):
414			return nearest;
415			else:
416			return nearest[1];
417
418
419			def find_nearest_dist_nodes(self, point, distance):
420			"""!
421			@brief Find neighbors that are located in area that is covered by specified distance.
422
423			@param[in] point (list): Coordinates that is considered as centroind for searching.
424			@param[in] distance (double): Distance from the center where seaching is performed.
425
426			@return (list) Neighbors in area that is specified by point (center) and distance (radius).
427
428			"""
429
430			best_nodes = [];
431			if (self.__root is not None):
432			self.__recursive_nearest_nodes(point, distance, distance ** 2, self.__root, best_nodes);
433
434			return best_nodes;
435
436
437			def __recursive_nearest_nodes(self, point, distance, sqrt_distance, node_head, best_nodes):
438			"""!
439			@brief Returns list of neighbors such as tuple (distance, node) that is located in area that is covered by distance.
440
441			@param[in] point (list): Coordinates that is considered as centroind for searching
442			@param[in] distance (double): Distance from the center where seaching is performed.
443			@param[in] sqrt_distance (double): Square distance from the center where searching is performed.
444			@param[in] node_head (node): Node from that searching is performed.
445			@param[in\|out] best_nodes (list): List of founded nodes.
446
447			"""
448
449			if (node_head.right is not None):
450			minimum = node_head.data[node_head.disc] - distance;
451			if (point[node_head.disc] >= minimum):
452			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.right, best_nodes);
453
454			if (node_head.left is not None):
455			maximum = node_head.data[node_head.disc] + distance;
456			if (point[node_head.disc] < maximum):
457			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.left, best_nodes);
458
459			candidate_distance = euclidean_distance_sqrt(point, node_head.data);
460			if (candidate_distance <= sqrt_distance):
461			best_nodes.append( (candidate_distance, node_head) );
462
463
464			def children(self, node_parent):
465			"""!
466			@brief Returns list of children of node.
467
468			@param[in] node_parent (node): Node whose children are required.
469
470			@return (list) Children of node. If node haven't got any child then None is returned.
471
472			"""
473
474			if (node_parent.left is not None):
475			yield node_parent.left;
476			if (node_parent.right is not None):
477			yield node_parent.right;
478
479
480			def traverse(self, start_node = None, level = None):
481			"""!
482			@brief Traverses all nodes of subtree that is defined by node specified in input parameter.
483
484			@param[in] start_node (node): Node from that travering of subtree is performed.
485			@param[in, out] level (uint): Should be ignored by application.
486
487			@return (list) All nodes of the subtree.
488
489			"""
490
491			if (start_node is None):
492			start_node = self.__root;
493			level = 0;
494
495			if (start_node is None):
496			return [];
497
498			items = [ (level, start_node) ];
499			for child in self.children(start_node):
500			if child is not None:
501			items += self.traverse(child, level + 1);
502
503			return items;
504

annoviko / pyclustering

Push — master ( 55f4eb...4814fa )

kdtree.show() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like