1 /************************************************************************/
2 /* */
3 /* Quad Tree implementation. */
4 /* */
5 /* Some kind of balancing is achieved by dividing a rectangle in */
6 /* quadrants. No attempt is made to balance the tree when the entries */
7 /* are not evenly spaced. */
8 /* */
9 /* Quadrants are in the cartherian plane and only based on the numbers */
10 /* even though in most applications the chirality is that of a bitmap */
11 /* image. */
12 /* */
13 /************************************************************************/
14
15 # include "appUtilConfig.h"
16 # include "geoQuadTree.h"
17
18 # include <stdlib.h>
19 # include <stdio.h>
20
21 # include <appDebugon.h>
22
23 static const int QMAP[]= { 2, 1, 3, 0 };
24
25 # define QUADRANT( x, y, xm, ym ) \
26 ( QMAP[ 2* ( (x) >= (xm) )+ ( (y) >= (ym) ) ] )
27
28 # define PARANOIA 0
29
30 /************************************************************************/
31 /* */
32 /* Debuugging routines. */
33 /* */
34 /************************************************************************/
35
qtQuadrantStr(int q)36 const char * qtQuadrantStr( int q )
37 {
38 static char scratch[12];
39
40 switch( q )
41 {
42 case QTquadNE: return "NE";
43 case QTquadNW: return "NW";
44 case QTquadSW: return "SW";
45 case QTquadSE: return "SE";
46
47 default:
48 sprintf( scratch, "%d", q );
49 break;
50 }
51
52 return scratch;
53 }
54
qtOctantStr(int o)55 const char * qtOctantStr( int o )
56 {
57 static char scratch[12];
58
59 switch( o )
60 {
61 case QToctENE: return "ENE";
62 case QToctNNE: return "NNE";
63 case QToctNNW: return "NNW";
64 case QToctWNW: return "WNW";
65 case QToctWSW: return "WSW";
66 case QToctSSW: return "SSW";
67 case QToctSSE: return "SSE";
68 case QToctESE: return "ESE";
69
70 default:
71 sprintf( scratch, "%d", o );
72 break;
73 }
74
75 return scratch;
76 }
77
78 /************************************************************************/
79 /* */
80 /* Destroy a node. */
81 /* */
82 /************************************************************************/
83
qnFree(QuadNode * qn,QuadForAllCall freefun,void * trough)84 static void qnFree( QuadNode * qn,
85 QuadForAllCall freefun,
86 void * trough )
87 {
88 int i;
89
90 for ( i= 0; i < QTquad_COUNT; i++ )
91 {
92 if ( qn->qnChildren[i] )
93 { qnFree( qn->qnChildren[i], freefun, trough ); }
94 }
95
96 if ( freefun )
97 {
98 for ( i= 0; i < qn->qnValueCount; i++ )
99 {
100 if ( qn->qnValues[i] )
101 {
102 int delete_ignored= 0;
103
104 (*freefun)( &delete_ignored,
105 qn->qnX, qn->qnY, qn->qnValues[i], trough );
106 }
107 }
108 }
109
110 if ( qn->qnValues )
111 { free( (void *)qn->qnValues ); }
112
113 free( (void *)qn );
114
115 return;
116 }
117
118 /************************************************************************/
119 /* */
120 /* Make a tree. */
121 /* */
122 /* NOTE the sanity check on the coordinates. It removes the necessity */
123 /* to check everything in the other routines. */
124 /* */
125 /************************************************************************/
126
qtMakeTree(const DocumentRectangle * dr)127 QuadTree * qtMakeTree( const DocumentRectangle * dr )
128 {
129 int d;
130 QuadTree * rval;
131
132 rval= (QuadTree *)malloc( sizeof(QuadTree) );
133 if ( ! rval )
134 { XDEB(rval); return (QuadTree *)0; }
135
136 rval->qtRectangle= *dr;
137 rval->qtRootNode= (QuadNode *)0;
138
139 d= dr->drX1- dr->drX0;
140 if ( d < dr->drY1- dr->drY0 )
141 { d= dr->drY1- dr->drY0; }
142
143 rval->qtDiameter= 1;
144 while( rval->qtDiameter <= d )
145 { rval->qtDiameter *= 2; }
146
147 return rval;
148 }
149
150 /************************************************************************/
151 /* */
152 /* Destroy a tree. */
153 /* */
154 /************************************************************************/
155
qtFreeTree(QuadTree * qt,QuadForAllCall freefun,void * trough)156 void qtFreeTree( QuadTree * qt,
157 QuadForAllCall freefun,
158 void * trough )
159 {
160 if ( qt->qtRootNode )
161 { qnFree( qt->qtRootNode, freefun, trough ); }
162
163 free( (char *)qt );
164
165 return;
166 }
167
qtFreeData(int x,int y,void * data,void * through)168 int qtFreeData( int x,
169 int y,
170 void * data,
171 void * through )
172 { free( data ); return 0; }
173
174 /************************************************************************/
175 /* */
176 /* Make a node. */
177 /* */
178 /************************************************************************/
179
qnMake(QuadNode * parent,int x,int y)180 static QuadNode * qnMake( QuadNode * parent,
181 int x,
182 int y )
183 {
184 int i;
185 QuadNode * rval= (QuadNode *)malloc( sizeof(QuadNode) );
186
187 if ( ! rval )
188 { XDEB(rval); return (QuadNode *)0; }
189
190
191 rval->qnX= x;
192 rval->qnY= y;
193 rval->qn_parent= parent;
194
195 for ( i= 0; i < QTquad_COUNT; i++ )
196 { rval->qnChildren[i]= (QuadNode *)0; }
197
198 rval->qnBusy= 0;
199 rval->qnValueCount= 0;
200 rval->qnValues= (void **)0;
201
202 return rval;
203 }
204
205 /************************************************************************/
206 /* */
207 /* Compact the array of values: Remove nulls. */
208 /* */
209 /************************************************************************/
210
qnCompactValues(QuadNode * qn)211 static void qnCompactValues( QuadNode * qn )
212 {
213 int fr;
214 int to= 0;
215
216 for ( fr= 0; fr < qn->qnValueCount; fr++ )
217 {
218 if ( qn->qnValues[fr] )
219 { qn->qnValues[to++]= qn->qnValues[fr]; }
220 }
221
222 qn->qnValueCount= to;
223 }
224
225 /************************************************************************/
226 /* */
227 /* Insert a new value into a tree. */
228 /* */
229 /************************************************************************/
230
231 # if PARANOIA
qnValidate(const QuadNode * qn)232 static void qnValidate( const QuadNode * qn )
233 {
234 int i;
235
236 for ( i= 0; i < QTquad_COUNT; i++ )
237 {
238 int q;
239 const QuadNode * child= qn->qnChildren[i];
240
241 if ( ! child )
242 { continue; }
243
244 q= QUADRANT( child->qnX, child->qnY, qn->qnX, qn->qnY );
245 if ( q != i )
246 {
247 SSDEB(qtQuadrantStr(q),qtQuadrantStr(i));
248 LLLLDEB( child->qnX, child->qnY, qn->qnX, qn->qnY );
249 }
250
251 qnValidate( child );
252 }
253 }
254 # endif
255
qtPut(QuadTree * qt,int x,int y,void * data)256 int qtPut( QuadTree * qt,
257 int x,
258 int y,
259 void * data )
260 {
261 int x0= qt->qtRectangle.drX0;
262 int xp= x0+ qt->qtDiameter;
263 int y0= qt->qtRectangle.drY0;
264 int yp= y0+ qt->qtDiameter;
265
266 int xm= ( x0+ xp )/ 2;
267 int ym= ( y0+ yp )/ 2;
268
269 QuadNode * qn;
270
271 void ** fresh;
272
273 if ( x < qt->qtRectangle.drX0 ||
274 x > qt->qtRectangle.drX1 ||
275 y < qt->qtRectangle.drY0 ||
276 y > qt->qtRectangle.drY1 )
277 { LLLLDEB(x,y,qt->qtRectangle.drX1,qt->qtRectangle.drY1); return -1; }
278
279 if ( ! qt->qtRootNode )
280 {
281 qt->qtRootNode= qnMake( (QuadNode *)0, xm, ym );
282 if ( ! qt->qtRootNode )
283 { XDEB(qt->qtRootNode); return -1; }
284 }
285
286 qn= qt->qtRootNode;
287
288 while( xm != x0 || ym != y0 )
289 {
290 int q= QUADRANT( x, y, qn->qnX, qn->qnY );
291
292 # if PARANOIA
293 if ( qn->qnX != xm || qn->qnY != ym )
294 { LLLLDEB(xm,ym,qn->qnX,qn->qnY); return -1; }
295 # endif
296
297 if ( x < xm )
298 { xp= xm; }
299 else{ x0= xm; }
300 if ( y < ym )
301 { yp= ym; }
302 else{ y0= ym; }
303
304 xm= ( x0+ xp )/ 2;
305 ym= ( y0+ yp )/ 2;
306
307 if ( ! qn->qnChildren[q] )
308 {
309 qn->qnChildren[q]= qnMake( qn, xm, ym );
310 if ( ! qn->qnChildren[q] )
311 { XDEB(qn->qnChildren[q]); return -1; }
312 }
313
314 qn= qn->qnChildren[q];
315 }
316
317 # if PARANOIA
318 if ( qn->qnX != x || qn->qnY != y )
319 { LLLLDEB(x,y,qn->qnX,qn->qnY); return -1; }
320 # endif
321 if ( qn->qnBusy )
322 { LDEB(qn->qnBusy); return -1; }
323
324 fresh= (void **)realloc( (void *)qn->qnValues,
325 (qn->qnValueCount +1)* sizeof(void *) );
326
327 if ( ! fresh )
328 { LXDEB(qn->qnValueCount,fresh); return -1; }
329
330 qn->qnValues= fresh;
331 fresh[qn->qnValueCount++]= data;
332
333 return 0;
334 }
335
336 /************************************************************************/
337 /* */
338 /* Get a series of values stored on a Quad Tree. */
339 /* */
340 /************************************************************************/
341
qtGetExact(QuadTree * qt,int x,int y,void *** const pvals,int * pnval)342 int qtGetExact( QuadTree * qt,
343 int x,
344 int y,
345 void *** const pvals,
346 int * pnval )
347 {
348 int x0= qt->qtRectangle.drX0;
349 int xp= x0+ qt->qtDiameter;
350 int y0= qt->qtRectangle.drY0;
351 int yp= y0+ qt->qtDiameter;
352
353 int xm= ( x0+ xp )/ 2;
354 int ym= ( y0+ yp )/ 2;
355
356 QuadNode * qn= qt->qtRootNode;
357
358 while( qn && ( xm != x0 || ym != y0 ) )
359 {
360 int q= QUADRANT( x, y, qn->qnX, qn->qnY );
361
362 if ( x < xm )
363 { xp= xm; }
364 else{ x0= xm; }
365 if ( y < ym )
366 { yp= ym; }
367 else{ y0= ym; }
368
369 xm= ( x0+ xp )/ 2;
370 ym= ( y0+ yp )/ 2;
371
372 qn= qn->qnChildren[q];
373 }
374
375 if ( ! qn )
376 { return 1; }
377
378 if ( qn->qnX != x || qn->qnY != y )
379 { LLLLDEB(x,y,qn->qnX,qn->qnY); return 1; }
380
381 *pvals= qn->qnValues;
382 *pnval= qn->qnValueCount;
383
384 return 0;
385 }
386
387 /************************************************************************/
388 /* */
389 /* Do something with all stored values in a rectangle. */
390 /* */
391 /************************************************************************/
392
393 static const int QTSCAN[QToct_COUNT][QTquad_COUNT]=
394 {
395 { QTquadNE, QTquadSE, QTquadNW, QTquadSW }, /* QToctENE */
396 { QTquadNE, QTquadNW, QTquadSE, QTquadSW }, /* QToctNNE */
397
398 { QTquadNW, QTquadNE, QTquadSW, QTquadSE }, /* QToctNNW */
399 { QTquadNW, QTquadSW, QTquadNE, QTquadSE }, /* QToctWNW */
400
401 { QTquadSW, QTquadNW, QTquadSE, QTquadNE }, /* QToctWSW */
402 { QTquadSW, QTquadSE, QTquadNW, QTquadNE }, /* QToctSSW */
403
404 { QTquadSE, QTquadSW, QTquadNE, QTquadNW }, /* QToctSSE */
405 { QTquadSE, QTquadNE, QTquadSW, QTquadNW }, /* QToctESE */
406 };
407
qnGetNearest(QuadNode * qn,int level,const QuadNode ** pFound,long * pD2,int x,int y,const void * data)408 static int qnGetNearest( QuadNode * qn,
409 int level,
410 const QuadNode ** pFound,
411 long * pD2,
412 int x,
413 int y,
414 const void * data )
415 {
416 int rval= 1;
417 int i;
418
419 int q= QUADRANT( x, y, qn->qnX, qn->qnY );
420 int o;
421
422 long d2x;
423 long d2y;
424 long d2;
425
426 long d[4];
427 const int * c;
428
429 d2= 0;
430 d2x= x- qn->qnX; d2x= d2x* d2x;
431 d2y= y- qn->qnY; d2y= d2y* d2y;
432 d2= d2x+ d2y;
433
434 d[0]= 0;
435 d[3]= d2;
436
437 switch( q )
438 {
439 case QTquadNE:
440 if ( x- qn->qnX > y- qn->qnY )
441 {
442 o= QToctENE;
443 d[1]= d2y; d[2]= d2x;
444 }
445 else{
446 o= QToctNNE;
447 d[1]= d2x; d[2]= d2y;
448 }
449 break;
450
451 case QTquadNW:
452 if ( qn->qnX- x < y- qn->qnY )
453 {
454 o= QToctNNW;
455 d[1]= d2x; d[2]= d2y;
456 }
457 else{
458 o= QToctWNW;
459 d[1]= d2y; d[2]= d2x;
460 }
461 break;
462
463 case QTquadSW:
464 if ( qn->qnX- x > qn->qnY- y )
465 {
466 o= QToctWSW;
467 d[1]= d2y; d[2]= d2x;
468 }
469 else{
470 o= QToctSSW;
471 d[1]= d2x; d[2]= d2y;
472 }
473 break;
474
475 case QTquadSE:
476 if ( x- qn->qnX < qn->qnY- y )
477 {
478 o= QToctSSE;
479 d[1]= d2x; d[2]= d2y;
480 }
481 else{
482 o= QToctESE;
483 d[1]= d2y; d[2]= d2x;
484 }
485 break;
486
487 default:
488 LDEB(q); return -1;
489 }
490
491 /*
492 appDebug( "NODE %*s [%4d,%4d] %s[%s] %*s N=%d D=%9ld\n",
493 2* level, "", qn->qnX, qn->qnY,
494 qtQuadrantStr( q ), qtOctantStr( o ),
495 level<16?32-2*level:2, "",
496 qn->qnValueCount, d2 );
497 */
498
499
500 c= QTSCAN[o];
501 for ( i= 0; i < QTquad_COUNT; i++ )
502 {
503 int r;
504 QuadNode * child= qn->qnChildren[c[i]];
505
506 if ( ! child )
507 { continue; }
508
509 if ( d[i] > *pD2 )
510 { continue; }
511
512 r= qnGetNearest( child, level+ 1, pFound, pD2, x, y, data );
513 if ( r < 0 )
514 { LLDEB(i,r); return -1; }
515 if ( r == 0 )
516 { rval= 0; }
517 }
518
519 if ( d2 < *pD2 &&
520 qn->qnValueCount > 0 &&
521 ( qn->qnValueCount > 1 || qn->qnValues[0] != data ) )
522 {
523 /*
524 appDebug( "GOT %*s [%4d,%4d] %*s N=%d D=%9ld (!)\n",
525 2* level, "", qn->qnX, qn->qnY,
526 level<16?32-2*level:2, "",
527 qn->qnValueCount, d2 );
528
529 */
530
531 *pFound= qn;
532 *pD2= d2;
533 rval= 0;
534 }
535
536 return rval;
537 }
538
qtGetNearest(QuadTree * qt,int x,int y,const void * data,int * pX,int * pY,void * const ** pvals,int * pnval)539 int qtGetNearest( QuadTree * qt,
540 int x,
541 int y,
542 const void * data,
543 int * pX,
544 int * pY,
545 void * const ** pvals,
546 int * pnval )
547 {
548 int rval= 0;
549 long d;
550 long d2;
551 const int level= 0;
552
553 const QuadNode * found= (const QuadNode *)0;
554
555 if ( ! qt->qtRootNode )
556 { return 1; }
557
558 if ( x < qt->qtRectangle.drX0 ||
559 x >= qt->qtRectangle.drX1 ||
560 y < qt->qtRectangle.drY0 ||
561 y >= qt->qtRectangle.drY1 )
562 { return 1; }
563
564 d2= 0;
565 d= qt->qtRectangle.drX1- qt->qtRectangle.drX0; d2 += d* d;
566 d= qt->qtRectangle.drY1- qt->qtRectangle.drY0; d2 += d* d;
567
568 rval= qnGetNearest( qt->qtRootNode, level, &found, &d2, x, y, data );
569
570 if ( rval == 0 )
571 {
572 int i;
573 int nval= found->qnValueCount;
574
575 for ( i= 0; i < found->qnValueCount; i++ )
576 {
577 if ( found->qnValues[i] == data )
578 {
579 nval--;
580
581 if ( found->qnValueCount > 1 && i != nval )
582 {
583 void * dt;
584
585 dt= found->qnValues[i];
586 found->qnValues[i]= found->qnValues[nval];
587 found->qnValues[nval]= dt;
588 }
589
590 break;
591 }
592 }
593
594 *pX= found->qnX;
595 *pY= found->qnY;
596 *pvals= found->qnValues;
597 *pnval= nval;
598 }
599
600 return rval;
601 }
602
603 /************************************************************************/
604 /* */
605 /* Perform an operation for all values in a certain rectangle. */
606 /* */
607 /************************************************************************/
608
qnForAllInRectangle(QuadNode * qn,const DocumentRectangle * dr,QuadForAllCall fun,void * through)609 static int qnForAllInRectangle( QuadNode * qn,
610 const DocumentRectangle * dr,
611 QuadForAllCall fun,
612 void * through )
613 {
614 int res;
615 int rval= 0;
616 int someDeleted= 0;
617
618 unsigned char children[QTquad_COUNT];
619 int i;
620
621 for ( i= 0; i < QTquad_COUNT; i++ )
622 { children[i]= 0; }
623
624 children[QUADRANT( dr->drX0, dr->drY0, qn->qnX, qn->qnY )]= 1;
625 children[QUADRANT( dr->drX1, dr->drY0, qn->qnX, qn->qnY )]= 1;
626 children[QUADRANT( dr->drX0, dr->drY1, qn->qnX, qn->qnY )]= 1;
627 children[QUADRANT( dr->drX1, dr->drY1, qn->qnX, qn->qnY )]= 1;
628
629 for ( i= 0; i < QTquad_COUNT; i++ )
630 {
631 if ( qn->qnChildren[i] && children[i] )
632 {
633 res= qnForAllInRectangle( qn->qnChildren[i], dr, fun, through );
634 if ( res < 0 )
635 { LDEB(res); return -1; }
636 if ( res > 0 )
637 { rval= 1; }
638 }
639 }
640
641 if ( geo2DIXYInBox( qn->qnX, qn->qnY, dr ) )
642 {
643 for ( i= 0; i < qn->qnValueCount; i++ )
644 {
645 int deleteIt= 0;
646
647 if ( ! qn->qnValues[i] )
648 { continue; }
649
650 qn->qnBusy++;
651 res= (*fun)( &deleteIt, qn->qnX, qn->qnY, qn->qnValues[i], through );
652 qn->qnBusy--;
653
654 if ( deleteIt )
655 { someDeleted= 1; qn->qnValues[i]= (void *)0; }
656
657 if ( res < 0 )
658 { LDEB(res); return -1; }
659 if ( res > 0 )
660 { rval= 1; }
661 }
662 }
663
664 if ( someDeleted && ! qn->qnBusy )
665 { qnCompactValues( qn ); }
666
667 return rval;
668 }
669
qtForAllInRectangle(const QuadTree * qt,const DocumentRectangle * dr,QuadForAllCall fun,void * through)670 int qtForAllInRectangle( const QuadTree * qt,
671 const DocumentRectangle * dr,
672 QuadForAllCall fun,
673 void * through )
674 {
675 int rval= 0;
676
677 if ( qt->qtRootNode &&
678 geoIntersectRectangle( (DocumentRectangle *)0,
679 &(qt->qtRectangle), dr ) )
680 { rval= qnForAllInRectangle( qt->qtRootNode, dr, fun, through ); }
681
682 return rval;
683 }
684
685 /************************************************************************/
686 /* */
687 /* Scan all items stored in a quad tree. As the logic of deciding */
688 /* what branches to enter is beyond the logic of simple geometry, the */
689 /* application can decide for itself. */
690 /* */
691 /************************************************************************/
692
qnForAll(QuadNode * qn,const DocumentRectangle * drParent,QuadForAllFilter filter,QuadForAllCall fun,void * through)693 static int qnForAll( QuadNode * qn,
694 const DocumentRectangle * drParent,
695 QuadForAllFilter filter,
696 QuadForAllCall fun,
697 void * through )
698 {
699 int i;
700 int res;
701 int rval= 0;
702 int someDeleted= 0;
703
704 DocumentRectangle drHere;
705
706 if ( rval == 0 && qn->qnChildren[QTquadNE] )
707 {
708 drHere= *drParent; drHere.drX0= qn->qnX; drHere.drY0= qn->qnY;
709
710 if ( geoIntersectRectangle( (DocumentRectangle *)0,
711 drParent, &drHere ) &&
712 ( ! filter || (*filter)( &drHere, through ) ) )
713 {
714 res= qnForAll( qn->qnChildren[QTquadNE], &drHere,
715 filter, fun, through );
716 if ( res < 0 )
717 { LDEB(res); return -1; }
718 if ( res > 0 )
719 { rval= 1; }
720 }
721 }
722
723 if ( rval == 0 && qn->qnChildren[QTquadNW] )
724 {
725 drHere= *drParent; drHere.drX1= qn->qnX; drHere.drY0= qn->qnY;
726
727 if ( geoIntersectRectangle( (DocumentRectangle *)0,
728 drParent, &drHere ) &&
729 ( ! filter || (*filter)( &drHere, through ) ) )
730 {
731 res= qnForAll( qn->qnChildren[QTquadNW], &drHere,
732 filter, fun, through );
733 if ( res < 0 )
734 { LDEB(res); return -1; }
735 if ( res > 0 )
736 { rval= 1; }
737 }
738 }
739
740 if ( rval == 0 && qn->qnChildren[QTquadSW] )
741 {
742 drHere= *drParent; drHere.drX1= qn->qnX; drHere.drY1= qn->qnY;
743
744 if ( geoIntersectRectangle( (DocumentRectangle *)0,
745 drParent, &drHere ) &&
746 ( ! filter || (*filter)( &drHere, through ) ) )
747 {
748 res= qnForAll( qn->qnChildren[QTquadSW], &drHere,
749 filter, fun, through );
750 if ( res < 0 )
751 { LDEB(res); return -1; }
752 if ( res > 0 )
753 { rval= 1; }
754 }
755 }
756
757 if ( rval == 0 && qn->qnChildren[QTquadSE] )
758 {
759 drHere= *drParent; drHere.drX0= qn->qnX; drHere.drY1= qn->qnY;
760
761 if ( geoIntersectRectangle( (DocumentRectangle *)0,
762 drParent, &drHere ) &&
763 ( ! filter || (*filter)( &drHere, through ) ) )
764 {
765 res= qnForAll( qn->qnChildren[QTquadSE], &drHere,
766 filter, fun, through );
767 if ( res < 0 )
768 { LDEB(res); return -1; }
769 if ( res > 0 )
770 { rval= 1; }
771 }
772 }
773
774 if ( rval == 0 && qn->qnValueCount > 0 )
775 {
776 for ( i= 0; i < qn->qnValueCount; i++ )
777 {
778 int deleteIt= 0;
779
780 if ( ! qn->qnValues[i] )
781 { continue; }
782
783 qn->qnBusy++;
784 res= (*fun)( &deleteIt, qn->qnX, qn->qnY, qn->qnValues[i], through );
785 qn->qnBusy--;
786
787 if ( deleteIt )
788 { someDeleted= 1; qn->qnValues[i]= (void *)0; }
789
790 if ( res < 0 )
791 { LDEB(res); return -1; }
792 if ( res > 0 )
793 { rval= 1; break; }
794 }
795
796 if ( someDeleted && ! qn->qnBusy )
797 { qnCompactValues( qn ); }
798 }
799
800 return rval;
801 }
802
qtForAll(const QuadTree * qt,QuadForAllFilter filter,QuadForAllCall fun,void * through)803 int qtForAll( const QuadTree * qt,
804 QuadForAllFilter filter,
805 QuadForAllCall fun,
806 void * through )
807 {
808 int rval= 0;
809
810 if ( qt->qtRootNode &&
811 ( ! filter || (*filter)( &(qt->qtRectangle), through ) ) )
812 {
813 rval= qnForAll( qt->qtRootNode, &(qt->qtRectangle),
814 filter, fun, through );
815 }
816
817 return rval;
818 }
819