Changeset 27415 in project
 Timestamp:
 09/12/12 06:30:02 (8 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

release/4/kdtree/trunk/kdtree.scm
r27351 r27415 1 1 ;; 2 ;; An implementation of the KD tree spatial indexing data structures. 3 ;; http://en.wikipedia.org/wiki/Kd_tree 2 ;; An implementation of the Kd tree spatial indexing data structure. 3 ;; 4 ;; http://en.wikipedia.org/wiki/Kd_tree 5 ;; 6 ;; The kd tree is a binary search tree in which every branching node 7 ;; contains a kdimensional 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 halfspaces. 10 ;; 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 kdimensional 15 ;; space. The axis at each branching level is chosen in a roundrobin 16 ;; fashion. For instance, in 3D space, at level 0, the chosen axis is 17 ;; X, so points are divided according to their Xcoordinates; at level 18 ;; 1, the chosen axis is Y, so the points are divided according to 19 ;; their Ycoordinates; at the next branch level the chosen axis is Z, 20 ;; and so on. 21 ;; 4 22 ;; 5 23 ;; This code is based on the Haskell kdtree library implementation of
Note: See TracChangeset
for help on using the changeset viewer.