Patch D133: Python wrapper for BLI_kdtree (adds mathutils.kdtree)

Originally by Dan Eicher, with my own fixes and adjustments (see patch page for details).

For details there are unit tests and api example usage.

	doc/python_api/sphinx-in-tmp/menu_id.png

2 files changed, 40 insertions, 1 deletions

diff --git a/doc/python_api/examples/mathutils.kdtree.py b/doc/python_api/examples/mathutils.kdtree.py
new file mode 100644
index 00000000000..d367582e5be
--- /dev/null
+++ b/doc/python_api/examples/mathutils.kdtree.py
@@ -0,0 +1,37 @@
+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)
+
diff --git a/doc/python_api/sphinx_doc_gen.py b/doc/python_api/sphinx_doc_gen.py
index a8128633569..4cea81d5cf0 100644
--- a/doc/python_api/sphinx_doc_gen.py
+++ b/doc/python_api/sphinx_doc_gen.py
@@ -271,6 +271,7 @@ else:
         "gpu",
         "mathutils",
         "mathutils.geometry",
+        "mathutils.kdtree",
         "mathutils.noise",
         "freestyle",
         ]
@@ -1625,7 +1626,7 @@ def write_rst_contents(basepath):
 
     standalone_modules = (
         # mathutils
-        "mathutils", "mathutils.geometry", "mathutils.noise",
+        "mathutils", "mathutils.geometry", "mathutils.kdtree", "mathutils.noise",
         # misc
         "freestyle", "bgl", "blf", "gpu", "aud", "bpy_extras",
         # bmesh, submodules are in own page
@@ -1776,6 +1777,7 @@ def write_rst_importable_modules(basepath):
         "bpy.props"            : "Property Definitions",
         "mathutils"            : "Math Types & Utilities",
         "mathutils.geometry"   : "Geometry Utilities",
+        "mathutils.kdtree"     : "KDTree Utilities",
         "mathutils.noise"      : "Noise Utilities",
         "freestyle"            : "Freestyle Data Types & Operators",
     }