Changeset 27415 in project
- Timestamp:
- 09/12/12 06:30:02 (8 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
release/4/kd-tree/trunk/kd-tree.scm
r27351 r27415 1 1 ;; 2 ;; An implementation of the K-D tree spatial indexing data structures. 3 ;; http://en.wikipedia.org/wiki/K-d_tree 2 ;; An implementation of the K-d tree spatial indexing data structure. 3 ;; 4 ;; http://en.wikipedia.org/wiki/K-d_tree 5 ;; 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. 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 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. 21 ;; 4 22 ;; 5 23 ;; This code is based on the Haskell kd-tree library implementation of
Note: See TracChangeset
for help on using the changeset viewer.