Changeset 27033 in project


Ignore:
Timestamp:
07/10/12 07:14:15 (9 years ago)
Author:
Ivan Raikov
Message:

spatial-trees: added get-min and get-max operations to kd-tree

Location:
release/4/spatial-trees/trunk
Files:
3 edited

Legend:

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

    r27008 r27033  
    2121   kd-tree-points
    2222   kd-tree-indices
     23   kd-tree-min
     24   kd-tree-max
    2325   kd-tree-size
    2426  )
     
    177179            (right kd-tree?)
    178180            (axis  positive-or-zero-integer?)
    179             (size  positive-integer?)
     181            (ci    cis:cis?)
    180182            )
    181183    (KdLeaf (ii cis:cis?)
     
    207209           (KdLeaf (ii pp vv axis)
    208210                   (KdLeaf ii (map f pp) vv axis))
    209            (KdNode (l x i r axis sz)
     211           (KdNode (l x i r axis ci)
    210212                   (KdNode (kd-tree-map f l)
    211213                           (f x)
    212214                           i
    213215                           (kd-tree-map f r)
    214                            axis sz))
     216                           axis ci))
    215217           ))
    216218 
     
    218220    (cases kd-tree t
    219221           (KdLeaf (ii pp vv axis) (for-each f pp))
    220            (KdNode (l x i r axis sz)
     222           (KdNode (l x i r axis ci)
    221223                   (begin
    222224                     (kd-tree-for-each f l)
     
    230232    (cases kd-tree t
    231233           (KdLeaf (ii pp vv axis) (for-each f (reverse (cis:elements ii)) vv pp))
    232            (KdNode (l x i r axis sz)
     234           (KdNode (l x i r axis ci)
    233235                   (begin
    234236                     (kd-tree-for-each* f l)
     
    243245           (KdLeaf (ii pp vv axis)
    244246                   (fold-right f init pp))
    245            (KdNode (l p i r axis sz)
     247           (KdNode (l p i r axis ci)
    246248                   (let* ((init2 (kd-tree-fold-right f init r))
    247249                          (init3 (f p init2)))
     
    256258                       (fold-right f init (zip (reverse (cis:elements ii)) vv) pp)
    257259                       (fold-right f init (reverse (cis:elements ii)) pp)))
    258            (KdNode (l x i r axis sz)
     260           (KdNode (l x i r axis ci)
    259261                   (let* ((init2 (kd-tree-fold-right* f init r))
    260262                          (init3 (f i x init2)))
     
    271273    (cases kd-tree t
    272274                  (KdLeaf (ii pp vv axis)  (list t))
    273                   (KdNode (l x i r axis sz)
     275                  (KdNode (l x i r axis ci)
    274276                          (append (kd-tree-subtrees l)
    275277                                  (list t)
     
    281283    (cases kd-tree t
    282284                  (KdLeaf (ii pp vv axis)  pp)
    283                   (KdNode (l x i r axis sz) (list x))
     285                  (KdNode (l x i r axis ci) (list x))
    284286                  ))
    285287
     
    288290    (cases kd-tree t
    289291                  (KdLeaf (ii pp vv axis) (cis:elements ii))
    290                   (KdNode (l x i r axis sz) (list i))
     292                  (KdNode (l x i r axis ci) (list i))
    291293                  ))
    292294
     
    294296    (cases kd-tree t
    295297           (KdLeaf (ii pp vv axis) (cis:cardinal ii))
    296            (KdNode (l x i r axis sz) sz)))
     298           (KdNode (l x i r axis ci) (cis:cardinal ci))))
     299
     300  (define (kd-tree-min t)
     301    (cases kd-tree t
     302           (KdLeaf (ii pp vv axis) (cis:get-min ii))
     303           (KdNode (l x i r axis ci) (cis:get-min ci))))
     304
     305  (define (kd-tree-max t)
     306    (cases kd-tree t
     307           (KdLeaf (ii pp vv axis) (cis:get-max ii))
     308           (KdNode (l x i r axis ci) (cis:get-max ci))))
     309
     310
    297311
    298312
     
    358372                                (list->kd-tree/depth (+ m median-index 1) n gte depth1
    359373                                                     leaf-factor: leaf-factor)
    360                                 axis (- n m))))
     374                                axis
     375                                (cis:interval m (- n 1)))))
    361376                    )))
    362377                 ))
     
    490505                               (minimum-by pp (lambda (a b) (negative? (compare-distance probe a b)))))
    491506
    492                        (KdNode (l p i r axis sz)
     507                       (KdNode (l p i r axis ci)
    493508                               (if (and (tree-empty? l)
    494509                                        (tree-empty? r)) p
     
    547562                                 (and v (reverse v))))
    548563
    549                        (KdNode (l p i r axis sz)
     564                       (KdNode (l p i r axis ci)
    550565
    551566                               (if (and (tree-empty? l)
     
    577592                                 (filter (lambda (p) (<= (fdist probe p) r2)) pp)))
    578593
    579                        (KdNode (l p i r axis sz)
     594                       (KdNode (l p i r axis ci)
    580595                               (let ((maybe-pivot
    581596                                      (if (<= (fdist probe p) (* radius radius)) (list p) '())))
     
    624639                                             
    625640
    626                        (KdNode (l p i r axis sz)
     641                       (KdNode (l p i r axis ci)
    627642                               (let ((maybe-pivot
    628643                                      (if (<= (fdist probe p) (* radius radius))
     
    727742                                     ))
    728743
    729                          (KdNode (l p i r axis sz)
     744                         (KdNode (l p i r axis ci)
    730745
    731746                                 ;(fprintf (current-error-port) "kd-tree-remove: p = ~A~%" p)
     
    748763                                           (and (or l1 r1)
    749764                                                (KdNode (or l1 l) p i (or r1 r) axis
    750                                                         (+ 1 (kd-tree-size (or l1 l))
    751                                                            (kd-tree-size (or r1 r))))))
     765                                                        (cis:add (if (integer? i) i (car i))
     766                                                                 (cis:interval (kd-tree-min (or l1 l))
     767                                                                               (kd-tree-max (or r1 r)))))
     768                                                ))
    752769
    753770                                         (let* ((r1 (tree-remove r p-kill))
     
    756773                                           (and (or r1 l1)
    757774                                                (KdNode (or l1 l) p i (or r1 r) axis
    758                                                         (+ 1 (kd-tree-size (or l1 l))
    759                                                            (kd-tree-size (or r1 r))))))
     775                                                        (cis:add (if (integer? i) i (car i))
     776                                                                 (cis:interval (kd-tree-min (or l1 l))
     777                                                                               (kd-tree-max (or r1 r)))))
     778                                                ))
    760779                                     )))
    761780                         ))
     
    775794             (KdLeaf (ii pp vv axis)  #t)
    776795
    777              (KdNode (l p i r axis sz)
     796             (KdNode (l p i r axis ci)
    778797                     (let ((x (coord axis p)))
    779798                       (and (every (lambda (y) (<= (coord axis y) x ))
     
    804823                           
    805824
    806                (KdNode (l p i r axis sz)
     825               (KdNode (l p i r axis ci)
    807826                       (if (= axis x-axis)
    808827                           
     
    838857                               pts))
    839858
    840                (KdNode (l p i r axis sz)
     859               (KdNode (l p i r axis ci)
    841860                       (if (= axis x-axis)
    842861                           
  • release/4/spatial-trees/trunk/spatial-trees.setup

    r27008 r27033  
    1616 
    1717  ;; Assoc list with properties for your extension:
    18   '((version 2.8)
     18  '((version 2.9)
    1919    ))
  • release/4/spatial-trees/trunk/tests/run.scm

    r27008 r27033  
    9999
    100100(define (test1)
    101   (let ((n 1000) (k 40) (r 0.2) (randst (random-mtzig:init)))
     101  (let ((n 10000) (k 40) (r 0.2) (randst (random-mtzig:init)))
    102102 
    103103  (let recur ((ntrials 10))
Note: See TracChangeset for help on using the changeset viewer.