polynomials_on_simplices.geometry.space_partitioning.kd_tree module¶

A K-d tree is a special case of a binary space partitioning tree, where each space partitioning (hyper-)plane is aligned with the coordinate axes (plane normal is some coordinate axis).

class KdTreeNode(parent, k=3, side=0)[source]¶

Bases: object

A node in a K-d tree.

The node is either a leaf node, or it contains a hyperplane that splits space into two parts, each part being associated with one of its two child nodes. Hence a node in a K-d tree has a subspace of \(\mathbb{R}^k\) associated with it. In a k-d tree the space partitioning hyperplane is always aligned with the coordinate axes. This means that the space associated with a node is an axis aligned box (potentially stretching to infinity), see in_node_space() and node_aabb().

Parameters:	parent (Optional[KdTreeNode]) – Parent node. None for the root node. k (int) – Dimension of the space the k-d tree exists in. side (int) – Indicate if this node is associated with the negative or positive side of the parent node hyperplane, indicated by a 0 or 1.

address()[source]¶

Address of node in the tree.

An address in the tree is a list of sibling indices. For example:

[0] gives the root node. [0, 1] gives the second (zero-based indexing) child node of the root node. [0, 1, 0] gives the first child node of the second child node of the root node.

Returns:	List of nodes to follow to reach to this node.
Return type:	List[{0, 1}]

cut_subtree()[source]¶: Remove the subtree beneath this node (remove child nodes and plane splitting this node).

depth()[source]¶

Get depth of node in the tree (number of parents to traverse to reach the root node).

Returns:	Depth of the node in the tree.
Return type:	int

is_leaf()[source]¶

Returns:	Whether or not this node is a leaf node in the tree.
Return type:	bool

is_root()[source]¶

Returns:	Whether or not this node is the root node of the tree.
Return type:	bool

recurse(fn)[source]¶

Recursively call a function on this node and all child nodes.

Parameters:	fn (Callable f(node)) – Function to call.

sibling()[source]¶

Get the sibling node for this node.

Returns:	Sibling node.
Return type:	KdTreeNode

sibling_index()[source]¶

Get index of node in the pair of siblings.

Returns:	0 or 1 depending on whether this is the first or second child node of the parent.

subdivide(plane_point, plane_normal_idx=0)[source]¶

Subdivide this node into 2 child nodes by splitting this node into two halves using the given (hyper-)plane.

Parameters:	plane_point – A point in the (hyper-)plane used to split this node. plane_normal_idx (int) – Index of the coordinate axis that should be the normal of the hyperplane that splits this node (in [0, 1, …, k - 1]).

create_kd_tree(k)[source]¶

Create a k-d tree containing a single root node.

Parameters:	k (int) – Dimension of the space the k-d tree exists in.
Returns:	KdTreeNode tree containing a single root node.
Return type:	KdTreeNode

find_leaf_containing_point(tree_root, point)[source]¶

Find a leaf node in a k-d tree which contains the given point.

Parameters:	tree_root (KdTreeNode) – Root node in the k-d tree. point (n-dimensional vector) – Point in \(\mathbb{R}^k\).
Returns:	Leaf node containing the point.
Return type:	KdTreeNode

in_node_space(tree_node, point)[source]¶

Check if the given point lies in the part of space associated with the given node in a k-d tree.

The root node in a k-d tree is associated with all of space. For a non root node the node is associated with the part of the parent node space lying on either the negative or positive side of the parent node splitting plane (depending on whether the node is the first or second child node of the parent).

Parameters:	tree_node (KdTreeNode) – Tree node in whose space we want to check if the point lies. point (n-dimensional vector) – Point in \(\mathbb{R}^k\).
Returns:	Whether or not the point lies in the part of space associated with the given node.
Return type:	bool

node_aabb(tree_node)[source]¶

Get the space associated with a node in a k-d tree. Since the space partitioning hyperplanes in a k-d tree is aligned with the coordinate axis, this space is an axis aligned box.

Parameters:	tree_node (KdTreeNode) – Tree node whose associated space (axis aligned bounding box) we want to get.
Returns:	Axis aligned box for the given tree node, represented with two n:d vectors giving the min and max point of the AABB.
Return type:	Pair of n-dimensional vectors