Changeset 26970 in project


Ignore:
Timestamp:
07/02/12 11:40:35 (9 years ago)
Author:
Ivan Raikov
Message:

spatial-trees: bug fix in kd-tree-remove where the size of the new tree was not computed properly

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

Legend:

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

    r26956 r26970  
    553553                              (if nn (append candidates1 (list nn)) candidates1))
    554554                            candidates1)))
     555
    555556                  (let ((v (minimum-by candidates2 (lambda (a b) (negative? (compare-distance probe (cadr a) (cadr b)))))))
    556557                    v)
     
    573574
    574575                               (if (and (tree-empty? l)
    575                                         (tree-empty? r)) (list i p)
    576                                         (let ((x-probe (coord axis probe))
    577                                               (xp (coord axis p))
    578                                               (xi i))
    579 
    580                                           (if (<= x-probe xp)
    581                                               (find-nearest l r i p probe xp x-probe)
    582                                               (find-nearest r l i p probe xp x-probe))
    583                                           ))
     576                                        (tree-empty? r))
     577                                   (list i p)
     578                                   (let ((x-probe (coord axis probe))
     579                                         (xp (coord axis p))
     580                                         (xi i))
     581                                     (if (<= x-probe xp)
     582                                         (find-nearest l r i p probe xp x-probe)
     583                                         (find-nearest r l i p probe xp x-probe))
     584                                     ))
    584585                               ))
    585586                )))
     
    723724                                                  (lambda (i p v) (and (equal? p p-kill) (list i p v)))
    724725                                                  (reverse (cis:elements ii)) pp vv)))
     726                                       (fprintf (current-error-port) "kd-tree-remove: ipvs = ~A~%" ipvs)
     727                                       (fprintf (current-error-port) "kd-tree-remove: cardinal ii = ~A~%" (cis:cardinal ii))
    725728                                       (let ((ii1 (fold (lambda (i ax) (cis:remove i ax))
    726729                                                        ii (map car ipvs)))
     
    731734                                                        vv (map caddr ipvs)))
    732735                                             )
     736                                         (fprintf (current-error-port) "kd-tree-remove: cardinal ii1 = ~A~%" (cis:cardinal ii1))
     737
    733738                                         (KdLeaf ii1 pp1 vv1 axis)
    734739                                         ))
     
    745750
    746751                         (KdNode (l p i r axis sz)
     752                                 
     753                                 (fprintf (current-error-port) "kd-tree-remove: p = ~A~%" p)
     754                                 (fprintf (current-error-port) "kd-tree-remove: p-kill = ~A~%" p-kill)
     755                                 (fprintf (current-error-port) "kd-tree-remove: equal? p p-kill = ~A~%" (equal? p p-kill))
     756
    747757                                 (if (equal? p p-kill)
     758
    748759                                     (if (integer? i)
    749760                                         (let ((pts1 (append (kd-tree->list l) (kd-tree->list r))))
     
    751762                                         (let ((pts1 (append (kd-tree->list* l) (kd-tree->list* r))))
    752763                                           (list->kd-tree* 0 (length pts1) pts1 axis)))
     764
    753765                                     (if (<= (coord axis p-kill)
    754766                                             (coord axis p))
    755767                                         (let ((l1 (tree-remove l p-kill)))
    756                                            (KdNode l1 p i r axis (+ (kd-tree-size l1) (kd-tree-size r))))
     768                                           
     769                                           (fprintf (current-error-port) "kd-tree-remove: kd-tree-size l1 = ~A~%" (kd-tree-size l1))
     770                                           (fprintf (current-error-port) "kd-tree-remove: kd-tree-size r = ~A~%" (kd-tree-size r))
     771
     772                                           (KdNode l1 p i r axis (+ 1 (kd-tree-size l1) (kd-tree-size r))))
    757773                                         (let ((r1 (tree-remove r p-kill)))
    758                                            (KdNode l p i r1 axis (+ (kd-tree-size l) (kd-tree-size r1)))))
     774                                           
     775                                           (fprintf (current-error-port) "kd-tree-remove: kd-tree-size l = ~A~%" (kd-tree-size l))
     776                                           (fprintf (current-error-port) "kd-tree-remove: kd-tree-size r1 = ~A~%" (kd-tree-size r1))
     777
     778                                           (KdNode l p i r1 axis (+ 1 (kd-tree-size l) (kd-tree-size r1)))))
    759779                                     ))
    760780                         ))
  • release/4/spatial-trees/trunk/spatial-trees.setup

    r26956 r26970  
    44  (make-pathname #f fn ##sys#load-dynamic-extension))   
    55
    6 (compile -d2 -O  -S -s kd-tree.scm -j kd-tree)
     6(compile -d0 -O2  -S -s kd-tree.scm -j kd-tree)
    77(compile -s kd-tree.import.scm)
    88
Note: See TracChangeset for help on using the changeset viewer.