Changeset 27414 in project
 Timestamp:
 09/12/12 06:28:04 (8 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

wiki/eggref/4/kdtree
r27353 r27414 13 13 == Documentation 14 14 15 This library implements a KD tree, a data structure for organizing 16 and searching points in an ndimensional space. 17 [[http://en.wikipedia.org/wiki/Kd_tree]]. 15 This library implements a [[http://en.wikipedia.org/wiki/Kd_treekd 16 tree]], a data structure for organizing and searching points in 17 kdimensional space. 18 19 The kd tree is a binary search tree in which every branching node 20 contains a kdimensional point, and every leaf node contains a set of 21 points. Every branching node represents a splitting hyperplane that 22 divides the space into two parts, known as halfspaces. 23 24 Points to the left of the splitting hyperplane are contained in the 25 left subtree of the node and points right of the hyperplane are 26 contained in the right subtree. The splitting hyperplane is chosen so 27 as to be perpendicular to one of the axes in the kdimensional 28 space. The axis at each branching level is chosen in a roundrobin 29 fashion. For instance, in 3D space, at level 0, the chosen axis is X, 30 so points are divided according to their Xcoordinates; at level 1, 31 the chosen axis is Y, so the points are divided according to their 32 Ycoordinates; at the next branch level the chosen axis is Z, and so 33 on. 34 18 35 19 36 === Point
Note: See TracChangeset
for help on using the changeset viewer.