KDTree Utilities (mathutils.kdtree)

Generic 3-dimentional kd-tree to perform spatial searches.

import mathutils

# create a kd-tree from a mesh
from bpy import context
obj = context.object

# 3d cursor relative to the object data
co_find = context.scene.cursor_location * obj.matrix_world.inverted()

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)


# 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")
co_find = context.scene.cursor_location
for (co, index, dist) in kd.find_range(co_find, 0.5):
    print("    ", co, index, dist)
class mathutils.kdtree.KDTree

KdTree(size) -> new kd-tree initialized to hold size items.

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 (float triplet) – 3d coordinates.

  • filter (callable) – function which takes an index and returns True for indices to include in the search.

Returns

Returns (Vector, index, distance).

Return type

tuple

find_n(co, n)

Find nearest n points to co.

Parameters

  • co (float triplet) – 3d coordinates.

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

Returns

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

Return type

list

find_range(co, radius)

Find all points within radius of co.

Parameters

  • co (float triplet) – 3d coordinates.

  • radius (float) – Distance to search for points.

Returns

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

Return type

list

insert(co, index)

Insert a point into the KDTree.

Parameters

  • co (float triplet) – Point 3d position.

  • index (int) – The index of the point.