Changeset 27414 in project


Ignore:
Timestamp:
09/12/12 06:28:04 (8 years ago)
Author:
Ivan Raikov
Message:

kd-tree doc: expanded introduction somewhat

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/eggref/4/kd-tree

    r27353 r27414  
    1313== Documentation
    1414
    15 This library implements a K-D tree, a data structure for organizing
    16 and searching points in an n-dimensional space. 
    17 [[http://en.wikipedia.org/wiki/K-d_tree]].
     15This library implements a [[http://en.wikipedia.org/wiki/K-d_tree|k-d
     16tree]], a data structure for organizing and searching points in
     17k-dimensional space.
     18
     19The k-d tree is a binary search tree in which every branching node
     20contains a k-dimensional point, and every leaf node contains a set of
     21points. Every branching node represents a splitting hyperplane that
     22divides the space into two parts, known as half-spaces.
     23
     24Points to the left of the splitting hyperplane are contained in the
     25left subtree of the node and points right of the hyperplane are
     26contained in the right subtree. The splitting hyperplane is chosen so
     27as to be perpendicular to one of the axes in the k-dimensional
     28space. The axis at each branching level is chosen in a round-robin
     29fashion. For instance, in 3-D space, at level 0, the chosen axis is X,
     30so points are divided according to their X-coordinates; at level 1,
     31the chosen axis is Y, so the points are divided according to their
     32Y-coordinates; at the next branch level the chosen axis is Z, and so
     33on.
     34
    1835
    1936=== Point
Note: See TracChangeset for help on using the changeset viewer.