KDTree Utilities (mathutils.kdtree)¶
Generic 3dimentional kdtree to perform spatial searches.
import mathutils
# create a kdtree 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 kdtree initialized to hold
size
items.Note
KDTree.balance
must have been called before using any of thefind
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 toco
.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
ofco
.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.
