kdtree.find_nearest_dist_nodes() - Code Metrics - Inspection of "[ccore.container.kdtree] Correction for method 'kd..." - annoviko/pyclustering - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — 0.7.dev ( 8f9721...44cbb1 )

by Andrei

created 2017-10-23 12:22 UTC

kdtree.find_nearest_dist_nodes() A

↳ Parent: kdtree

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	1
dl	0
loc	15
rs	9.4285
c	1
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.
    
    """
    
    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 (list) Neighbors, if redistance is True then neighbors with distances to them will be returned.
        
        """
        
        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 = [];
        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.
        
        """
        
        minimum = node_head.data[node_head.disc] - distance;
        maximum = node_head.data[node_head.disc] + distance;
        
        if (node_head.right is not None):
            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):
            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			def __repr__(self):
131			"""!
132			@return (string) Default representation of the node.
133
134			"""
135			left = None;
136			right = None;
137
138			if (self.left is not None):
139			left = self.left.data;
140
141			if (self.right is not None):
142			right = self.right.data;
143
144			return "(%s: [L:'%s', R:'%s'])" % (self.data, left, right);
145
146			def __str__(self):
147			"""!
148			@return (string) String representation of the node.
149
150			"""
151			return self.__repr__();
152
153
154			class kdtree:
155			"""!
156			@brief Represents KD Tree.
157
158			"""
159
160			def __init__(self, data_list = None, payload_list = None):
161			"""!
162			@brief Create kd-tree from list of points and from according list of payloads.
163			@details If lists were not specified then empty kd-tree will be created.
164
165			@param[in] data_list (list): Insert points from the list to created KD tree.
166			@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.
167
168			"""
169
170			self.__root = None;
171			self.__dimension = None;
172
173			if (data_list is None):
174			return; # Just return from here, tree can be filled by insert method later
175
176			if (payload_list is None):
177			# Case when payload is not specified.
178			for index in range(0, len(data_list)):
179			self.insert(data_list[index], None);
180			else:
181			# Case when payload is specified.
182			for index in range(0, len(data_list)):
183			self.insert(data_list[index], payload_list[index]);
184
185
186			def insert(self, point, payload):
187			"""!
188			@brief Insert new point with payload to kd-tree.
189
190			@param[in] point (list): Coordinates of the point of inserted node.
191			@param[in] payload (*): Payload of inserted node.
192
193			"""
194
195			if (self.__root is None):
196			self.__dimension = len(point);
197			self.__root = node(point, payload, None, None, 0);
198			return self.__root;
199
200			cur_node = self.__root;
201
202			while True:
203			if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
204			# If new node is greater or equal than current node then check right leaf
205			if (cur_node.right is None):
206			discriminator = cur_node.disc + 1;
207			if (discriminator >= self.__dimension):
208			discriminator = 0;
209
210			cur_node.right = node(point, payload, None, None, discriminator, cur_node);
211			return cur_node.right;
212			else:
213			cur_node = cur_node.right;
214
215			else:
216			# If new node is less than current then check left leaf
217			if (cur_node.left is None):
218			discriminator = cur_node.disc + 1;
219			if (discriminator >= self.__dimension):
220			discriminator = 0;
221
222			cur_node.left = node(point, payload, None, None, discriminator, cur_node);
223			return cur_node.left;
224			else:
225			cur_node = cur_node.left;
226
227
228			def remove(self, point):
229			"""!
230			@brief Remove specified point from kd-tree.
231
232			@param[in] point (list): Coordinates of the point of removed node.
233
234			@return (node) Root if node has been successfully removed, otherwise None.
235
236			"""
237
238			# Get required node
239			node_for_remove = self.find_node(point);
240			if (node_for_remove is None):
241			return None;
242
243			parent = node_for_remove.parent;
244			minimal_node = self.__recursive_remove(node_for_remove);
245			if (parent is None):
246			self.__root = minimal_node;
247
248			# If all k-d tree was destroyed
249			if (minimal_node is not None):
250			minimal_node.parent = None;
251			else:
252			if (parent.left is node_for_remove):
253			parent.left = minimal_node;
254			elif (parent.right is node_for_remove):
255			parent.right = minimal_node;
256
257			return self.__root;
258
259
260			def __recursive_remove(self, node_removed):
261			"""!
262			@brief Delete node and return root of subtree.
263
264			@param[in] node_removed (node): Node that should be removed.
265
266			@return (node) Minimal node in line with coordinate that is defined by descriminator.
267
268			"""
269
270			# Check if it is leaf
271			if ( (node_removed.right is None) and (node_removed.left is None) ):
272			return None;
273
274			discriminator = node_removed.disc;
275
276			# Check if only left branch exist
277			if (node_removed.right is None):
278			node_removed.right = node_removed.left;
279			node_removed.left = None;
280
281			# Find minimal node in line with coordinate that is defined by discriminator
282			minimal_node = self.find_minimal_node(node_removed.right, discriminator);
283			parent = minimal_node.parent;
284
285			if (parent.left is minimal_node):
286			parent.left = self.__recursive_remove(minimal_node);
287			elif (parent.right is minimal_node):
288			parent.right = self.__recursive_remove(minimal_node);
289
290			minimal_node.parent = node_removed.parent;
291			minimal_node.disc = node_removed.disc;
292			minimal_node.right = node_removed.right;
293			minimal_node.left = node_removed.left;
294
295			# Update parent for successors of previous parent.
296			if (minimal_node.right is not None):
297			minimal_node.right.parent = minimal_node;
298
299			if (minimal_node.left is not None):
300			minimal_node.left.parent = minimal_node;
301
302			return minimal_node;
303
304
305			def find_minimal_node(self, node_head, discriminator):
306			"""!
307			@brief Find minimal node in line with coordinate that is defined by discriminator.
308
309			@param[in] node_head (node): Node of KD tree from that search should be started.
310			@param[in] discriminator (uint): Coordinate number that is used for comparison.
311
312			@return (node) Minimal node in line with descriminator from the specified node.
313
314			"""
315
316			min_key = lambda cur_node: cur_node.data[discriminator];
317			stack = [];
318			candidates = [];
319			isFinished = False;
320			while isFinished is False:
321			if node_head is not None:
322			stack.append(node_head);
323			node_head = node_head.left;
324			else:
325			if len(stack) != 0:
326			node_head = stack.pop();
327			candidates.append(node_head);
328			node_head = node_head.right;
329			else:
330			isFinished = True;
331
332			return min(candidates, key = min_key);
333
334
335			def find_node(self, point, cur_node = None):
336			"""!
337			@brief Find node with coordinates that are defined by specified point.
338			@details If node does not exist then None will be returned. Otherwise required node will be returned.
339
340			@param[in] point (list): Coordinates of the point whose node should be found.
341			@param[in] cur_node (node): Node from which search should be started.
342
343			@return (node) Node in case of existance of node with specified coordinates, otherwise it return None.
344
345			"""
346
347			req_node = None;
348
349			if (cur_node is None):
350			cur_node = self.__root;
351
352			while True:
353			if (cur_node.data[cur_node.disc] <= point[cur_node.disc]):
354			# Check if it's required node
355			if (cur_node.data == point):
356			req_node = cur_node;
357			break;
358
359			if (cur_node.right is not None):
360			cur_node = cur_node.right;
361
362			else:
363			if (cur_node.left is not None):
364			cur_node = cur_node.left;
365
366			return req_node;
367
368
369
370			def find_nearest_dist_node(self, point, distance, retdistance = False):
371			"""!
372			@brief Find nearest neighbor in area with radius = distance.
373
374			@param[in] point (list): Maximum distance where neighbors are searched.
375			@param[in] distance (double): Maximum distance where neighbors are searched.
376			@param[in] retdistance (bool): If True - returns neighbors with distances to them, otherwise only neighbors is returned.
377
378			@return (list) Neighbors, if redistance is True then neighbors with distances to them will be returned.
379
380			"""
381
382			best_nodes = self.find_nearest_dist_nodes(point, distance);
383
384			if (best_nodes == []):
385			return None;
386
387			nearest = min(best_nodes, key = lambda item: item[0]);
388
389			if (retdistance == True):
390			return nearest;
391			else:
392			return nearest[1];
393
394
395			def find_nearest_dist_nodes(self, point, distance):
396			"""!
397			@brief Find neighbors that are located in area that is covered by specified distance.
398
399			@param[in] point (list): Coordinates that is considered as centroind for searching.
400			@param[in] distance (double): Distance from the center where seaching is performed.
401
402			@return (list) Neighbors in area that is specified by point (center) and distance (radius).
403
404			"""
405
406			best_nodes = [];
407			self.__recursive_nearest_nodes(point, distance, distance ** 2, self.__root, best_nodes);
408
409			return best_nodes;
410
411
412			def __recursive_nearest_nodes(self, point, distance, sqrt_distance, node_head, best_nodes):
413			"""!
414			@brief Returns list of neighbors such as tuple (distance, node) that is located in area that is covered by distance.
415
416			@param[in] point (list): Coordinates that is considered as centroind for searching
417			@param[in] distance (double): Distance from the center where seaching is performed.
418			@param[in] sqrt_distance (double): Square distance from the center where searching is performed.
419			@param[in] node_head (node): Node from that searching is performed.
420			@param[in\|out] best_nodes (list): List of founded nodes.
421
422			"""
423
424			minimum = node_head.data[node_head.disc] - distance;
425			maximum = node_head.data[node_head.disc] + distance;
426
427			if (node_head.right is not None):
428			if (point[node_head.disc] >= minimum):
429			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.right, best_nodes);
430
431			if (node_head.left is not None):
432			if (point[node_head.disc] < maximum):
433			self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.left, best_nodes);
434
435			candidate_distance = euclidean_distance_sqrt(point, node_head.data);
436			if (candidate_distance <= sqrt_distance):
437			best_nodes.append( (candidate_distance, node_head) );
438
439
440			def children(self, node_parent):
441			"""!
442			@brief Returns list of children of node.
443
444			@param[in] node_parent (node): Node whose children are required.
445
446			@return (list) Children of node. If node haven't got any child then None is returned.
447
448			"""
449
450			if (node_parent.left is not None):
451			yield node_parent.left;
452			if (node_parent.right is not None):
453			yield node_parent.right;
454
455
456			def traverse(self, start_node = None, level = None):
457			"""!
458			@brief Traverses all nodes of subtree that is defined by node specified in input parameter.
459
460			@param[in] start_node (node): Node from that travering of subtree is performed.
461			@param[in, out] level (uint): Should be ignored by application.
462
463			@return (list) All nodes of the subtree.
464
465			"""
466
467			if (start_node is None):
468			start_node = self.__root;
469			level = 0;
470
471			if (start_node is None):
472			return [];
473
474			items = [ (level, start_node) ];
475			for child in self.children(start_node):
476			if child is not None:
477			items += self.traverse(child, level + 1);
478
479			return items;
480

annoviko / pyclustering

Push — 0.7.dev ( 8f9721...44cbb1 )

kdtree.find_nearest_dist_nodes() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like