Python Documentation

Python bindings for the KDTree C++ library, generated via nanobind. The module is also available at the package level via KDTree_Python.

from scikdtree import KDTree, PlaneSelectionAlgorithm

PlaneSelectionAlgorithm

class scikdtree.PlaneSelectionAlgorithm

Enum controlling which split-plane algorithm the KDTree uses during construction.

LOG: PlaneSelectionAlgorithm: O(n log n) — default, recommended for most use cases.

LOGSQUARED: PlaneSelectionAlgorithm: O(n log² n) — unoptimised LOG variant, useful for validation and comparison.

QUADRATIC: PlaneSelectionAlgorithm: O(n²) — suitable only for very small datasets.

NOTREE: PlaneSelectionAlgorithm: No tree structure is built; falls back to brute-force traversal. Useful as a performance baseline.

KDTree

class scikdtree.KDTree(vertices, faces, algorithm=PlaneSelectionAlgorithm.LOG)

class scikdtree.KDTree(polySource, algorithm=PlaneSelectionAlgorithm.LOG)

class scikdtree.KDTree(nodeFilePath, faceFilePath, algorithm=PlaneSelectionAlgorithm.LOG)

A lazily-built KD-Tree for spatial partitioning of triangle meshes or particle clouds in three-dimensional space. Thread-safe for concurrent intersection queries.

The tree is built on demand: the root node is only constructed when the first query is made, or explicitly via prebuildTree().

Parameters:

vertices (list[list[float]]) – Vertex coordinates of the polyhedron. Each vertex is a list of three floats [x, y, z].
faces (list[list[int]]) – Triangle faces of the polyhedron. Each face is a list of three vertex indices [i, j, k].
polySource (tuple[list[list[float]], list[list[int]]]) – A tuple (vertices, faces) combining both inputs above.
nodeFilePath (str) – Path to a Tetgen .node file containing vertex coordinates.
faceFilePath (str) – Path to a Tetgen .face file containing triangle indices.
algorithm (PlaneSelectionAlgorithm) – Split-plane selection algorithm. Defaults to PlaneSelectionAlgorithm.LOG.

prebuildTree() → KDTree

Eagerly constructs the entire KD-Tree instead of building it lazily on the first query. Useful when consistent query latency is required or when the same tree is queried many times.

Returns:: The same KDTree instance (allows method chaining).
Return type:: KDTree

countIntersections(origin, ray) → int

Counts how many triangles the given ray intersects.

Parameters:

origin (list[float]) – Ray origin as [x, y, z].
ray (list[float]) – Ray direction as [x, y, z].

Returns:

Number of intersected triangles.

Return type:

int

getIntersections(origin, ray) → list[list[float]]

Returns the exact intersection points of the given ray with the mesh triangles.

Parameters:

origin (list[float]) – Ray origin as [x, y, z].
ray (list[float]) – Ray direction as [x, y, z].

Returns:

List of intersection points, each as [x, y, z].

Return type:

list[list[float]]

printTree() → None: Prints the KD-Tree structure to the Python console.

__str__() → str

Returns a string representation of the KD-Tree structure.

Return type:: str