pyclustering.container.kdtree.kdtree Class Reference

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...

Detailed Description

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:

# 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);

Definition at line 157 of file kdtree.py.

Constructor & Destructor Documentation

__init__()

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.

Parameters

[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.

Definition at line 187 of file kdtree.py.

Member Function Documentation

children()

def pyclustering.container.kdtree.kdtree.children	(		self,
			node_parent
	)

Returns list of children of node.

Parameters

[in]

node_parent

(node): Node whose children are required.

Returns

(list) Children of node. If node haven't got any child then None is returned.

Definition at line 547 of file kdtree.py.

Referenced by pyclustering.container.kdtree.kdtree.traverse().

find_minimal_node()

def pyclustering.container.kdtree.kdtree.find_minimal_node	(		self,
			node_head,
			discriminator
	)

Find minimal node in line with coordinate that is defined by discriminator.

Parameters

[in]	node_head	(node): Node of KD tree from that search should be started.
[in]	discriminator	(uint): Coordinate number that is used for comparison.

Returns

(node) Minimal node in line with descriminator from the specified node.

Definition at line 338 of file kdtree.py.

Referenced by pyclustering.container.kdtree.kdtree.remove().

find_nearest_dist_node()

def pyclustering.container.kdtree.kdtree.find_nearest_dist_node	(		self,
			point,
			distance,
			retdistance = False
	)

Find nearest neighbor in area with radius = distance.

Parameters

[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.

Returns

(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.

Definition at line 476 of file kdtree.py.

find_nearest_dist_nodes()

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.

Parameters

[in]	point	(list): Coordinates that is considered as centroind for searching.
[in]	distance	(double): Distance from the center where seaching is performed.

Returns

(list) Neighbors in area that is specified by point (center) and distance (radius).

Definition at line 502 of file kdtree.py.

Referenced by pyclustering.container.kdtree.kdtree.find_nearest_dist_node().

find_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.

Parameters

[in]	point	(list): Coordinates of the point whose node should be found.
[in]	cur_node	(node): Node from which search should be started.

Returns

(node) Node if it satisfies to input parameters, otherwise it return None.

Definition at line 459 of file kdtree.py.

Referenced by pyclustering.container.kdtree.kdtree.remove().

find_node_with_payload()

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.

Parameters

[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.

Returns

(node) Node if it satisfies to input parameters, otherwise it return None.

Definition at line 441 of file kdtree.py.

Referenced by pyclustering.container.kdtree.kdtree.remove().

insert()

def pyclustering.container.kdtree.kdtree.insert	(		self,
			point,
			payload
	)

Insert new point with payload to kd-tree.

Parameters

[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.

Returns

(node) Inserted node to the kd-tree.

Definition at line 204 of file kdtree.py.

Referenced by pyclustering.container.kdtree.kdtree.find_minimal_node().

remove()

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.

Parameters

[in]	point	(list): Coordinates of the point of removed node.
[in]	**kwargs	Arbitrary keyword arguments (available arguments: 'payload').

Keyword Args:

• payload (any): Payload of the node that should be removed.

Returns

(node) Root if node has been successfully removed, otherwise None.

Definition at line 250 of file kdtree.py.

traverse()

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.

Parameters

[in]	start_node	(node): Node from that travering of subtree is performed.
[in,out]	level	(uint): Should be ignored by application.

Returns

(list) All nodes of the subtree.

Definition at line 563 of file kdtree.py.

Referenced by pyclustering.container.kdtree.kdtree.traverse().

---

The documentation for this class was generated from the following file:

• pyclustering/container/kdtree.py