Changeset 25933 in project
 Timestamp:
 02/20/12 07:16:24 (9 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

release/4/spatialtrees/trunk/kdtree.scm
r25918 r25933 10 10 kdtreeempty? 11 11 kdtree>list 12 kdtree>list* 12 13 kdtreemap 13 14 kdtreeforeach 14 kdtree iforeach15 kdtreeforeach* 15 16 kdtreefoldright 17 kdtreefoldright* 16 18 kdtreesubtrees 17 19 kdtreepoint … … 19 21 kdtreenearestneighbor 20 22 kdtreenearneighbors 21 kdtree inearneighbors23 kdtreenearneighbors* 22 24 kdtreeknearestneighbors 23 25 kdtreeremove 24 26 kdtreeslice 25 kdtree islice27 kdtreeslice* 26 28 kdtreeisvalid? 27 29 kdtreeallsubtreesarevalid? … … 114 116 (define=> (makelist>kdtree/depth <Point>) 115 117 (letrec ((list>kdtree/depth 116 (lambda ( points depth)118 (lambda (m n points depth) 117 119 (if (null? points) (KdEmpty) 118 120 (let* ((axis … … 121 123 (sortedpoints 122 124 (sort points (lambda (a b) (< (coord axis a) (coord axis b))))) 123 (medianindex 124 (quotient ( (length sortedpoints) 1) 2))) 125 126 (KdNode (list>kdtree/depth (take sortedpoints medianindex) (+ 1 depth)) 125 (medianindex (quotient ( ( n m) 1) 2))) 126 (KdNode (list>kdtree/depth m (+ m medianindex) 127 (take sortedpoints medianindex) (+ 1 depth)) 127 128 (listref sortedpoints medianindex) 128 medianindex 129 (list>kdtree/depth (drop sortedpoints (+ medianindex 1)) (+ 1 depth)) 129 (+ m medianindex) 130 (list>kdtree/depth (+ m medianindex 1) n 131 (drop sortedpoints (+ medianindex 1)) (+ 1 depth)) 130 132 axis) 131 133 )) … … 213 215 214 216 215 (define=> (makekdtree inearneighbors<Point>)217 (define=> (makekdtreenearneighbors* <Point>) 216 218 (define (treeempty? t) (cases kdtree t (KdEmpty () #t) (else #f))) 217 219 (letrec ((nearneighbors … … 270 272 (KdNode (l p i r axis) 271 273 (if (equal? p pkill) 272 (list>kdtree/depth 273 (append 274 (kdtree>list l) 275 (kdtree>list r)) 276 axis) 274 (let ((pts1 (append (kdtree>list l) (kdtree>list r)))) 275 (list>kdtree/depth 0 (length pts1) pts1 axis)) 277 276 (if (<= (coord axis pkill) 278 277 (coord axis p)) … … 327 326 (kdtreefoldright cons '() t)) 328 327 328 (define (kdtree>list* t) 329 (kdtreefoldright* (lambda (i x ax) (cons (list i x) ax)) '() t)) 330 329 331 (define (kdtreemap f t) 330 332 (cases kdtree t … … 348 350 )) 349 351 350 (define (kdtree iforeachf t)352 (define (kdtreeforeach* f t) 351 353 (cases kdtree t 352 354 (KdEmpty () (begin)) 353 355 (KdNode (l x i r axis) 354 356 (begin 355 (kdtree iforeachf l)357 (kdtreeforeach* f l) 356 358 (f i x) 357 (kdtree iforeachf r)359 (kdtreeforeach* f r) 358 360 )) 359 361 )) … … 366 368 (init3 (f x init2))) 367 369 (kdtreefoldright f init3 l))) 370 )) 371 372 (define (kdtreefoldright* f init t) 373 (cases kdtree t 374 (KdEmpty () init) 375 (KdNode (l x i r _) 376 (let* ((init2 (kdtreefoldright* f init r)) 377 (init3 (f i x init2))) 378 (kdtreefoldright* f init3 l))) 368 379 )) 369 380 … … 395 406 396 407 397 (define=> (makekdtree islice<Point>)408 (define=> (makekdtreeslice* <Point>) 398 409 (lambda (xaxis x1 x2 t) 399 410 (let recur ((t t) (pts '())) … … 447 458 448 459 (define (list>kdtree points) 449 (list>kdtree/depth points 0))460 (list>kdtree/depth 0 (length points) points 0)) 450 461 451 462 (define kdtreenearestneighbor (makekdtreenearestneighbor Pointpoint3d)) … … 453 464 (define kdtreenearneighbors (makekdtreenearneighbors Pointpoint3d)) 454 465 455 (define kdtree inearneighbors (makekdtreeinearneighborsPointpoint3d))466 (define kdtreenearneighbors* (makekdtreenearneighbors* Pointpoint3d)) 456 467 457 468 (define kdtreeknearestneighbors (makekdtreeknearestneighbors Pointpoint3d)) … … 461 472 (define kdtreeslice (makekdtreeslice Pointpoint3d)) 462 473 463 (define kdtree islice (makekdtreeislicePointpoint3d))474 (define kdtreeslice* (makekdtreeslice* Pointpoint3d)) 464 475 465 476 (define kdtreeisvalid? (makekdtreeisvalid? Pointpoint3d))
Note: See TracChangeset
for help on using the changeset viewer.