KdTree 1.0.0 for Maya (maya plugin)

Kd-tree is a well suited data structure for nearest neighbour search (NNS) in n-dimensional space. The Visual studio project provided contains a very simple clear and self explanatory code for a 2D kd-tree construction and search algorithm. The extension to n-dimensions is straightforward following this paper .

Installation:
Download the archive Sources + Maya 8.5 , and just add a module file so that maya can locate the plugin (See the installation of the Delaunay Triangulator for Maya if you are not familiar with modules files)

Test the kdTree node :
Just open the scene %UNRAR_FOLDER%KdTreetestScenekd.mb
You should get the following result:

Notes :
The kdTree is a dependency node with the following attributes :

Inputs :

• inCurves (nurbsCurve array) : Array of input points ( In the (XZ) plane )  : the point cloud;
• inPoint (Matrix) : Transform of a locator ( In the (XZ) plane ) : the target point;
• neighbourhoodRadius (float) : The search radius around the target point;
• displayKdTree (bool) : Toggle the update of the geometry of the kd-tree;
• displayVisitedNode (bool) : Toggle the update of the nodes visited during the search.

Outputs

• outKdTreeCurves (nurbsCurve array) : the geometry of the kd tree
• outVisitedNodes (nurbsCurve array) : the geometry of the nodes visited during the search
• nearPoint (Compound) : the position of the nearest neighbour.

Maybe you have noticed In the outliner, the transforms with red icons. They are curveVarGroups. Curve var group are very useful when dealing with array of curve without knowing the size of the array. This node will automatically create the transform/nurbsCurve pairs below it depending on the number of curves it can evaluate at its input.