MakeTree – this function creates the kd tree structure. It has two input arguments:
-m (model object)    =    model to create the tree for.
-f (flag)    =    to identify which nodes to build the tree with.

The function returns a tree structure object containing the flagged nodes of the given model.

CheckTree – this function traverses the tree and finds the node nearest a given point. It has two input arguements:
-tree    =    the tree object as returned by MakeTree.
-point    =    a node (or object with .x/.y/.z properties) for which we want to find the neighbour of.

CheckTree does not return a value, instead it adds two properties to the input point:
.neighbour    =    object of the nearest node in the tree to the point.
.dist    =    the distance between the point and its neighbour *squared*.

Additionally three search functions and a ‘distance between two nodes’ function is included (and referenced by the core functions).

KD trees are very efficient when the likely distance between point and neighbour is unknown (making  a BucketSearch more difficult). For large problems the time overhead is mostly in the MakeTree functions, checking the tree is typically very fast.

In this example, the user selects nodes on one part and the nearest node on the neighbouring part is then sketched. A timer is included for interest.