Changeset 27415 in project

09/12/12 06:30:02 (8 years ago)
Ivan Raikov

kd-tree: added some introductory explanation to source file

1 edited


  • release/4/kd-tree/trunk/kd-tree.scm

    r27351 r27415  
    2 ;; An implementation of the K-D tree spatial indexing data structures.
    3 ;;
     2;; An implementation of the K-d tree spatial indexing data structure.
     6;; The k-d tree is a binary search tree in which every branching node
     7;; contains a k-dimensional point, and every leaf node contains a set
     8;; of points. Every branching node represents a splitting hyperplane
     9;; that divides the space into two parts, known as half-spaces.
     11;; Points to the left of the splitting hyperplane are contained in the
     12;; left subtree of the node and points right of the hyperplane are
     13;; contained in the right subtree. The splitting hyperplane is chosen
     14;; so as to be perpendicular to one of the axes in the k-dimensional
     15;; space. The axis at each branching level is chosen in a round-robin
     16;; fashion. For instance, in 3-D space, at level 0, the chosen axis is
     17;; X, so points are divided according to their X-coordinates; at level
     18;; 1, the chosen axis is Y, so the points are divided according to
     19;; their Y-coordinates; at the next branch level the chosen axis is Z,
     20;; and so on.
    523;; This code is based on the Haskell kd-tree library implementation of
Note: See TracChangeset for help on using the changeset viewer.