Changeset 26941 in project


Ignore:
Timestamp:
06/21/12 05:14:35 (8 years ago)
Author:
Ivan Raikov
Message:

spatial-trees: really fix bugs in kd-tree-remove and -nearest-neighbor

File:
1 edited

Legend:

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

    r26940 r26941  
    199199    )
    200200
     201
    201202  (define (kd-tree-empty? t)
    202203    (cases kd-tree t
    203204           (KdLeaf (ii pp vv axis) (cis:empty? ii))
    204205           (else #f)))
     206
    205207 
    206208  (define (kd-tree->list t)
    207209    (kd-tree-fold-right cons '() t))
     210
    208211 
    209212  (define (kd-tree->list* t)
    210     (kd-tree-fold-right* (lambda (i x ax) (cons (list i x) ax)) '() t))
     213    (kd-tree-fold-right*
     214     (lambda (i x ax)
     215       (cons (list i x) ax))
     216     '() t))
     217
    211218 
    212219  (define (kd-tree-map f t)
     
    233240           ))
    234241
     242
    235243  (define (kd-tree-for-each* f t)
    236244    (cases kd-tree t
     
    243251                     ))
    244252           ))
     253
    245254 
    246255  (define (kd-tree-fold-right f init t)
     
    281290                                  (kd-tree-subtrees r)))
    282291                  ))
     292
    283293 
    284294  (define (kd-tree-points t)
     
    287297                  (KdNode (l x i r axis) (list x))
    288298                  ))
     299
    289300 
    290301  (define (kd-tree-indices t)
     
    293304                  (KdNode (l x i r axis) (list i))
    294305                  ))
     306
    295307
    296308  ;; construct a kd-tree from a list of points
     
    536548                               (let ((v
    537549                                      (if vv
    538                                           (minimum-by pp (lambda (a b) (negative? (compare-distance probe a b))) vv )
     550                                          (minimum-by pp (lambda (a b) (negative? (compare-distance probe a b)))
     551                                                      (zip (reverse (cis:elements ii)) vv ))
    539552                                          (minimum-by pp (lambda (a b) (negative? (compare-distance probe a b)))
    540553                                                      (reverse (cis:elements ii))))))
     
    685698  ;; removes the point p from t.
    686699  (define=> (make-kd-tree-remove <Point>)
    687     (lambda (list->kd-tree/depth)
     700    (lambda (list->kd-tree list->kd-tree*)
    688701      (letrec ((tree-remove
    689702                (lambda (t p-kill)
     
    717730                         (KdNode (l p i r axis)
    718731                                 (if (equal? p p-kill)
    719                                      (let ((pts1 (append (kd-tree->list* l) (kd-tree->list* r))))
    720                                        (list->kd-tree/depth 0 (length pts1) pts1 axis))
     732                                     (if (integer? i)
     733                                         (let ((pts1 (append (kd-tree->list l) (kd-tree->list r))))
     734                                           (list->kd-tree 0 (length pts1) pts1 axis))
     735                                         (let ((pts1 (append (kd-tree->list* l) (kd-tree->list* r))))
     736                                           (list->kd-tree* 0 (length pts1) pts1 axis)))
    721737                                     (if (<= (coord axis p-kill)
    722738                                             (coord axis p))
     
    831847           (kd-tree-remove
    832848            ((make-kd-tree-remove point-class)
    833              (list->kd-tree/depth cadr (lambda (i v) v))))
     849             (list->kd-tree/depth identity #f)
     850             (list->kd-tree/depth cadr (lambda (i v) (cadar v)))))
    834851           (kd-tree-nearest-neighbor
    835852            (make-kd-tree-nearest-neighbor point-class)))
    836853
    837       (make-<KdTree>
     854      (make-<KdTree> s
    838855       (lambda (points #!key (leaf-factor 10) (point-ref identity) (make-value #f))
    839856         ((list->kd-tree/depth point-ref make-value) 0 (length points) points 0 leaf-factor: leaf-factor))
Note: See TracChangeset for help on using the changeset viewer.