Represents KD Tree that is a space-partitioning data structure for organizing points in a k-dimensional space. More...
Public Member Functions | |
def | __init__ (self, data_list=None, payload_list=None) |
Create kd-tree from list of points and from according list of payloads. More... | |
def | insert (self, point, payload) |
Insert new point with payload to kd-tree. More... | |
def | remove (self, point, kwargs) |
Remove specified point from kd-tree. More... | |
def | find_minimal_node (self, node_head, discriminator) |
Find minimal node in line with coordinate that is defined by discriminator. More... | |
def | find_node_with_payload (self, point, point_payload, cur_node=None) |
Find node with specified coordinates and payload. More... | |
def | find_node (self, point, cur_node=None) |
Find node with coordinates that are defined by specified point. More... | |
def | find_nearest_dist_node (self, point, distance, retdistance=False) |
Find nearest neighbor in area with radius = distance. More... | |
def | find_nearest_dist_nodes (self, point, distance) |
Find neighbors that are located in area that is covered by specified distance. More... | |
def | children (self, node_parent) |
Returns list of children of node. More... | |
def | traverse (self, start_node=None, level=None) |
Traverses all nodes of subtree that is defined by node specified in input parameter. More... | |
Represents KD Tree that is a space-partitioning data structure for organizing points in a k-dimensional space.
In the term k-d tree, k denotes the dimensionality of the space being represented. Each data point is represented as a node in the k-d tree in the form of a record of type node.
Examples:
def pyclustering.container.kdtree.kdtree.__init__ | ( | self, | |
data_list = None , |
|||
payload_list = None |
|||
) |
Create kd-tree from list of points and from according list of payloads.
If lists were not specified then empty kd-tree will be created.
[in] | data_list | (list): Insert points from the list to created KD tree. |
[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. |
def pyclustering.container.kdtree.kdtree.children | ( | self, | |
node_parent | |||
) |
Returns list of children of node.
[in] | node_parent | (node): Node whose children are required. |
Definition at line 547 of file kdtree.py.
Referenced by pyclustering.container.kdtree.kdtree.traverse().
def pyclustering.container.kdtree.kdtree.find_minimal_node | ( | self, | |
node_head, | |||
discriminator | |||
) |
Find minimal node in line with coordinate that is defined by discriminator.
[in] | node_head | (node): Node of KD tree from that search should be started. |
[in] | discriminator | (uint): Coordinate number that is used for comparison. |
Definition at line 338 of file kdtree.py.
Referenced by pyclustering.container.kdtree.kdtree.remove().
def pyclustering.container.kdtree.kdtree.find_nearest_dist_node | ( | self, | |
point, | |||
distance, | |||
retdistance = False |
|||
) |
Find nearest neighbor in area with radius = distance.
[in] | point | (list): Maximum distance where neighbors are searched. |
[in] | distance | (double): Maximum distance where neighbors are searched. |
[in] | retdistance | (bool): If True - returns neighbors with distances to them, otherwise only neighbors is returned. |
def pyclustering.container.kdtree.kdtree.find_nearest_dist_nodes | ( | self, | |
point, | |||
distance | |||
) |
Find neighbors that are located in area that is covered by specified distance.
[in] | point | (list): Coordinates that is considered as centroind for searching. |
[in] | distance | (double): Distance from the center where seaching is performed. |
Definition at line 502 of file kdtree.py.
Referenced by pyclustering.container.kdtree.kdtree.find_nearest_dist_node().
def pyclustering.container.kdtree.kdtree.find_node | ( | self, | |
point, | |||
cur_node = None |
|||
) |
Find node with coordinates that are defined by specified point.
If node with specified parameters does not exist then None will be returned, otherwise required node will be returned.
[in] | point | (list): Coordinates of the point whose node should be found. |
[in] | cur_node | (node): Node from which search should be started. |
Definition at line 459 of file kdtree.py.
Referenced by pyclustering.container.kdtree.kdtree.remove().
def pyclustering.container.kdtree.kdtree.find_node_with_payload | ( | self, | |
point, | |||
point_payload, | |||
cur_node = None |
|||
) |
Find node with specified coordinates and payload.
If node with specified parameters does not exist then None will be returned, otherwise required node will be returned.
[in] | point | (list): Coordinates of the point whose node should be found. |
[in] | point_payload | (any): Payload of the node that is searched in the tree. |
[in] | cur_node | (node): Node from which search should be started. |
Definition at line 441 of file kdtree.py.
Referenced by pyclustering.container.kdtree.kdtree.remove().
def pyclustering.container.kdtree.kdtree.insert | ( | self, | |
point, | |||
payload | |||
) |
Insert new point with payload to kd-tree.
[in] | point | (list): Coordinates of the point of inserted node. |
[in] | payload | (any-type): Payload of inserted node. It can be identificator of the node or some useful payload that belongs to the point. |
Definition at line 204 of file kdtree.py.
Referenced by pyclustering.container.kdtree.kdtree.find_minimal_node().
def pyclustering.container.kdtree.kdtree.remove | ( | self, | |
point, | |||
kwargs | |||
) |
Remove specified point from kd-tree.
It removes the first found node that satisfy to the input parameters. Make sure that pair (point, payload) is unique for each node, othewise the first found is removed.
[in] | point | (list): Coordinates of the point of removed node. |
[in] | **kwargs | Arbitrary keyword arguments (available arguments: 'payload'). |
Keyword Args:
def pyclustering.container.kdtree.kdtree.traverse | ( | self, | |
start_node = None , |
|||
level = None |
|||
) |
Traverses all nodes of subtree that is defined by node specified in input parameter.
[in] | start_node | (node): Node from that travering of subtree is performed. |
[in,out] | level | (uint): Should be ignored by application. |
Definition at line 563 of file kdtree.py.
Referenced by pyclustering.container.kdtree.kdtree.traverse().