Changeset 25933 in project


Ignore:
Timestamp:
02/20/12 07:16:24 (9 years ago)
Author:
Ivan Raikov
Message:

spatial-tree: using * for procedures that use point indices

File:
1 edited

Legend:

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

    r25918 r25933  
    1010   kd-tree-empty?
    1111   kd-tree->list
     12   kd-tree->list*
    1213   kd-tree-map
    1314   kd-tree-for-each
    14    kd-tree-i-for-each
     15   kd-tree-for-each*
    1516   kd-tree-fold-right
     17   kd-tree-fold-right*
    1618   kd-tree-subtrees
    1719   kd-tree-point
     
    1921   kd-tree-nearest-neighbor
    2022   kd-tree-near-neighbors
    21    kd-tree-i-near-neighbors
     23   kd-tree-near-neighbors*
    2224   kd-tree-k-nearest-neighbors
    2325   kd-tree-remove
    2426   kd-tree-slice
    25    kd-tree-i-slice
     27   kd-tree-slice*
    2628   kd-tree-is-valid?
    2729   kd-tree-all-subtrees-are-valid?
     
    114116  (define=> (make-list->kd-tree/depth <Point>)
    115117    (letrec ((list->kd-tree/depth
    116               (lambda (points depth)
     118              (lambda (m n points depth)
    117119                (if (null? points) (KdEmpty)
    118120                    (let* ((axis
     
    121123                           (sorted-points
    122124                            (sort points (lambda (a b) (< (coord axis a) (coord axis b)))))
    123                            (median-index
    124                             (quotient (- (length sorted-points) 1) 2)))
    125 
    126                       (KdNode (list->kd-tree/depth (take sorted-points median-index) (+ 1 depth))
     125                           (median-index (quotient (- (- n m) 1) 2)))
     126                      (KdNode (list->kd-tree/depth m (+ m median-index)
     127                                                   (take sorted-points median-index) (+ 1 depth))
    127128                              (list-ref sorted-points median-index)
    128                               median-index
    129                               (list->kd-tree/depth (drop sorted-points (+ median-index 1)) (+ 1 depth))
     129                              (+ m median-index)
     130                              (list->kd-tree/depth (+ m median-index 1) n
     131                                                   (drop sorted-points (+ median-index 1)) (+ 1 depth))
    130132                              axis)
    131133                      ))
     
    213215 
    214216
    215   (define=> (make-kd-tree-i-near-neighbors <Point>)
     217  (define=> (make-kd-tree-near-neighbors* <Point>)
    216218    (define (tree-empty? t) (cases kd-tree t (KdEmpty () #t) (else #f)))
    217219    (letrec ((near-neighbors
     
    270272                       (KdNode (l p i r axis)
    271273                               (if (equal? p p-kill)
    272                                    (list->kd-tree/depth
    273                                     (append
    274                                      (kd-tree->list l)
    275                                      (kd-tree->list r))
    276                                     axis)
     274                                   (let ((pts1 (append (kd-tree->list l) (kd-tree->list r))))
     275                                     (list->kd-tree/depth 0 (length pts1) pts1 axis))
    277276                                   (if (<= (coord axis p-kill)
    278277                                           (coord axis p))
     
    327326    (kd-tree-fold-right cons '() t))
    328327 
     328  (define (kd-tree->list* t)
     329    (kd-tree-fold-right* (lambda (i x ax) (cons (list i x) ax)) '() t))
     330 
    329331  (define (kd-tree-map f t)
    330332    (cases kd-tree t
     
    348350           ))
    349351
    350   (define (kd-tree-i-for-each f t)
     352  (define (kd-tree-for-each* f t)
    351353    (cases kd-tree t
    352354           (KdEmpty () (begin))
    353355           (KdNode (l x i r axis)
    354356                   (begin
    355                      (kd-tree-i-for-each f l)
     357                     (kd-tree-for-each* f l)
    356358                     (f i x)
    357                      (kd-tree-i-for-each f r)
     359                     (kd-tree-for-each* f r)
    358360                     ))
    359361           ))
     
    366368                          (init3 (f x init2)))
    367369                     (kd-tree-fold-right f init3 l)))
     370           ))
     371
     372  (define (kd-tree-fold-right* f init t)
     373    (cases kd-tree t
     374           (KdEmpty () init)
     375           (KdNode (l x i r _)
     376                   (let* ((init2 (kd-tree-fold-right* f init r))
     377                          (init3 (f i x init2)))
     378                     (kd-tree-fold-right* f init3 l)))
    368379           ))
    369380
     
    395406 
    396407 
    397   (define=> (make-kd-tree-i-slice <Point>)
     408  (define=> (make-kd-tree-slice* <Point>)
    398409    (lambda (x-axis x1 x2 t)
    399410      (let recur ((t t)  (pts '()))
     
    447458
    448459  (define (list->kd-tree points)
    449     (list->kd-tree/depth points 0))
     460    (list->kd-tree/depth 0 (length points) points 0))
    450461
    451462  (define kd-tree-nearest-neighbor (make-kd-tree-nearest-neighbor Point-point3d))
     
    453464  (define kd-tree-near-neighbors (make-kd-tree-near-neighbors Point-point3d))
    454465
    455   (define kd-tree-i-near-neighbors (make-kd-tree-i-near-neighbors Point-point3d))
     466  (define kd-tree-near-neighbors* (make-kd-tree-near-neighbors* Point-point3d))
    456467 
    457468  (define kd-tree-k-nearest-neighbors (make-kd-tree-k-nearest-neighbors Point-point3d))
     
    461472  (define kd-tree-slice (make-kd-tree-slice Point-point3d))
    462473
    463   (define kd-tree-i-slice (make-kd-tree-i-slice Point-point3d))
     474  (define kd-tree-slice* (make-kd-tree-slice* Point-point3d))
    464475 
    465476  (define kd-tree-is-valid? (make-kd-tree-is-valid? Point-point3d))
Note: See TracChangeset for help on using the changeset viewer.