1 : /******************************************************************************
2 : * $Id: cpl_quad_tree.cpp 15067 2008-07-28 22:08:58Z rouault $
3 : *
4 : * Project: CPL - Common Portability Library
5 : * Purpose: Implementation of quadtree building and searching functions.
6 : * Derived from shapelib and mapserver implementations
7 : * Author: Frank Warmerdam, warmerdam@pobox.com
8 : * Even Rouault, <even dot rouault at mines dash paris dot org>
9 : *
10 : ******************************************************************************
11 : * Copyright (c) 1999-2008, Frank Warmerdam
12 : *
13 : * Permission is hereby granted, free of charge, to any person obtaining a
14 : * copy of this software and associated documentation files (the "Software"),
15 : * to deal in the Software without restriction, including without limitation
16 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
17 : * and/or sell copies of the Software, and to permit persons to whom the
18 : * Software is furnished to do so, subject to the following conditions:
19 : *
20 : * The above copyright notice and this permission notice shall be included
21 : * in all copies or substantial portions of the Software.
22 : *
23 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
24 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
26 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
28 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
29 : * DEALINGS IN THE SOFTWARE.
30 : ******************************************************************************
31 : *
32 : */
33 :
34 : #include "cpl_conv.h"
35 : #include "cpl_quad_tree.h"
36 :
37 : CPL_CVSID("$Id: cpl_quad_tree.cpp 15067 2008-07-28 22:08:58Z rouault $");
38 :
39 : #define MAX_DEFAULT_TREE_DEPTH 12
40 : #define MAX_SUBNODES 4
41 :
42 : typedef struct _QuadTreeNode QuadTreeNode;
43 :
44 : struct _QuadTreeNode
45 : {
46 : /* area covered by this psNode */
47 : CPLRectObj rect;
48 :
49 : /* list of shapes stored at this psNode. */
50 : int nFeatures;
51 : void **pahFeatures;
52 :
53 : int nNumSubNodes;
54 : QuadTreeNode *apSubNode[MAX_SUBNODES];
55 : };
56 :
57 : struct _CPLQuadTree
58 : {
59 : QuadTreeNode *psRoot;
60 : CPLQuadTreeGetBoundsFunc pfnGetBounds;
61 : int nFeatures;
62 : int nMaxDepth;
63 : int nBucketCapacity;
64 : double dfSplitRatio;
65 : };
66 :
67 :
68 : static void CPLQuadTreeAddFeatureInternal(CPLQuadTree *hQuadTree,
69 : void* hFeature,
70 : const CPLRectObj *pRect);
71 :
72 : /* -------------------------------------------------------------------- */
73 : /* If the following is 0.5, psNodes will be split in half. If it */
74 : /* is 0.6 then each apSubNode will contain 60% of the parent */
75 : /* psNode, with 20% representing overlap. This can be help to */
76 : /* prevent small objects on a boundary from shifting too high */
77 : /* up the hQuadTree. */
78 : /* -------------------------------------------------------------------- */
79 : #define DEFAULT_SPLIT_RATIO 0.55
80 :
81 : /*
82 : ** Returns TRUE if rectangle a is contained in rectangle b
83 : */
84 0 : static CPL_INLINE int CPL_RectContained(const CPLRectObj *a, const CPLRectObj *b)
85 : {
86 0 : if(a->minx >= b->minx && a->maxx <= b->maxx)
87 0 : if(a->miny >= b->miny && a->maxy <= b->maxy)
88 0 : return(TRUE);
89 0 : return(FALSE);
90 : }
91 :
92 : /*
93 : ** Returns TRUE if rectangles a and b overlap
94 : */
95 0 : static CPL_INLINE int CPL_RectOverlap(const CPLRectObj *a, const CPLRectObj *b)
96 : {
97 0 : if(a->minx > b->maxx) return(FALSE);
98 0 : if(a->maxx < b->minx) return(FALSE);
99 0 : if(a->miny > b->maxy) return(FALSE);
100 0 : if(a->maxy < b->miny) return(FALSE);
101 0 : return(TRUE);
102 : }
103 :
104 : /************************************************************************/
105 : /* CPLQuadTreeNodeCreate() */
106 : /************************************************************************/
107 :
108 0 : static QuadTreeNode *CPLQuadTreeNodeCreate(const CPLRectObj* pRect)
109 : {
110 : QuadTreeNode *psNode;
111 :
112 0 : psNode = (QuadTreeNode *) CPLMalloc(sizeof(QuadTreeNode));
113 :
114 0 : psNode->nFeatures = 0;
115 0 : psNode->pahFeatures = NULL;
116 :
117 0 : psNode->nNumSubNodes = 0;
118 :
119 0 : memcpy(&(psNode->rect), pRect, sizeof(CPLRectObj));
120 :
121 0 : return psNode;
122 : }
123 :
124 : /************************************************************************/
125 : /* CPLQuadTreeCreate() */
126 : /************************************************************************/
127 :
128 : /**
129 : * Create a new quadtree
130 : *
131 : * @param pGlobalBounds a pointer to the global extent of all
132 : * the elements that will be inserted
133 : * @param pfnGetBounds a user provided function to get the bounding box of
134 : * the inserted elements
135 : *
136 : * @return a newly allocated quadtree
137 : */
138 :
139 0 : CPLQuadTree *CPLQuadTreeCreate(const CPLRectObj* pGlobalBounds, CPLQuadTreeGetBoundsFunc pfnGetBounds)
140 : {
141 : CPLQuadTree *hQuadTree;
142 :
143 0 : CPLAssert(pGlobalBounds);
144 :
145 : /* -------------------------------------------------------------------- */
146 : /* Allocate the hQuadTree object */
147 : /* -------------------------------------------------------------------- */
148 0 : hQuadTree = (CPLQuadTree *) CPLMalloc(sizeof(CPLQuadTree));
149 :
150 0 : hQuadTree->nFeatures = 0;
151 0 : hQuadTree->pfnGetBounds = pfnGetBounds;
152 0 : hQuadTree->nMaxDepth = 0;
153 0 : hQuadTree->nBucketCapacity = 8;
154 :
155 0 : hQuadTree->dfSplitRatio = DEFAULT_SPLIT_RATIO;
156 :
157 : /* -------------------------------------------------------------------- */
158 : /* Allocate the psRoot psNode. */
159 : /* -------------------------------------------------------------------- */
160 0 : hQuadTree->psRoot = CPLQuadTreeNodeCreate(pGlobalBounds);
161 :
162 0 : return hQuadTree;
163 : }
164 :
165 : /************************************************************************/
166 : /* CPLQuadTreeGetAdvisedMaxDepth() */
167 : /************************************************************************/
168 :
169 : /**
170 : * Returns the optimal depth of a quadtree to hold nExpectedFeatures
171 : *
172 : * @param nExpectedFeatures the expected maximum number of elements to be inserted
173 : *
174 : * @return the optimal depth of a quadtree to hold nExpectedFeatures
175 : */
176 :
177 0 : int CPLQuadTreeGetAdvisedMaxDepth(int nExpectedFeatures)
178 : {
179 : /* -------------------------------------------------------------------- */
180 : /* Try to select a reasonable one */
181 : /* that implies approximately 8 shapes per node. */
182 : /* -------------------------------------------------------------------- */
183 0 : int nMaxDepth = 0;
184 0 : int nMaxNodeCount = 1;
185 :
186 0 : while( nMaxNodeCount*4 < nExpectedFeatures )
187 : {
188 0 : nMaxDepth += 1;
189 0 : nMaxNodeCount = nMaxNodeCount * 2;
190 : }
191 :
192 : CPLDebug( "CPLQuadTree",
193 : "Estimated spatial index tree depth: %d",
194 0 : nMaxDepth );
195 :
196 : /* NOTE: Due to problems with memory allocation for deep trees,
197 : * automatically estimated depth is limited up to 12 levels.
198 : * See Ticket #1594 for detailed discussion.
199 : */
200 0 : if( nMaxDepth > MAX_DEFAULT_TREE_DEPTH )
201 : {
202 0 : nMaxDepth = MAX_DEFAULT_TREE_DEPTH;
203 :
204 : CPLDebug( "CPLQuadTree",
205 : "Falling back to max number of allowed index tree levels (%d).",
206 0 : MAX_DEFAULT_TREE_DEPTH );
207 :
208 : }
209 :
210 0 : return nMaxDepth;
211 : }
212 :
213 : /************************************************************************/
214 : /* CPLQuadTreeSetMaxDepth() */
215 : /************************************************************************/
216 :
217 : /**
218 : * Set the maximum depth of a quadtree. By default, quad trees have
219 : * no maximum depth, but a maximum bucket capacity.
220 : *
221 : * @param hQuadTree the quad tree
222 : * @param nMaxDepth the maximum depth allowed
223 : */
224 :
225 0 : void CPLQuadTreeSetMaxDepth(CPLQuadTree *hQuadTree, int nMaxDepth)
226 : {
227 0 : hQuadTree->nMaxDepth = nMaxDepth;
228 0 : }
229 :
230 : /************************************************************************/
231 : /* CPLQuadTreeSetBucketCapacity() */
232 : /************************************************************************/
233 :
234 : /**
235 : * Set the maximum capacity of a node of a quadtree. The default value is 8.
236 : * Note that the maximum capacity will only be honoured if the features
237 : * inserted have a point geometry. Otherwise it may be exceeded.
238 : *
239 : * @param hQuadTree the quad tree
240 : * @param nBucketCapacity the maximum capactiy of a node of a quadtree
241 : */
242 :
243 0 : void CPLQuadTreeSetBucketCapacity(CPLQuadTree *hQuadTree, int nBucketCapacity)
244 : {
245 0 : hQuadTree->nBucketCapacity = nBucketCapacity;
246 0 : }
247 :
248 : /************************************************************************/
249 : /* CPLQuadTreeInsert() */
250 : /************************************************************************/
251 :
252 : /**
253 : * Insert a feature into a quadtree
254 : *
255 : * @param hQuadTree the quad tree
256 : * @param hFeature the feature to insert
257 : */
258 :
259 0 : void CPLQuadTreeInsert(CPLQuadTree * hQuadTree, void* hFeature)
260 : {
261 : CPLRectObj bounds;
262 0 : hQuadTree->nFeatures ++;
263 0 : hQuadTree->pfnGetBounds(hFeature, &bounds);
264 0 : CPLQuadTreeAddFeatureInternal(hQuadTree, hFeature, &bounds);
265 0 : }
266 :
267 : /************************************************************************/
268 : /* CPLQuadTreeNodeDestroy() */
269 : /************************************************************************/
270 :
271 0 : static void CPLQuadTreeNodeDestroy(QuadTreeNode *psNode)
272 : {
273 : int i;
274 :
275 0 : for(i=0; i<psNode->nNumSubNodes; i++ )
276 : {
277 0 : if(psNode->apSubNode[i])
278 0 : CPLQuadTreeNodeDestroy(psNode->apSubNode[i]);
279 : }
280 :
281 0 : if(psNode->pahFeatures)
282 0 : CPLFree(psNode->pahFeatures);
283 :
284 0 : CPLFree(psNode);
285 0 : }
286 :
287 :
288 : /************************************************************************/
289 : /* CPLQuadTreeDestroy() */
290 : /************************************************************************/
291 :
292 : /**
293 : * Destroy a quadtree
294 : *
295 : * @param hQuadTree the quad tree to destroy
296 : */
297 :
298 0 : void CPLQuadTreeDestroy(CPLQuadTree *hQuadTree)
299 : {
300 0 : CPLAssert(hQuadTree);
301 0 : CPLQuadTreeNodeDestroy(hQuadTree->psRoot);
302 0 : CPLFree(hQuadTree);
303 0 : }
304 :
305 :
306 :
307 : /************************************************************************/
308 : /* CPLQuadTreeSplitBounds() */
309 : /************************************************************************/
310 :
311 0 : static void CPLQuadTreeSplitBounds( double dfSplitRatio,
312 : const CPLRectObj *in,
313 : CPLRectObj *out1,
314 : CPLRectObj *out2)
315 : {
316 : double range;
317 :
318 : /* -------------------------------------------------------------------- */
319 : /* The output bounds will be very similar to the input bounds, */
320 : /* so just copy over to start. */
321 : /* -------------------------------------------------------------------- */
322 0 : memcpy(out1, in, sizeof(CPLRectObj));
323 0 : memcpy(out2, in, sizeof(CPLRectObj));
324 :
325 : /* -------------------------------------------------------------------- */
326 : /* Split in X direction. */
327 : /* -------------------------------------------------------------------- */
328 0 : if((in->maxx - in->minx) > (in->maxy - in->miny)) {
329 0 : range = in->maxx - in->minx;
330 :
331 0 : out1->maxx = in->minx + range * dfSplitRatio;
332 0 : out2->minx = in->maxx - range * dfSplitRatio;
333 : }
334 :
335 : /* -------------------------------------------------------------------- */
336 : /* Otherwise split in Y direction. */
337 : /* -------------------------------------------------------------------- */
338 : else {
339 0 : range = in->maxy - in->miny;
340 :
341 0 : out1->maxy = in->miny + range * dfSplitRatio;
342 0 : out2->miny = in->maxy - range * dfSplitRatio;
343 : }
344 0 : }
345 :
346 : /************************************************************************/
347 : /* CPLQuadTreeNodeAddFeatureAlg1() */
348 : /************************************************************************/
349 :
350 0 : static void CPLQuadTreeNodeAddFeatureAlg1( CPLQuadTree* hQuadTree,
351 : QuadTreeNode *psNode,
352 : void* hFeature,
353 : const CPLRectObj* pRect)
354 : {
355 : int i;
356 0 : if (psNode->nNumSubNodes == 0)
357 : {
358 : /* If we have reached the max bucket capacity, try to insert */
359 : /* in a subnode if possible */
360 0 : if (psNode->nFeatures >= hQuadTree->nBucketCapacity)
361 : {
362 : CPLRectObj half1, half2, quad1, quad2, quad3, quad4;
363 :
364 0 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &psNode->rect, &half1, &half2);
365 0 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half1, &quad1, &quad2);
366 0 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half2, &quad3, &quad4);
367 :
368 0 : if (CPL_RectContained(pRect, &quad1) ||
369 : CPL_RectContained(pRect, &quad2) ||
370 : CPL_RectContained(pRect, &quad3) ||
371 : CPL_RectContained(pRect, &quad4))
372 : {
373 0 : psNode->nNumSubNodes = 4;
374 0 : psNode->apSubNode[0] = CPLQuadTreeNodeCreate(&quad1);
375 0 : psNode->apSubNode[1] = CPLQuadTreeNodeCreate(&quad2);
376 0 : psNode->apSubNode[2] = CPLQuadTreeNodeCreate(&quad3);
377 0 : psNode->apSubNode[3] = CPLQuadTreeNodeCreate(&quad4);
378 :
379 0 : int oldNumFeatures = psNode->nFeatures;
380 0 : void** oldFeatures = psNode->pahFeatures;
381 0 : psNode->nFeatures = 0;
382 0 : psNode->pahFeatures = NULL;
383 :
384 : /* redispatch existing pahFeatures in apSubNodes */
385 : int i;
386 0 : for(i=0;i<oldNumFeatures;i++)
387 : {
388 : CPLRectObj hFeatureBound;
389 0 : hQuadTree->pfnGetBounds(oldFeatures[i], &hFeatureBound);
390 0 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, psNode, oldFeatures[i], &hFeatureBound);
391 : }
392 :
393 0 : CPLFree(oldFeatures);
394 :
395 : /* recurse back on this psNode now that it has apSubNodes */
396 0 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, psNode, hFeature, pRect);
397 0 : return;
398 : }
399 : }
400 : }
401 : else
402 : {
403 : /* -------------------------------------------------------------------- */
404 : /* If there are apSubNodes, then consider whether this object */
405 : /* will fit in them. */
406 : /* -------------------------------------------------------------------- */
407 0 : for(i=0; i<psNode->nNumSubNodes; i++ )
408 : {
409 0 : if( CPL_RectContained(pRect, &psNode->apSubNode[i]->rect))
410 : {
411 0 : CPLQuadTreeNodeAddFeatureAlg1( hQuadTree, psNode->apSubNode[i], hFeature, pRect);
412 0 : return;
413 : }
414 : }
415 : }
416 :
417 : /* -------------------------------------------------------------------- */
418 : /* If none of that worked, just add it to this psNodes list. */
419 : /* -------------------------------------------------------------------- */
420 0 : psNode->nFeatures++;
421 :
422 0 : psNode->pahFeatures = (void**) CPLRealloc( psNode->pahFeatures, sizeof(void*) * psNode->nFeatures );
423 0 : psNode->pahFeatures[psNode->nFeatures-1] = hFeature;
424 :
425 0 : return ;
426 : }
427 :
428 :
429 : /************************************************************************/
430 : /* CPLQuadTreeNodeAddFeatureAlg2() */
431 : /************************************************************************/
432 :
433 0 : static void CPLQuadTreeNodeAddFeatureAlg2( CPLQuadTree *hQuadTree,
434 : QuadTreeNode *psNode,
435 : void* hFeature,
436 : const CPLRectObj* pRect,
437 : int nMaxDepth)
438 : {
439 : int i;
440 :
441 : /* -------------------------------------------------------------------- */
442 : /* If there are apSubNodes, then consider whether this object */
443 : /* will fit in them. */
444 : /* -------------------------------------------------------------------- */
445 0 : if( nMaxDepth > 1 && psNode->nNumSubNodes > 0 )
446 : {
447 0 : for(i=0; i<psNode->nNumSubNodes; i++ )
448 : {
449 0 : if( CPL_RectContained(pRect, &psNode->apSubNode[i]->rect))
450 : {
451 : CPLQuadTreeNodeAddFeatureAlg2( hQuadTree, psNode->apSubNode[i],
452 0 : hFeature, pRect, nMaxDepth-1);
453 0 : return;
454 : }
455 : }
456 : }
457 :
458 : /* -------------------------------------------------------------------- */
459 : /* Otherwise, consider creating four apSubNodes if could fit into */
460 : /* them, and adding to the appropriate apSubNode. */
461 : /* -------------------------------------------------------------------- */
462 0 : else if( nMaxDepth > 1 && psNode->nNumSubNodes == 0 )
463 : {
464 : CPLRectObj half1, half2, quad1, quad2, quad3, quad4;
465 :
466 0 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &psNode->rect, &half1, &half2);
467 0 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half1, &quad1, &quad2);
468 0 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half2, &quad3, &quad4);
469 :
470 0 : if(CPL_RectContained(pRect, &quad1) ||
471 : CPL_RectContained(pRect, &quad2) ||
472 : CPL_RectContained(pRect, &quad3) ||
473 : CPL_RectContained(pRect, &quad4))
474 : {
475 0 : psNode->nNumSubNodes = 4;
476 0 : psNode->apSubNode[0] = CPLQuadTreeNodeCreate(&quad1);
477 0 : psNode->apSubNode[1] = CPLQuadTreeNodeCreate(&quad2);
478 0 : psNode->apSubNode[2] = CPLQuadTreeNodeCreate(&quad3);
479 0 : psNode->apSubNode[3] = CPLQuadTreeNodeCreate(&quad4);
480 :
481 : /* recurse back on this psNode now that it has apSubNodes */
482 0 : CPLQuadTreeNodeAddFeatureAlg2(hQuadTree, psNode, hFeature, pRect, nMaxDepth);
483 0 : return;
484 : }
485 : }
486 :
487 : /* -------------------------------------------------------------------- */
488 : /* If none of that worked, just add it to this psNodes list. */
489 : /* -------------------------------------------------------------------- */
490 0 : psNode->nFeatures++;
491 :
492 : psNode->pahFeatures =
493 : (void**) CPLRealloc( psNode->pahFeatures,
494 0 : sizeof(void*) * psNode->nFeatures );
495 0 : psNode->pahFeatures[psNode->nFeatures-1] = hFeature;
496 : }
497 :
498 :
499 : /************************************************************************/
500 : /* CPLQuadTreeAddFeatureInternal() */
501 : /************************************************************************/
502 :
503 0 : static void CPLQuadTreeAddFeatureInternal(CPLQuadTree *hQuadTree,
504 : void* hFeature,
505 : const CPLRectObj *pRect)
506 : {
507 0 : if (hQuadTree->nMaxDepth == 0)
508 : {
509 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, hQuadTree->psRoot,
510 0 : hFeature, pRect);
511 : }
512 : else
513 : {
514 : CPLQuadTreeNodeAddFeatureAlg2(hQuadTree, hQuadTree->psRoot,
515 0 : hFeature, pRect, hQuadTree->nMaxDepth);
516 : }
517 0 : }
518 :
519 : /************************************************************************/
520 : /* CPLQuadTreeCollectFeatures() */
521 : /************************************************************************/
522 :
523 0 : static void CPLQuadTreeCollectFeatures(const CPLQuadTree *hQuadTree,
524 : const QuadTreeNode *psNode,
525 : const CPLRectObj* pAoi,
526 : int* pnFeatureCount,
527 : int* pnMaxFeatures,
528 : void*** pppFeatureList)
529 : {
530 : int i;
531 :
532 : /* -------------------------------------------------------------------- */
533 : /* Does this psNode overlap the area of interest at all? If not, */
534 : /* return without adding to the list at all. */
535 : /* -------------------------------------------------------------------- */
536 0 : if(!CPL_RectOverlap(&psNode->rect, pAoi))
537 0 : return;
538 :
539 : /* -------------------------------------------------------------------- */
540 : /* Grow the list to hold the features on this psNode. */
541 : /* -------------------------------------------------------------------- */
542 0 : if( *pnFeatureCount + psNode->nFeatures > *pnMaxFeatures )
543 : {
544 0 : *pnMaxFeatures = (*pnFeatureCount + psNode->nFeatures) * 2 + 20;
545 : *pppFeatureList = (void**)
546 0 : CPLRealloc(*pppFeatureList,sizeof(void*) * *pnMaxFeatures);
547 : }
548 :
549 : /* -------------------------------------------------------------------- */
550 : /* Add the local features to the list. */
551 : /* -------------------------------------------------------------------- */
552 0 : for(i=0; i<psNode->nFeatures; i++)
553 : {
554 : CPLRectObj bounds;
555 0 : hQuadTree->pfnGetBounds(psNode->pahFeatures[i], &bounds);
556 0 : if (CPL_RectOverlap(&bounds, pAoi))
557 0 : (*pppFeatureList)[(*pnFeatureCount)++] = psNode->pahFeatures[i];
558 : }
559 :
560 : /* -------------------------------------------------------------------- */
561 : /* Recurse to subnodes if they exist. */
562 : /* -------------------------------------------------------------------- */
563 0 : for(i=0; i<psNode->nNumSubNodes; i++)
564 : {
565 0 : if(psNode->apSubNode[i])
566 0 : CPLQuadTreeCollectFeatures(hQuadTree, psNode->apSubNode[i], pAoi,
567 0 : pnFeatureCount, pnMaxFeatures, pppFeatureList);
568 : }
569 : }
570 :
571 : /************************************************************************/
572 : /* CPLQuadTreeSearch() */
573 : /************************************************************************/
574 :
575 : /**
576 : * Returns all the elements inserted whose bounding box intersects the
577 : * provided area of interest
578 : *
579 : * @param hQuadTree the quad tree
580 : * @param pAoi the pointer to the area of interest
581 : * @param pnFeatureCount the user data provided to the function.
582 : *
583 : * @return an array of features that must be freed with CPLFree
584 : */
585 :
586 0 : void** CPLQuadTreeSearch(const CPLQuadTree *hQuadTree,
587 : const CPLRectObj* pAoi,
588 : int* pnFeatureCount)
589 : {
590 0 : void** ppFeatureList = NULL;
591 0 : int nMaxFeatures = 0;
592 0 : int nFeatureCount = 0;
593 :
594 0 : CPLAssert(hQuadTree);
595 0 : CPLAssert(pAoi);
596 :
597 0 : if (pnFeatureCount == NULL)
598 0 : pnFeatureCount = &nFeatureCount;
599 :
600 0 : *pnFeatureCount = 0;
601 : CPLQuadTreeCollectFeatures(hQuadTree, hQuadTree->psRoot, pAoi,
602 0 : pnFeatureCount, &nMaxFeatures, &ppFeatureList);
603 :
604 0 : return(ppFeatureList);
605 : }
606 :
607 : /************************************************************************/
608 : /* CPLQuadTreeNodeForeach() */
609 : /************************************************************************/
610 :
611 0 : static int CPLQuadTreeNodeForeach(const QuadTreeNode *psNode,
612 : CPLQuadTreeForeachFunc pfnForeach,
613 : void* pUserData)
614 : {
615 : int i;
616 0 : for(i=0; i<psNode->nNumSubNodes; i++ )
617 : {
618 0 : if (CPLQuadTreeNodeForeach(psNode->apSubNode[i], pfnForeach, pUserData) == FALSE)
619 0 : return FALSE;
620 : }
621 :
622 0 : for(i=0; i<psNode->nFeatures; i++)
623 : {
624 0 : if (pfnForeach(psNode->pahFeatures[i], pUserData) == FALSE)
625 0 : return FALSE;
626 : }
627 :
628 0 : return TRUE;
629 : }
630 :
631 : /************************************************************************/
632 : /* CPLQuadTreeForeach() */
633 : /************************************************************************/
634 :
635 : /**
636 : * Walk through the quadtree and runs the provided function on all the
637 : * elements
638 : *
639 : * This function is provided with the user_data argument of pfnForeach.
640 : * It must return TRUE to go on the walk through the hash set, or FALSE to
641 : * make it stop.
642 : *
643 : * Note : the structure of the quadtree must *NOT* be modified during the
644 : * walk.
645 : *
646 : * @param hQuadTree the quad tree
647 : * @param pfnForeach the function called on each element.
648 : * @param pUserData the user data provided to the function.
649 : */
650 :
651 0 : void CPLQuadTreeForeach(const CPLQuadTree *hQuadTree,
652 : CPLQuadTreeForeachFunc pfnForeach,
653 : void* pUserData)
654 : {
655 0 : CPLAssert(hQuadTree);
656 0 : CPLAssert(pfnForeach);
657 0 : CPLQuadTreeNodeForeach(hQuadTree->psRoot, pfnForeach, pUserData);
658 0 : }
659 :
660 : /************************************************************************/
661 : /* CPLQuadTreeDumpNode() */
662 : /************************************************************************/
663 :
664 0 : static void CPLQuadTreeDumpNode(const QuadTreeNode *psNode,
665 : int nIndentLevel,
666 : CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc,
667 : void* pUserData)
668 : {
669 : int i;
670 : int count;
671 0 : if (psNode->nNumSubNodes)
672 : {
673 0 : for(count=nIndentLevel;--count>=0;)
674 0 : printf(" ");
675 0 : printf("SubhQuadTrees :\n");
676 0 : for(i=0; i<psNode->nNumSubNodes; i++ )
677 : {
678 0 : for(count=nIndentLevel+1;--count>=0;)
679 0 : printf(" ");
680 0 : printf("SubhQuadTree %d :\n", i+1);
681 0 : CPLQuadTreeDumpNode(psNode->apSubNode[i], nIndentLevel + 2,
682 0 : pfnDumpFeatureFunc, pUserData);
683 : }
684 : }
685 0 : if (psNode->nFeatures)
686 : {
687 0 : for(count=nIndentLevel;--count>=0;)
688 0 : printf(" ");
689 0 : printf("Leaves (%d):\n", psNode->nFeatures);
690 0 : for(i=0; i<psNode->nFeatures; i++)
691 : {
692 0 : if (pfnDumpFeatureFunc)
693 0 : pfnDumpFeatureFunc(psNode->pahFeatures[i], nIndentLevel + 2,
694 0 : pUserData);
695 : else
696 : {
697 0 : for(count=nIndentLevel + 1;--count>=0;)
698 0 : printf(" ");
699 0 : printf("%p\n", psNode->pahFeatures[i]);
700 : }
701 : }
702 : }
703 0 : }
704 :
705 : /************************************************************************/
706 : /* CPLQuadTreeDump() */
707 : /************************************************************************/
708 :
709 0 : void CPLQuadTreeDump(const CPLQuadTree *hQuadTree,
710 : CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc,
711 : void* pUserData)
712 : {
713 0 : CPLQuadTreeDumpNode(hQuadTree->psRoot, 0, pfnDumpFeatureFunc, pUserData);
714 0 : }
715 :
716 : /************************************************************************/
717 : /* CPLQuadTreeGetStatsNode() */
718 : /************************************************************************/
719 :
720 : static
721 0 : void CPLQuadTreeGetStatsNode(const QuadTreeNode *psNode,
722 : int nDepthLevel,
723 : int* pnNodeCount,
724 : int* pnMaxDepth,
725 : int* pnMaxBucketCapacity)
726 : {
727 : int i;
728 0 : (*pnNodeCount) ++;
729 0 : if (nDepthLevel > *pnMaxDepth)
730 0 : *pnMaxDepth = nDepthLevel;
731 0 : if (psNode->nFeatures > *pnMaxBucketCapacity)
732 0 : *pnMaxBucketCapacity = psNode->nFeatures;
733 0 : for(i=0; i<psNode->nNumSubNodes; i++ )
734 : {
735 0 : CPLQuadTreeGetStatsNode(psNode->apSubNode[i], nDepthLevel + 1,
736 0 : pnNodeCount, pnMaxDepth, pnMaxBucketCapacity);
737 : }
738 0 : }
739 :
740 :
741 : /************************************************************************/
742 : /* CPLQuadTreeGetStats() */
743 : /************************************************************************/
744 :
745 0 : void CPLQuadTreeGetStats(const CPLQuadTree *hQuadTree,
746 : int* pnFeatureCount,
747 : int* pnNodeCount,
748 : int* pnMaxDepth,
749 : int* pnMaxBucketCapacity)
750 : {
751 : int nFeatureCount, nNodeCount, nMaxDepth, nMaxBucketCapacity;
752 0 : CPLAssert(hQuadTree);
753 0 : if (pnFeatureCount == NULL)
754 0 : pnFeatureCount = &nFeatureCount;
755 0 : if (pnNodeCount == NULL)
756 0 : pnNodeCount = &nNodeCount;
757 0 : if (pnMaxDepth == NULL)
758 0 : pnMaxDepth = &nMaxDepth;
759 0 : if (pnMaxBucketCapacity == NULL)
760 0 : pnMaxBucketCapacity = &nMaxBucketCapacity;
761 :
762 0 : *pnFeatureCount = hQuadTree->nFeatures;
763 0 : *pnNodeCount = 0;
764 0 : *pnMaxDepth = 1;
765 0 : *pnMaxBucketCapacity = 0;
766 :
767 0 : CPLQuadTreeGetStatsNode(hQuadTree->psRoot, 0, pnNodeCount, pnMaxDepth, pnMaxBucketCapacity);
768 0 : }
|
