Changeset 25918 in project


Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • release/4/spatial-trees/trunk/kd-tree.scm

    r25915 r25918  
    1919   kd-tree-nearest-neighbor
    2020   kd-tree-near-neighbors
     21   kd-tree-i-near-neighbors
    2122   kd-tree-k-nearest-neighbors
    2223   kd-tree-remove
     
    212213 
    213214
     215  (define=> (make-kd-tree-i-near-neighbors <Point>)
     216    (define (tree-empty? t) (cases kd-tree t (KdEmpty () #t) (else #f)))
     217    (letrec ((near-neighbors
     218              (lambda (t radius probe)
     219                (cases kd-tree t
     220                       (KdEmpty ()  '())
     221                       (KdNode (l p i r axis)
     222                               (let ((maybe-pivot (if (<= (dist2 probe p) (* radius radius))
     223                                                      (list (list i p)) '())))
     224                                 (if (and (tree-empty? l)
     225                                          (tree-empty? r))
     226                                     maybe-pivot
     227                                     (let ((x-probe (coord axis probe))
     228                                           (xp (coord axis p)))
     229                                       (if (<= x-probe xp)
     230                                           (let ((nearest (append maybe-pivot (near-neighbors l radius probe))))
     231                                             (if (> (+ x-probe (abs radius)) xp)
     232                                                 (append (near-neighbors r radius probe) nearest)
     233                                                 nearest))
     234                                           (let ((nearest (append maybe-pivot (near-neighbors r radius probe))))
     235                                             (if (< (- x-probe (abs radius)) xp)
     236                                                 (append (near-neighbors l radius probe) nearest)
     237                                                 nearest)))
     238                                       ))
     239                                 ))
     240                       ))
     241              ))
     242      near-neighbors
     243      ))
     244 
     245
    214246 
    215247  ;; Returns the k nearest points to p within tree.
     
    420452
    421453  (define kd-tree-near-neighbors (make-kd-tree-near-neighbors Point-point3d))
     454
     455  (define kd-tree-i-near-neighbors (make-kd-tree-i-near-neighbors Point-point3d))
    422456 
    423457  (define kd-tree-k-nearest-neighbors (make-kd-tree-k-nearest-neighbors Point-point3d))
Note: See TracChangeset for help on using the changeset viewer.