pyclustering
0.10.1
pyclustring is a Python, C++ data mining library.

Represents KD Tree that is a spacepartitioning data structure for organizing points in a kdimensional space. More...
Public Member Functions  
def  __init__ (self, data_list=None, payload_list=None) 
Create kdtree from list of points and from according list of payloads. More...  
def  insert (self, point, payload=None) 
Insert new point with payload to kdtree. More...  
def  remove (self, point, **kwargs) 
Remove specified point from kdtree. More...  
Public Member Functions inherited from pyclustering.container.kdtree.kdtree_balanced  
def  __len__ (self) 
Returns amount of nodes in the KDtree. More...  
def  get_root (self) 
Returns root of the tree. 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...  
Represents KD Tree that is a spacepartitioning data structure for organizing points in a kdimensional space.
In the term kd tree, k denotes the dimensionality of the space being represented. Each data point is represented as a node in the kd tree in the form of a record of type node. The tree supports dynamic construction when nodes can be dynamically added and removed. As a result KDtree might not be balanced if methods insert
and remove
are used to built the tree. If the tree is built using constructor where all points are passed to the tree then balanced tree is built. Single point search and rangesearch procedures have complexity is O(n)
in worse case in case of unbalanced tree. If there is no need to build dynamic KDtree, then it is much better to use static KDtree kdtree_balanced
.
There is an example how to use KDtree to search nodes (points from input data) that are nearest to some point:
In case of building KDtree using insert
and remove
method, the output KDtree might be unbalanced  here is an example that demonstrates this:
There are two figures where difference between balanced and unbalanced KDtrees is demonstrated.
def pyclustering.container.kdtree.kdtree.__init__  (  self,  
data_list = None , 

payload_list = None 

) 
Create kdtree from list of points and from according list of payloads.
If lists were not specified then empty kdtree 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. 
Reimplemented from pyclustering.container.kdtree.kdtree_balanced.
def pyclustering.container.kdtree.kdtree.insert  (  self,  
point,  
payload = None 

) 
Insert new point with payload to kdtree.
[in]  point  (list): Coordinates of the point of inserted node. 
[in]  payload  (anytype): Payload of inserted node. It can be ID of the node or some useful payload that belongs to the point. 
def pyclustering.container.kdtree.kdtree.remove  (  self,  
point,  
**  kwargs  
) 
Remove specified point from kdtree.
It removes the first found node that satisfy to the input parameters. Make sure that pair (point, payload) is unique for each node, otherwise 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: