KDTree Utilities (mathutils.kdtree)

Generic 2D/3D KD-tree to perform spatial searches.

import mathutils

# Create a KD-tree from a mesh.
from bpy import context
obj = context.object

mesh = obj.data
size = len(mesh.vertices)
kd = mathutils.kdtree.KDTree(size)

for i, v in enumerate(mesh.vertices):
    kd.insert(v.co, i)

kd.balance()


# Find the closest point to the center.
co_find = (0.0, 0.0, 0.0)
co, index, dist = kd.find(co_find)
print("Close to center:", co, index, dist)

# 3D cursor relative to the object data.
co_find = obj.matrix_world.inverted() @ context.scene.cursor.location

# Find the closest 10 points to the 3D cursor.
print("Close 10 points")
for (co, index, dist) in kd.find_n(co_find, 10):
    print("    ", co, index, dist)


# Find points within a radius of the 3D cursor.
print("Close points within 0.5 distance")
for (co, index, dist) in kd.find_range(co_find, 0.5):
    print("    ", co, index, dist)
class mathutils.kdtree.KDTree(size, *, dimensions=3)

A KD-tree initialized to hold up to size items.

Parameters:

  • size (int) – Maximum number of items.

  • dimensions (int) – The dimensions of the tree (2 or 3).

Note

KDTree.balance() must have been called before using any of the find methods.

balance()

Balance the tree.

Note

This builds the entire tree, avoid calling after each insertion.

find(co, *, filter=None)

Find nearest point to co.

Parameters:

  • co (Sequence[float]) – Point position. Can be 2D or 3D, based on the KDTree dimensions.

  • filter (Callable[[int], bool] | None) – function which takes an index and returns True for indices to include in the search.

Returns:

Returns (position, index, distance), or (None, None, None) when no match is found.

Return type:

tuple[Vector, int, float] | tuple[None, None, None]

find_n(co, n)

Find nearest n points to co.

Parameters:

  • co (Sequence[float]) – Point position. Can be 2D or 3D, based on the KDTree dimensions.

  • n (int) – Number of points to find.

Returns:

Returns a list of tuples (position, index, distance).

Return type:

list[tuple[Vector, int, float]]

find_range(co, radius)

Find all points within radius of co.

Parameters:

  • co (Sequence[float]) – Point position. Can be 2D or 3D, based on the KDTree dimensions.

  • radius (float) – Maximum distance to search for points.

Returns:

Returns a list of tuples (position, index, distance).

Return type:

list[tuple[Vector, int, float]]

insert(co, index)

Insert a point into the KDTree.

Parameters:

  • co (Sequence[float]) – Point position. Can be 2D or 3D, based on the KDTree dimensions.

  • index (int) – The index of the point (must be non-negative).

dimensions

KDTree dimensions.

Type:

int