Changeset 25918 in project

Timestamp:

02/17/12 08:39:38 (9 years ago)

Author:

Ivan Raikov

Message:

spatial-trees: added -i-near-neighbors procedure to kd-tree

File:

• release/4/spatial-trees/trunk/kd-tree.scm (modified) (3 diffs)

release/4/spatial-trees/trunk/kd-tree.scm

@@ -19 +19 @@
    kd-tree-nearest-neighbor
    kd-tree-near-neighbors
+   kd-tree-i-near-neighbors
    kd-tree-k-nearest-neighbors
    kd-tree-remove
@@ -212 +213 @@
   
 
+  (define=> (make-kd-tree-i-near-neighbors <Point>)
+    (define (tree-empty? t) (cases kd-tree t (KdEmpty () #t) (else #f)))
+    (letrec ((near-neighbors
+              (lambda (t radius probe)
+                (cases kd-tree t
+                       (KdEmpty ()  '())
+                       (KdNode (l p i r axis)
+                               (let ((maybe-pivot (if (<= (dist2 probe p) (* radius radius))
+                                                      (list (list i p)) '())))
+                                 (if (and (tree-empty? l)
+                                          (tree-empty? r))
+                                     maybe-pivot
+                                     (let ((x-probe (coord axis probe))
+                                           (xp (coord axis p)))
+                                       (if (<= x-probe xp)
+                                           (let ((nearest (append maybe-pivot (near-neighbors l radius probe))))
+                                             (if (> (+ x-probe (abs radius)) xp)
+                                                 (append (near-neighbors r radius probe) nearest)
+                                                 nearest))
+                                           (let ((nearest (append maybe-pivot (near-neighbors r radius probe))))
+                                             (if (< (- x-probe (abs radius)) xp)
+                                                 (append (near-neighbors l radius probe) nearest)
+                                                 nearest)))
+                                       ))
+                                 ))
+                       ))
+              ))
+      near-neighbors
+      ))
+  
+
   
   ;; Returns the k nearest points to p within tree.
@@ -420 +452 @@
 
   (define kd-tree-near-neighbors (make-kd-tree-near-neighbors Point-point3d))
+
+  (define kd-tree-i-near-neighbors (make-kd-tree-i-near-neighbors Point-point3d))
   
   (define kd-tree-k-nearest-neighbors (make-kd-tree-k-nearest-neighbors Point-point3d))