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

    Find nearest point to `co`.

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