# 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.

find(co)

Find nearest point to co.

Parameters: co (float triplet) – 3d coordinates. Returns (Vector, index, distance). 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 a list of tuples (Vector, index, distance). 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 a list of tuples (Vector, index, distance). list
insert(index, co)

Insert a point into the KDTree.

Parameters: co (float triplet) – Point 3d position. index (int) – The index of the point.

#### Previous topic

Geometry Utilities (mathutils.geometry)

#### Next topic

Noise Utilities (mathutils.noise)