Changeset 25915 in project
 Timestamp:
 02/16/12 09:46:22 (9 years ago)
 Location:
 release/4/spatialtrees/trunk
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

release/4/spatialtrees/trunk/kdtree.scm
r25912 r25915 11 11 kdtree>list 12 12 kdtreemap 13 kdtreeforeach 14 kdtreeiforeach 13 15 kdtreefoldright 14 16 kdtreesubtrees 17 kdtreepoint 15 18 list>kdtree 16 19 kdtreenearestneighbor … … 18 21 kdtreeknearestneighbors 19 22 kdtreeremove 23 kdtreeslice 24 kdtreeislice 20 25 kdtreeisvalid? 21 26 kdtreeallsubtreesarevalid? … … 120 125 (KdNode (list>kdtree/depth (take sortedpoints medianindex) (+ 1 depth)) 121 126 (listref sortedpoints medianindex) 127 medianindex 122 128 (list>kdtree/depth (drop sortedpoints (+ medianindex 1)) (+ 1 depth)) 123 129 axis) … … 156 162 (cases kdtree t 157 163 (KdEmpty () #f) 158 (KdNode (l p r axis)164 (KdNode (l p i r axis) 159 165 (if (and (treeempty? l) 160 166 (treeempty? r)) p … … 181 187 (cases kdtree t 182 188 (KdEmpty () '()) 183 (KdNode (l p r axis)189 (KdNode (l p i r axis) 184 190 (let ((maybepivot (if (<= (dist2 probe p) (* radius radius)) 185 191 (list p) '()))) … … 230 236 (cases kdtree t 231 237 (KdEmpty () (KdEmpty)) 232 (KdNode (l p r axis)238 (KdNode (l p i r axis) 233 239 (if (equal? p pkill) 234 240 (list>kdtree/depth … … 239 245 (if (<= (coord axis pkill) 240 246 (coord axis p)) 241 (KdNode (remove l pkill) p r axis)242 (KdNode l p (remove r pkill) axis))247 (KdNode (remove l pkill) p i r axis) 248 (KdNode l p i (remove r pkill) axis)) 243 249 )) 244 250 )) … … 257 263 (cases kdtree t 258 264 (KdEmpty () #t) 259 (KdNode (l p r axis)265 (KdNode (l p i r axis) 260 266 (let ((x (coord axis p))) 261 267 (and (every (lambda (y) (<= (coord axis y) x )) … … 276 282 (KdNode (left kdtree?) 277 283 (p point3d?) 284 (i integer?) 278 285 (right kdtree?) 279 286 (axis integer?)) … … 291 298 (cases kdtree t 292 299 (KdEmpty () (KdEmpty)) 293 (KdNode (l x r axis)300 (KdNode (l x i r axis) 294 301 (KdNode (kdtreemap f l) 295 302 (f x) … … 298 305 )) 299 306 307 (define (kdtreeforeach f t) 308 (cases kdtree t 309 (KdEmpty () (begin)) 310 (KdNode (l x i r axis) 311 (begin 312 (kdtreeforeach f l) 313 (f x) 314 (kdtreeforeach f r) 315 )) 316 )) 317 318 (define (kdtreeiforeach f t) 319 (cases kdtree t 320 (KdEmpty () (begin)) 321 (KdNode (l x i r axis) 322 (begin 323 (kdtreeiforeach f l) 324 (f i x) 325 (kdtreeiforeach f r) 326 )) 327 )) 328 300 329 (define (kdtreefoldright f init t) 301 330 (cases kdtree t 302 331 (KdEmpty () init) 303 (KdNode (l x r _)332 (KdNode (l x i r _) 304 333 (let* ((init2 (kdtreefoldright f init r)) 305 334 (init3 (f x init2))) 306 335 (kdtreefoldright f init3 l))) 307 336 )) 337 338 (define=> (makekdtreeslice <Point>) 339 (lambda (xaxis x1 x2 t) 340 (let recur ((t t) (pts '())) 341 (cases kdtree t 342 (KdEmpty () pts) 343 (KdNode (l p i r axis) 344 (if (= axis xaxis) 345 346 (cond ((and (<= x1 (coord axis p)) 347 (<= (coord axis p) x2)) 348 (recur l (cons p (recur r pts)))) 349 350 ((< (coord axis p) x1) 351 (recur r pts)) 352 353 ((< x2 (coord axis p)) 354 (recur l pts))) 355 356 (if (and (<= x1 (coord xaxis p)) 357 (<= (coord xaxis p) x2)) 358 (recur l (cons p (recur r pts))) 359 (recur l (recur r pts))) 360 )) 361 )) 362 )) 363 364 365 (define=> (makekdtreeislice <Point>) 366 (lambda (xaxis x1 x2 t) 367 (let recur ((t t) (pts '())) 368 (cases kdtree t 369 (KdEmpty () pts) 370 (KdNode (l p i r axis) 371 (if (= axis xaxis) 372 373 (cond ((and (<= x1 (coord axis p)) 374 (<= (coord axis p) x2)) 375 (recur l (cons (cons i p) (recur r pts)))) 376 377 ((< (coord axis p) x1) 378 (recur r pts)) 379 380 ((< x2 (coord axis p)) 381 (recur l pts))) 382 383 (if (and (<= x1 (coord xaxis p)) 384 (<= (coord xaxis p) x2)) 385 (recur l (cons p (recur r pts))) 386 (recur l (recur r pts))) 387 )) 388 )) 389 )) 390 391 308 392 309 393 … … 315 399 (KdEmpty () 316 400 (list (KdEmpty))) 317 (KdNode (l x r axis)401 (KdNode (l x i r axis) 318 402 (append (kdtreesubtrees l) 319 403 (list t) … … 321 405 )) 322 406 407 (define (kdtreepoint t) 408 (cases kdtree t 409 (KdEmpty () #f) 410 (KdNode (l x i r axis) x) 411 )) 412 323 413 (define list>kdtree/depth 324 414 (makelist>kdtree/depth Pointpoint3d)) … … 335 425 (define kdtreeremove (makekdtreeremove Pointpoint3d)) 336 426 427 (define kdtreeslice (makekdtreeslice Pointpoint3d)) 428 429 (define kdtreeislice (makekdtreeislice Pointpoint3d)) 430 337 431 (define kdtreeisvalid? (makekdtreeisvalid? Pointpoint3d)) 338 432 
release/4/spatialtrees/trunk/spatialtrees.setup
r25912 r25915 18 18 '((version 1.0) 19 19 )) 20 21
Note: See TracChangeset
for help on using the changeset viewer.