Posted By

weilawei on 05/07/12


Tagged

tree k-d


Versions (?)

k-d tree


 / Published in: Clojure
 

make-kd-node [median left right]: Creates a node in a kd-tree.

make-kd-tree [k depth points]: Creates a kd-tree of kd-nodes. TODO: Not stack safe. Use loop/recur.

kd-nearest-neighbor [a-point kd-tree]: Returns the nearest neighboring point to a given point, using a kd-tree.

  1. (ns kd-tree
  2. (:use [clojure.zip]))
  3.  
  4. (defn ^{
  5. :doc "Creates a node in a kd-tree."
  6. } make-kd-node [median left right] [median left right])
  7.  
  8. (defn ^{
  9. :doc "Creates a kd-tree of kd-nodes. **TODO**: Not stack safe. Use loop/recur."
  10. } make-kd-tree [k depth points]
  11. (if (empty? points)
  12. nil
  13. (let [axis (mod depth k)
  14. sorted-points (sort-by (fn [a-point] (nth a-point axis)) > points)
  15. pivot (/ (count points) 2)
  16. median (nth sorted-points pivot)
  17. left (take (dec pivot) sorted-points)
  18. right (drop pivot sorted-points)
  19. next-depth (inc depth)]
  20. (make-kd-node
  21. median
  22. (make-kd-tree k next-depth left)
  23. (make-kd-tree k next-depth right)))))
  24.  
  25. (defn ^{
  26. :doc "Returns the nearest neighboring point to a given point, using a kd-tree."
  27. } kd-nearest-neighbor [a-point kd-tree]
  28. (let [kd-tree-zipper (seq-zip kd-tree)]
  29. (-> kd-tree-zipper down)))
  30.  
  31. (kd-nearest-neighbor [3 3 3]
  32. (make-kd-tree 3 0 [[0 1 2]
  33. [1 2 0]
  34. [2 0 1]
  35. [3 4 5]
  36. [5 3 4]
  37. [4 5 3]]))

Report this snippet  

You need to login to post a comment.