polynomials_on_simplices.geometry.space_partitioning.kd_mesh_tree.simplicial_mesh_kd_tree module

Kd-tree built around a simplicial mesh (a mesh consisting of n-dimensional simplices, e.g. a triangle mesh or a tetrahedral mesh).

class KdTreeSMNode(parent, side, simplices, vertices, simplices_of_interest=None)[source]

Bases: polynomials_on_simplices.geometry.space_partitioning.kd_tree.KdTreeNode

A node in a k-d tree, which is augmented with information about the simplices in a simplicial mesh which potentially intersects with the space associated with the node.

The calculation of potentially intersecting simplices is conservative, in that the list of potentially intersecting simplices can contain simplices that doesn’t intersect with the node. However it will not miss any simplices, i.e. there are no simplices in the mesh that intersect a node which are not part of that nodes list of potentially intersecting simplices.

Parameters:
  • parent (Optional[KdTreeSMNode]) – Parent node. None for the root node.
  • 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.
  • simplices (num simplices by (n + 1) array of integers) – The simplices in the mesh the k-d tree is built around.
  • vertices (num vertices by n array of floats) – The vertices in the mesh the k-d tree is built around.
  • simplices_of_interest (Optional[List[None]]) – Optional subset of simplices in the mesh that we want to build the k-d tree around. If not specified all simplices will be used.
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(simplices, vertices, fixed_depth=False, max_depth=5, max_simplices_in_leaf=None, simplices_of_interest=None)[source]

Create a k-d tree which covers a simplicial mesh.

Parameters:
  • simplices (num simplices by (n + 1) array of integers) – The simplices in the mesh the k-d tree is built around.
  • vertices (num vertices by n array of floats) – The vertices in the mesh the k-d tree is built around.
  • fixed_depth (bool) – Specify how to subdivide the k-d tree when covering the simplicial mesh. If fixed depth is True, k-d tree nodes intersecting simplices will be subdivided to the max depth specified by the max_depth parameter. If fixed_depth is False, the tree will instead be adaptively subdivided until the max depth is reached or a leaf node doesn’t intersect with more than max_simplices_in_leaf simplices (if specified).
  • max_depth (int) – Maximum depth of the created k-d tree.
  • max_simplices_in_leaf (Optional[int]) – If fixed_depth is False, the tree will be subdivided until no leaf node intersects with more than this number of simplices, or the maximum depth is reached.
  • simplices_of_interest (Optional[List[int]]) – Optional subset of simplices in the mesh that we want to build the k-d tree around. If not specified all simplices will be used.
Returns:

K-d tree build around the line strip.
Return type:

KdTreeSMNode