Line data Source code
1 : /******************************************************************************
2 : *
3 : * Project: CPL - Common Portability Library
4 : * Purpose: Implementation of quadtree building and searching functions.
5 : * Derived from shapelib and mapserver implementations
6 : * Author: Frank Warmerdam, warmerdam@pobox.com
7 : * Even Rouault, <even dot rouault at spatialys.com>
8 : *
9 : ******************************************************************************
10 : * Copyright (c) 1999-2008, Frank Warmerdam
11 : * Copyright (c) 2008-2014, Even Rouault <even dot rouault at spatialys.com>
12 : *
13 : * SPDX-License-Identifier: MIT
14 : ******************************************************************************
15 : */
16 :
17 : #include "cpl_port.h"
18 : #include "cpl_quad_tree.h"
19 :
20 : #include <algorithm>
21 : #include <cstdio>
22 : #include <cstring>
23 :
24 : #include "cpl_conv.h"
25 : #include "cpl_error.h"
26 :
27 : constexpr int MAX_DEFAULT_TREE_DEPTH = 12;
28 : constexpr int MAX_SUBNODES = 4;
29 :
30 : typedef struct _QuadTreeNode QuadTreeNode;
31 :
32 : struct _QuadTreeNode
33 : {
34 : /* area covered by this psNode */
35 : CPLRectObj rect;
36 :
37 : int nFeatures; /* number of shapes stored at this psNode. */
38 :
39 : int nNumSubNodes; /* number of active subnodes */
40 :
41 : void **pahFeatures; /* list of shapes stored at this psNode. */
42 : CPLRectObj *pasBounds;
43 :
44 : QuadTreeNode *apSubNode[MAX_SUBNODES];
45 : };
46 :
47 : struct _CPLQuadTree
48 : {
49 : QuadTreeNode *psRoot;
50 : CPLQuadTreeGetBoundsFunc pfnGetBounds;
51 : CPLQuadTreeGetBoundsExFunc pfnGetBoundsEx;
52 : void *pUserData;
53 : int nFeatures;
54 : int nMaxDepth;
55 : int nBucketCapacity;
56 : double dfSplitRatio;
57 : bool bForceUseOfSubNodes;
58 : };
59 :
60 : static void CPLQuadTreeAddFeatureInternal(CPLQuadTree *hQuadTree,
61 : void *hFeature,
62 : const CPLRectObj *pRect);
63 : static void CPLQuadTreeNodeDestroy(QuadTreeNode *psNode);
64 :
65 : /* -------------------------------------------------------------------- */
66 : /* If the following is 0.5, psNodes will be split in half. If it */
67 : /* is 0.6 then each apSubNode will contain 60% of the parent */
68 : /* psNode, with 20% representing overlap. This can be help to */
69 : /* prevent small objects on a boundary from shifting too high */
70 : /* up the hQuadTree. */
71 : /* -------------------------------------------------------------------- */
72 : constexpr double DEFAULT_SPLIT_RATIO = 0.55;
73 :
74 : /*
75 : ** Returns TRUE if rectangle a is contained in rectangle b
76 : */
77 2974400 : static CPL_INLINE bool CPL_RectContained(const CPLRectObj *a,
78 : const CPLRectObj *b)
79 : {
80 4669370 : return a->minx >= b->minx && a->maxx <= b->maxx && a->miny >= b->miny &&
81 4669370 : a->maxy <= b->maxy;
82 : }
83 :
84 : /*
85 : ** Returns TRUE if rectangles a and b overlap
86 : */
87 31740100 : static CPL_INLINE bool CPL_RectOverlap(const CPLRectObj *a, const CPLRectObj *b)
88 : {
89 31740100 : if (a->minx > b->maxx)
90 11036300 : return false;
91 20703800 : if (a->maxx < b->minx)
92 4437670 : return false;
93 16266100 : if (a->miny > b->maxy)
94 1929700 : return false;
95 14336400 : if (a->maxy < b->miny)
96 2108100 : return false;
97 12228300 : return true;
98 : }
99 :
100 : /************************************************************************/
101 : /* CPLQuadTreeNodeCreate() */
102 : /************************************************************************/
103 :
104 75960 : static QuadTreeNode *CPLQuadTreeNodeCreate(const CPLRectObj *pRect)
105 : {
106 : QuadTreeNode *psNode =
107 75960 : static_cast<QuadTreeNode *>(CPLMalloc(sizeof(QuadTreeNode)));
108 :
109 75960 : psNode->nFeatures = 0;
110 75960 : psNode->pahFeatures = nullptr;
111 75960 : psNode->pasBounds = nullptr;
112 :
113 75960 : psNode->nNumSubNodes = 0;
114 :
115 75960 : memcpy(&(psNode->rect), pRect, sizeof(CPLRectObj));
116 :
117 75960 : return psNode;
118 : }
119 :
120 : /************************************************************************/
121 : /* CPLQuadTreeCreate() */
122 : /************************************************************************/
123 :
124 : /**
125 : * Create a new quadtree
126 : *
127 : * @param pGlobalBounds a pointer to the global extent of all
128 : * the elements that will be inserted
129 : * @param pfnGetBounds a user provided function to get the bounding box of
130 : * the inserted elements. If it is set to NULL, then
131 : * CPLQuadTreeInsertWithBounds() must be used, and
132 : * extra memory will be used to keep features bounds in the
133 : * quad tree.
134 : *
135 : * @return a newly allocated quadtree
136 : */
137 :
138 16016 : CPLQuadTree *CPLQuadTreeCreate(const CPLRectObj *pGlobalBounds,
139 : CPLQuadTreeGetBoundsFunc pfnGetBounds)
140 : {
141 16016 : CPLAssert(pGlobalBounds);
142 :
143 : /* -------------------------------------------------------------------- */
144 : /* Allocate the hQuadTree object */
145 : /* -------------------------------------------------------------------- */
146 : CPLQuadTree *hQuadTree =
147 16016 : static_cast<CPLQuadTree *>(CPLMalloc(sizeof(CPLQuadTree)));
148 :
149 16016 : hQuadTree->nFeatures = 0;
150 16016 : hQuadTree->pfnGetBounds = pfnGetBounds;
151 16016 : hQuadTree->pfnGetBoundsEx = nullptr;
152 16016 : hQuadTree->nMaxDepth = 0;
153 16016 : hQuadTree->nBucketCapacity = 8;
154 :
155 16016 : hQuadTree->dfSplitRatio = DEFAULT_SPLIT_RATIO;
156 16016 : hQuadTree->bForceUseOfSubNodes = false;
157 :
158 : /* -------------------------------------------------------------------- */
159 : /* Allocate the psRoot psNode. */
160 : /* -------------------------------------------------------------------- */
161 16016 : hQuadTree->psRoot = CPLQuadTreeNodeCreate(pGlobalBounds);
162 :
163 16016 : hQuadTree->pUserData = nullptr;
164 :
165 16016 : return hQuadTree;
166 : }
167 :
168 : /************************************************************************/
169 : /* CPLQuadTreeCreateEx() */
170 : /************************************************************************/
171 :
172 : /**
173 : * Create a new quadtree
174 : *
175 : * @param pGlobalBounds a pointer to the global extent of all
176 : * the elements that will be inserted
177 : * @param pfnGetBoundsEx a user provided function to get the bounding box of
178 : * the inserted elements. If it is set to NULL, then
179 : * CPLQuadTreeInsertWithBounds() must be used, and
180 : * extra memory will be used to keep features bounds in the
181 : * quad tree.
182 : * @param pUserData user data passed to pfnGetBoundsEx
183 : *
184 : * @return a newly allocated quadtree
185 : */
186 :
187 4 : CPLQuadTree *CPLQuadTreeCreateEx(const CPLRectObj *pGlobalBounds,
188 : CPLQuadTreeGetBoundsExFunc pfnGetBoundsEx,
189 : void *pUserData)
190 : {
191 4 : CPLAssert(pGlobalBounds);
192 :
193 : /* -------------------------------------------------------------------- */
194 : /* Allocate the hQuadTree object */
195 : /* -------------------------------------------------------------------- */
196 : CPLQuadTree *hQuadTree =
197 4 : static_cast<CPLQuadTree *>(CPLMalloc(sizeof(CPLQuadTree)));
198 :
199 4 : hQuadTree->nFeatures = 0;
200 4 : hQuadTree->pfnGetBounds = nullptr;
201 4 : hQuadTree->pfnGetBoundsEx = pfnGetBoundsEx;
202 4 : hQuadTree->nMaxDepth = 0;
203 4 : hQuadTree->nBucketCapacity = 8;
204 :
205 4 : hQuadTree->dfSplitRatio = DEFAULT_SPLIT_RATIO;
206 4 : hQuadTree->bForceUseOfSubNodes = false;
207 :
208 : /* -------------------------------------------------------------------- */
209 : /* Allocate the psRoot psNode. */
210 : /* -------------------------------------------------------------------- */
211 4 : hQuadTree->psRoot = CPLQuadTreeNodeCreate(pGlobalBounds);
212 :
213 4 : hQuadTree->pUserData = pUserData;
214 :
215 4 : return hQuadTree;
216 : }
217 :
218 : /************************************************************************/
219 : /* CPLQuadTreeGetAdvisedMaxDepth() */
220 : /************************************************************************/
221 :
222 : /**
223 : * Returns the optimal depth of a quadtree to hold nExpectedFeatures
224 : *
225 : * @param nExpectedFeatures the expected maximum number of elements to be
226 : * inserted.
227 : *
228 : * @return the optimal depth of a quadtree to hold nExpectedFeatures
229 : */
230 :
231 125 : int CPLQuadTreeGetAdvisedMaxDepth(int nExpectedFeatures)
232 : {
233 : /* -------------------------------------------------------------------- */
234 : /* Try to select a reasonable one */
235 : /* that implies approximately 8 shapes per node. */
236 : /* -------------------------------------------------------------------- */
237 125 : int nMaxDepth = 0;
238 125 : int nMaxNodeCount = 1;
239 :
240 140 : while (nMaxNodeCount < nExpectedFeatures / 4)
241 : {
242 15 : nMaxDepth += 1;
243 15 : nMaxNodeCount = nMaxNodeCount * 2;
244 : }
245 :
246 125 : CPLDebug("CPLQuadTree", "Estimated spatial index tree depth: %d",
247 : nMaxDepth);
248 :
249 : /* NOTE: Due to problems with memory allocation for deep trees,
250 : * automatically estimated depth is limited up to 12 levels.
251 : * See Ticket #1594 for detailed discussion.
252 : */
253 125 : if (nMaxDepth > MAX_DEFAULT_TREE_DEPTH)
254 : {
255 0 : nMaxDepth = MAX_DEFAULT_TREE_DEPTH;
256 :
257 0 : CPLDebug("CPLQuadTree",
258 : "Falling back to max number of allowed index tree "
259 : "levels (%d).",
260 : MAX_DEFAULT_TREE_DEPTH);
261 : }
262 :
263 125 : return nMaxDepth;
264 : }
265 :
266 : /************************************************************************/
267 : /* CPLQuadTreeSetMaxDepth() */
268 : /************************************************************************/
269 :
270 : /**
271 : * Set the maximum depth of a quadtree. By default, quad trees have
272 : * no maximum depth, but a maximum bucket capacity.
273 : *
274 : * @param hQuadTree the quad tree
275 : * @param nMaxDepth the maximum depth allowed
276 : */
277 :
278 125 : void CPLQuadTreeSetMaxDepth(CPLQuadTree *hQuadTree, int nMaxDepth)
279 : {
280 125 : hQuadTree->nMaxDepth = nMaxDepth;
281 125 : }
282 :
283 : /************************************************************************/
284 : /* CPLQuadTreeSetBucketCapacity() */
285 : /************************************************************************/
286 :
287 : /**
288 : * Set the maximum capacity of a node of a quadtree. The default value is 8.
289 : * Note that the maximum capacity will only be honoured if the features
290 : * inserted have a point geometry. Otherwise it may be exceeded.
291 : *
292 : * @param hQuadTree the quad tree
293 : * @param nBucketCapacity the maximum capacity of a node of a quadtree
294 : */
295 :
296 1 : void CPLQuadTreeSetBucketCapacity(CPLQuadTree *hQuadTree, int nBucketCapacity)
297 : {
298 1 : if (nBucketCapacity > 0)
299 1 : hQuadTree->nBucketCapacity = nBucketCapacity;
300 1 : }
301 :
302 : /************************************************************************/
303 : /* CPLQuadTreeForceUseOfSubNodes() */
304 : /************************************************************************/
305 :
306 : /**
307 : * Force the quadtree to insert as much as possible a feature whose bbox
308 : * spread over multiple subnodes into those subnodes, rather than in the
309 : * list of features attached to the node.
310 : *
311 : * @param hQuadTree the quad tree
312 : */
313 :
314 4 : void CPLQuadTreeForceUseOfSubNodes(CPLQuadTree *hQuadTree)
315 : {
316 4 : hQuadTree->bForceUseOfSubNodes = true;
317 4 : }
318 :
319 : /************************************************************************/
320 : /* CPLQuadTreeInsert() */
321 : /************************************************************************/
322 :
323 : /**
324 : * Insert a feature into a quadtree
325 : *
326 : * @param hQuadTree the quad tree
327 : * @param hFeature the feature to insert
328 : */
329 :
330 98212 : void CPLQuadTreeInsert(CPLQuadTree *hQuadTree, void *hFeature)
331 : {
332 98212 : if (hQuadTree->pfnGetBounds == nullptr &&
333 1062 : hQuadTree->pfnGetBoundsEx == nullptr)
334 : {
335 0 : CPLError(CE_Failure, CPLE_AppDefined,
336 : "hQuadTree->pfnGetBounds == NULL");
337 0 : return;
338 : }
339 98212 : hQuadTree->nFeatures++;
340 : CPLRectObj bounds;
341 98212 : if (hQuadTree->pfnGetBoundsEx)
342 1062 : hQuadTree->pfnGetBoundsEx(hFeature, hQuadTree->pUserData, &bounds);
343 : else
344 97150 : hQuadTree->pfnGetBounds(hFeature, &bounds);
345 98212 : CPLQuadTreeAddFeatureInternal(hQuadTree, hFeature, &bounds);
346 : }
347 :
348 : /************************************************************************/
349 : /* CPLQuadTreeInsertWithBounds() */
350 : /************************************************************************/
351 :
352 : /**
353 : * Insert a feature into a quadtree
354 : *
355 : * @param hQuadTree the quad tree
356 : * @param hFeature the feature to insert
357 : * @param psBounds bounds of the feature
358 : */
359 97380 : void CPLQuadTreeInsertWithBounds(CPLQuadTree *hQuadTree, void *hFeature,
360 : const CPLRectObj *psBounds)
361 : {
362 97380 : hQuadTree->nFeatures++;
363 97380 : CPLQuadTreeAddFeatureInternal(hQuadTree, hFeature, psBounds);
364 97380 : }
365 :
366 : /************************************************************************/
367 : /* CPLQuadTreeRemove() */
368 : /************************************************************************/
369 :
370 35118 : static bool CPLQuadTreeRemoveInternal(QuadTreeNode *psNode, void *hFeature,
371 : const CPLRectObj *psBounds)
372 : {
373 35118 : bool bRemoved = false;
374 :
375 494930 : for (int i = 0; i < psNode->nFeatures; i++)
376 : {
377 462819 : if (psNode->pahFeatures[i] == hFeature)
378 : {
379 3007 : if (i < psNode->nFeatures - 1)
380 : {
381 2627 : memmove(psNode->pahFeatures + i, psNode->pahFeatures + i + 1,
382 2627 : (psNode->nFeatures - 1 - i) * sizeof(void *));
383 2627 : if (psNode->pasBounds)
384 : {
385 2627 : memmove(psNode->pasBounds + i, psNode->pasBounds + i + 1,
386 2627 : (psNode->nFeatures - 1 - i) * sizeof(CPLRectObj));
387 : }
388 : }
389 3007 : bRemoved = true;
390 3007 : psNode->nFeatures--;
391 3007 : break;
392 : }
393 : }
394 35118 : if (psNode->nFeatures == 0 && psNode->pahFeatures != nullptr)
395 : {
396 348 : CPLFree(psNode->pahFeatures);
397 348 : CPLFree(psNode->pasBounds);
398 348 : psNode->pahFeatures = nullptr;
399 348 : psNode->pasBounds = nullptr;
400 : }
401 :
402 : /* -------------------------------------------------------------------- */
403 : /* Recurse to subnodes if they exist. */
404 : /* -------------------------------------------------------------------- */
405 97154 : for (int i = 0; i < psNode->nNumSubNodes; i++)
406 : {
407 124072 : if (psNode->apSubNode[i] &&
408 62036 : CPL_RectOverlap(&(psNode->apSubNode[i]->rect), psBounds))
409 : {
410 32111 : bRemoved |= CPLQuadTreeRemoveInternal(psNode->apSubNode[i],
411 : hFeature, psBounds);
412 : }
413 : }
414 :
415 : /* -------------------------------------------------------------------- */
416 : /* Only collapse the subnodes when all of them are empty leaves: */
417 : /* the node then becomes a leaf again and may re-split on a later */
418 : /* insertion. Destroying an individual empty subnode would leave a */
419 : /* quadrant hole: features falling in it can neither descend nor */
420 : /* trigger a split (splitting requires a node without subnodes), */
421 : /* so they would pile up in this node's bucket forever, degrading */
422 : /* every search overlapping it to a linear scan. */
423 : /* -------------------------------------------------------------------- */
424 35118 : if (psNode->nNumSubNodes != 0)
425 : {
426 15509 : bool bAllSubNodesEmpty = true;
427 23429 : for (int i = 0; i < psNode->nNumSubNodes; i++)
428 : {
429 23348 : if (psNode->apSubNode[i] &&
430 23348 : (psNode->apSubNode[i]->nFeatures != 0 ||
431 10459 : psNode->apSubNode[i]->nNumSubNodes != 0))
432 : {
433 15428 : bAllSubNodesEmpty = false;
434 15428 : break;
435 : }
436 : }
437 15509 : if (bAllSubNodesEmpty)
438 : {
439 405 : for (int i = 0; i < psNode->nNumSubNodes; i++)
440 : {
441 324 : if (psNode->apSubNode[i])
442 324 : CPLQuadTreeNodeDestroy(psNode->apSubNode[i]);
443 324 : psNode->apSubNode[i] = nullptr;
444 : }
445 81 : psNode->nNumSubNodes = 0;
446 : }
447 : }
448 :
449 35118 : return bRemoved;
450 : }
451 :
452 : /**
453 : * Remove a feature from a quadtree.
454 : *
455 : * Currently the quadtree is not re-balanced.
456 : *
457 : * @param hQuadTree the quad tree
458 : * @param hFeature the feature to remove
459 : * @param psBounds bounds of the feature (or NULL if pfnGetBounds has been
460 : * filled)
461 : */
462 3007 : void CPLQuadTreeRemove(CPLQuadTree *hQuadTree, void *hFeature,
463 : const CPLRectObj *psBounds)
464 : {
465 3007 : if (psBounds == nullptr && hQuadTree->pfnGetBounds == nullptr &&
466 0 : hQuadTree->pfnGetBoundsEx == nullptr)
467 : {
468 0 : CPLError(CE_Failure, CPLE_AppDefined,
469 : "hQuadTree->pfnGetBounds == NULL");
470 0 : return;
471 : }
472 : CPLRectObj bounds; // keep variable in this outer scope
473 3007 : if (psBounds == nullptr)
474 : {
475 0 : if (hQuadTree->pfnGetBoundsEx)
476 0 : hQuadTree->pfnGetBoundsEx(hFeature, hQuadTree->pUserData, &bounds);
477 : else
478 0 : hQuadTree->pfnGetBounds(hFeature, &bounds);
479 0 : psBounds = &bounds;
480 : }
481 3007 : if (CPLQuadTreeRemoveInternal(hQuadTree->psRoot, hFeature, psBounds))
482 : {
483 3007 : hQuadTree->nFeatures--;
484 : }
485 : }
486 :
487 : /************************************************************************/
488 : /* CPLQuadTreeNodeDestroy() */
489 : /************************************************************************/
490 :
491 75960 : static void CPLQuadTreeNodeDestroy(QuadTreeNode *psNode)
492 : {
493 135576 : for (int i = 0; i < psNode->nNumSubNodes; i++)
494 : {
495 59616 : if (psNode->apSubNode[i])
496 59616 : CPLQuadTreeNodeDestroy(psNode->apSubNode[i]);
497 : }
498 :
499 75960 : if (psNode->pahFeatures)
500 : {
501 56507 : CPLFree(psNode->pahFeatures);
502 56507 : CPLFree(psNode->pasBounds);
503 : }
504 :
505 75960 : CPLFree(psNode);
506 75960 : }
507 :
508 : /************************************************************************/
509 : /* CPLQuadTreeDestroy() */
510 : /************************************************************************/
511 :
512 : /**
513 : * Destroy a quadtree
514 : *
515 : * @param hQuadTree the quad tree to destroy
516 : */
517 :
518 16020 : void CPLQuadTreeDestroy(CPLQuadTree *hQuadTree)
519 : {
520 16020 : CPLAssert(hQuadTree);
521 16020 : CPLQuadTreeNodeDestroy(hQuadTree->psRoot);
522 16020 : CPLFree(hQuadTree);
523 16020 : }
524 :
525 : /************************************************************************/
526 : /* CPLQuadTreeSplitBounds() */
527 : /************************************************************************/
528 :
529 60681 : static void CPLQuadTreeSplitBounds(double dfSplitRatio, const CPLRectObj *in,
530 : CPLRectObj *out1, CPLRectObj *out2)
531 : {
532 : /* -------------------------------------------------------------------- */
533 : /* The output bounds will be very similar to the input bounds, */
534 : /* so just copy over to start. */
535 : /* -------------------------------------------------------------------- */
536 60681 : memcpy(out1, in, sizeof(CPLRectObj));
537 60681 : memcpy(out2, in, sizeof(CPLRectObj));
538 :
539 : /* -------------------------------------------------------------------- */
540 : /* Split in X direction. */
541 : /* -------------------------------------------------------------------- */
542 60681 : if ((in->maxx - in->minx) > (in->maxy - in->miny))
543 : {
544 28880 : const double range = in->maxx - in->minx;
545 :
546 28880 : out1->maxx = in->minx + range * dfSplitRatio;
547 28880 : out2->minx = in->maxx - range * dfSplitRatio;
548 : }
549 :
550 : /* -------------------------------------------------------------------- */
551 : /* Otherwise split in Y direction. */
552 : /* -------------------------------------------------------------------- */
553 : else
554 : {
555 31801 : const double range = in->maxy - in->miny;
556 :
557 31801 : out1->maxy = in->miny + range * dfSplitRatio;
558 31801 : out2->miny = in->maxy - range * dfSplitRatio;
559 : }
560 60681 : }
561 :
562 : /************************************************************************/
563 : /* CPLQuadTreeNodeAddFeatureAlg1() */
564 : /************************************************************************/
565 :
566 1372150 : static void CPLQuadTreeNodeAddFeatureAlg1(CPLQuadTree *hQuadTree,
567 : QuadTreeNode *psNode, void *hFeature,
568 : const CPLRectObj *pRect)
569 : {
570 1372150 : if (psNode->nNumSubNodes == 0)
571 : {
572 : // If we have reached the max bucket capacity, try to insert
573 : // in a subnode if possible.
574 304673 : if (psNode->nFeatures >= hQuadTree->nBucketCapacity)
575 : {
576 20225 : CPLRectObj half1 = {0.0, 0.0, 0.0, 0.0};
577 20225 : CPLRectObj half2 = {0.0, 0.0, 0.0, 0.0};
578 20225 : CPLRectObj quad1 = {0.0, 0.0, 0.0, 0.0};
579 20225 : CPLRectObj quad2 = {0.0, 0.0, 0.0, 0.0};
580 20225 : CPLRectObj quad3 = {0.0, 0.0, 0.0, 0.0};
581 20225 : CPLRectObj quad4 = {0.0, 0.0, 0.0, 0.0};
582 :
583 20225 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &psNode->rect,
584 : &half1, &half2);
585 20225 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half1, &quad1,
586 : &quad2);
587 20225 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half2, &quad3,
588 : &quad4);
589 :
590 60675 : if (memcmp(&psNode->rect, &quad1, sizeof(CPLRectObj)) != 0 &&
591 20225 : memcmp(&psNode->rect, &quad2, sizeof(CPLRectObj)) != 0 &&
592 20225 : memcmp(&psNode->rect, &quad3, sizeof(CPLRectObj)) != 0 &&
593 60675 : memcmp(&psNode->rect, &quad4, sizeof(CPLRectObj)) != 0 &&
594 40342 : (hQuadTree->bForceUseOfSubNodes ||
595 38511 : CPL_RectContained(pRect, &quad1) ||
596 33510 : CPL_RectContained(pRect, &quad2) ||
597 26362 : CPL_RectContained(pRect, &quad3) ||
598 11246 : CPL_RectContained(pRect, &quad4)))
599 : {
600 14983 : psNode->nNumSubNodes = 4;
601 14983 : psNode->apSubNode[0] = CPLQuadTreeNodeCreate(&quad1);
602 14983 : psNode->apSubNode[1] = CPLQuadTreeNodeCreate(&quad2);
603 14983 : psNode->apSubNode[2] = CPLQuadTreeNodeCreate(&quad3);
604 14983 : psNode->apSubNode[3] = CPLQuadTreeNodeCreate(&quad4);
605 :
606 14983 : const int oldNumFeatures = psNode->nFeatures;
607 14983 : void **oldFeatures = psNode->pahFeatures;
608 14983 : CPLRectObj *pasOldBounds = psNode->pasBounds;
609 14983 : psNode->nFeatures = 0;
610 14983 : psNode->pahFeatures = nullptr;
611 14983 : psNode->pasBounds = nullptr;
612 :
613 : // Redispatch existing pahFeatures in apSubNodes.
614 137092 : for (int i = 0; i < oldNumFeatures; i++)
615 : {
616 122109 : if (hQuadTree->pfnGetBounds == nullptr &&
617 65245 : hQuadTree->pfnGetBoundsEx == nullptr)
618 64381 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, psNode,
619 64381 : oldFeatures[i],
620 64381 : &pasOldBounds[i]);
621 : else
622 : {
623 : CPLRectObj bounds;
624 57728 : if (hQuadTree->pfnGetBoundsEx)
625 864 : hQuadTree->pfnGetBoundsEx(
626 864 : oldFeatures[i], hQuadTree->pUserData, &bounds);
627 : else
628 56864 : hQuadTree->pfnGetBounds(oldFeatures[i], &bounds);
629 57728 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, psNode,
630 57728 : oldFeatures[i], &bounds);
631 : }
632 : }
633 :
634 14983 : CPLFree(oldFeatures);
635 14983 : CPLFree(pasOldBounds);
636 :
637 : /* recurse back on this psNode now that it has apSubNodes */
638 14983 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, psNode, hFeature,
639 : pRect);
640 14983 : return;
641 : }
642 : }
643 : }
644 : else
645 : {
646 : /* --------------------------------------------------------------------
647 : */
648 : /* If there are apSubNodes, then consider whether this object */
649 : /* will fit in them. */
650 : /* --------------------------------------------------------------------
651 : */
652 2938320 : for (int i = 0; i < psNode->nNumSubNodes; i++)
653 : {
654 2909530 : if (CPL_RectContained(pRect, &psNode->apSubNode[i]->rect))
655 : {
656 1038680 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, psNode->apSubNode[i],
657 : hFeature, pRect);
658 1038680 : return;
659 : }
660 : }
661 28793 : if (hQuadTree->bForceUseOfSubNodes)
662 : {
663 : bool overlaps[4];
664 576 : bool overlapAll = true;
665 2880 : for (int i = 0; i < psNode->nNumSubNodes; i++)
666 : {
667 2304 : overlaps[i] =
668 2304 : CPL_RectOverlap(pRect, &psNode->apSubNode[i]->rect);
669 2304 : if (!overlaps[i])
670 1142 : overlapAll = false;
671 : }
672 576 : if (!overlapAll)
673 : {
674 2440 : for (int i = 0; i < psNode->nNumSubNodes; i++)
675 : {
676 1952 : if (overlaps[i])
677 : {
678 : CPLRectObj intersection;
679 810 : intersection.minx = std::max(
680 810 : pRect->minx, psNode->apSubNode[i]->rect.minx);
681 810 : intersection.miny = std::max(
682 810 : pRect->miny, psNode->apSubNode[i]->rect.miny);
683 810 : intersection.maxx = std::min(
684 810 : pRect->maxx, psNode->apSubNode[i]->rect.maxx);
685 810 : intersection.maxy = std::min(
686 810 : pRect->maxy, psNode->apSubNode[i]->rect.maxy);
687 810 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree,
688 : psNode->apSubNode[i],
689 : hFeature, &intersection);
690 : }
691 : }
692 488 : return;
693 : }
694 : }
695 : }
696 :
697 : /* -------------------------------------------------------------------- */
698 : /* If none of that worked, just add it to this psNodes list. */
699 : /* -------------------------------------------------------------------- */
700 317995 : psNode->nFeatures++;
701 :
702 317995 : if (psNode->nFeatures == 1)
703 : {
704 71834 : CPLAssert(psNode->pahFeatures == nullptr);
705 71834 : psNode->pahFeatures = static_cast<void **>(
706 71834 : CPLMalloc(hQuadTree->nBucketCapacity * sizeof(void *)));
707 71834 : if (hQuadTree->pfnGetBounds == nullptr &&
708 30467 : hQuadTree->pfnGetBoundsEx == nullptr)
709 29961 : psNode->pasBounds = static_cast<CPLRectObj *>(
710 29961 : CPLMalloc(hQuadTree->nBucketCapacity * sizeof(CPLRectObj)));
711 : }
712 246161 : else if (psNode->nFeatures > hQuadTree->nBucketCapacity)
713 : {
714 16772 : psNode->pahFeatures = static_cast<void **>(CPLRealloc(
715 8386 : psNode->pahFeatures, sizeof(void *) * psNode->nFeatures));
716 8386 : if (hQuadTree->pfnGetBounds == nullptr &&
717 8292 : hQuadTree->pfnGetBoundsEx == nullptr)
718 8292 : psNode->pasBounds = static_cast<CPLRectObj *>(CPLRealloc(
719 8292 : psNode->pasBounds, sizeof(CPLRectObj) * psNode->nFeatures));
720 : }
721 317995 : psNode->pahFeatures[psNode->nFeatures - 1] = hFeature;
722 317995 : if (hQuadTree->pfnGetBounds == nullptr &&
723 163981 : hQuadTree->pfnGetBoundsEx == nullptr)
724 161733 : psNode->pasBounds[psNode->nFeatures - 1] = *pRect;
725 :
726 317995 : return;
727 : }
728 :
729 : /************************************************************************/
730 : /* CPLQuadTreeNodeAddFeatureAlg2() */
731 : /************************************************************************/
732 :
733 32 : static void CPLQuadTreeNodeAddFeatureAlg2(CPLQuadTree *hQuadTree,
734 : QuadTreeNode *psNode, void *hFeature,
735 : const CPLRectObj *pRect,
736 : int nMaxDepth)
737 : {
738 : /* -------------------------------------------------------------------- */
739 : /* If there are apSubNodes, then consider whether this object */
740 : /* will fit in them. */
741 : /* -------------------------------------------------------------------- */
742 32 : if (nMaxDepth > 1 && psNode->nNumSubNodes > 0)
743 : {
744 2 : for (int i = 0; i < psNode->nNumSubNodes; i++)
745 : {
746 2 : if (CPL_RectContained(pRect, &psNode->apSubNode[i]->rect))
747 : {
748 2 : CPLQuadTreeNodeAddFeatureAlg2(hQuadTree, psNode->apSubNode[i],
749 : hFeature, pRect, nMaxDepth - 1);
750 2 : return;
751 : }
752 0 : }
753 : }
754 :
755 : /* -------------------------------------------------------------------- */
756 : /* Otherwise, consider creating four apSubNodes if could fit into */
757 : /* them, and adding to the appropriate apSubNode. */
758 : /* -------------------------------------------------------------------- */
759 30 : else if (nMaxDepth > 1 && psNode->nNumSubNodes == 0)
760 : {
761 : CPLRectObj half1, half2, quad1, quad2, quad3, quad4;
762 :
763 2 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &psNode->rect, &half1,
764 : &half2);
765 2 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half1, &quad1, &quad2);
766 2 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half2, &quad3, &quad4);
767 :
768 6 : if (memcmp(&psNode->rect, &quad1, sizeof(CPLRectObj)) != 0 &&
769 2 : memcmp(&psNode->rect, &quad2, sizeof(CPLRectObj)) != 0 &&
770 2 : memcmp(&psNode->rect, &quad3, sizeof(CPLRectObj)) != 0 &&
771 6 : memcmp(&psNode->rect, &quad4, sizeof(CPLRectObj)) != 0 &&
772 2 : (CPL_RectContained(pRect, &quad1) ||
773 0 : CPL_RectContained(pRect, &quad2) ||
774 0 : CPL_RectContained(pRect, &quad3) ||
775 0 : CPL_RectContained(pRect, &quad4)))
776 : {
777 2 : psNode->nNumSubNodes = 4;
778 2 : psNode->apSubNode[0] = CPLQuadTreeNodeCreate(&quad1);
779 2 : psNode->apSubNode[1] = CPLQuadTreeNodeCreate(&quad2);
780 2 : psNode->apSubNode[2] = CPLQuadTreeNodeCreate(&quad3);
781 2 : psNode->apSubNode[3] = CPLQuadTreeNodeCreate(&quad4);
782 :
783 : /* recurse back on this psNode now that it has apSubNodes */
784 2 : CPLQuadTreeNodeAddFeatureAlg2(hQuadTree, psNode, hFeature, pRect,
785 : nMaxDepth);
786 2 : return;
787 : }
788 : }
789 :
790 : /* -------------------------------------------------------------------- */
791 : /* If none of that worked, just add it to this psNodes list. */
792 : /* -------------------------------------------------------------------- */
793 28 : psNode->nFeatures++;
794 :
795 28 : psNode->pahFeatures = static_cast<void **>(
796 28 : CPLRealloc(psNode->pahFeatures, sizeof(void *) * psNode->nFeatures));
797 28 : if (hQuadTree->pfnGetBounds == nullptr &&
798 28 : hQuadTree->pfnGetBoundsEx == nullptr)
799 : {
800 28 : psNode->pasBounds = static_cast<CPLRectObj *>(CPLRealloc(
801 28 : psNode->pasBounds, sizeof(CPLRectObj) * psNode->nFeatures));
802 : }
803 28 : psNode->pahFeatures[psNode->nFeatures - 1] = hFeature;
804 28 : if (hQuadTree->pfnGetBounds == nullptr &&
805 28 : hQuadTree->pfnGetBoundsEx == nullptr)
806 : {
807 28 : psNode->pasBounds[psNode->nFeatures - 1] = *pRect;
808 : }
809 : }
810 :
811 : /************************************************************************/
812 : /* CPLQuadTreeAddFeatureInternal() */
813 : /************************************************************************/
814 :
815 195592 : static void CPLQuadTreeAddFeatureInternal(CPLQuadTree *hQuadTree,
816 : void *hFeature,
817 : const CPLRectObj *pRect)
818 : {
819 195592 : if (hQuadTree->nMaxDepth == 0)
820 : {
821 195564 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, hQuadTree->psRoot, hFeature,
822 : pRect);
823 : }
824 : else
825 : {
826 28 : CPLQuadTreeNodeAddFeatureAlg2(hQuadTree, hQuadTree->psRoot, hFeature,
827 : pRect, hQuadTree->nMaxDepth);
828 : }
829 195592 : }
830 :
831 : /************************************************************************/
832 : /* CPLQuadTreeCollectFeatures() */
833 : /************************************************************************/
834 :
835 13129300 : static void CPLQuadTreeCollectFeatures(const CPLQuadTree *hQuadTree,
836 : const QuadTreeNode *psNode,
837 : const CPLRectObj *pAoi,
838 : int *pnFeatureCount, int *pnMaxFeatures,
839 : void ***pppFeatureList)
840 : {
841 : /* -------------------------------------------------------------------- */
842 : /* Does this psNode overlap the area of interest at all? If not, */
843 : /* return without adding to the list at all. */
844 : /* -------------------------------------------------------------------- */
845 13129300 : if (!CPL_RectOverlap(&psNode->rect, pAoi))
846 7115530 : return;
847 :
848 : /* -------------------------------------------------------------------- */
849 : /* Grow the list to hold the features on this psNode. */
850 : /* -------------------------------------------------------------------- */
851 6017920 : if (*pnFeatureCount + psNode->nFeatures > *pnMaxFeatures)
852 : {
853 : // TODO(schwehr): Symbolic constant.
854 2543710 : *pnMaxFeatures = (*pnFeatureCount + psNode->nFeatures) * 2 + 20;
855 2543740 : *pppFeatureList = static_cast<void **>(
856 2543710 : CPLRealloc(*pppFeatureList, sizeof(void *) * *pnMaxFeatures));
857 : }
858 :
859 : /* -------------------------------------------------------------------- */
860 : /* Add the local features to the list. */
861 : /* -------------------------------------------------------------------- */
862 24739600 : for (int i = 0; i < psNode->nFeatures; i++)
863 : {
864 18690300 : if (hQuadTree->pfnGetBounds == nullptr &&
865 12444100 : hQuadTree->pfnGetBoundsEx == nullptr)
866 : {
867 12443900 : if (CPL_RectOverlap(&psNode->pasBounds[i], pAoi))
868 805389 : (*pppFeatureList)[(*pnFeatureCount)++] = psNode->pahFeatures[i];
869 : }
870 : else
871 : {
872 : CPLRectObj bounds;
873 6246420 : if (hQuadTree->pfnGetBoundsEx)
874 188 : hQuadTree->pfnGetBoundsEx(psNode->pahFeatures[i],
875 188 : hQuadTree->pUserData, &bounds);
876 : else
877 6246230 : hQuadTree->pfnGetBounds(psNode->pahFeatures[i], &bounds);
878 :
879 6281740 : if (CPL_RectOverlap(&bounds, pAoi))
880 5577300 : (*pppFeatureList)[(*pnFeatureCount)++] = psNode->pahFeatures[i];
881 : }
882 : }
883 :
884 : /* -------------------------------------------------------------------- */
885 : /* Recurse to subnodes if they exist. */
886 : /* -------------------------------------------------------------------- */
887 16392600 : for (int i = 0; i < psNode->nNumSubNodes; i++)
888 : {
889 10340200 : if (psNode->apSubNode[i])
890 10343000 : CPLQuadTreeCollectFeatures(hQuadTree, psNode->apSubNode[i], pAoi,
891 : pnFeatureCount, pnMaxFeatures,
892 : pppFeatureList);
893 : }
894 : }
895 :
896 : /************************************************************************/
897 : /* CPLQuadTreeSearch() */
898 : /************************************************************************/
899 :
900 : /**
901 : * Returns all the elements inserted whose bounding box intersects the
902 : * provided area of interest
903 : *
904 : * @param hQuadTree the quad tree
905 : * @param pAoi the pointer to the area of interest
906 : * @param pnFeatureCount the user data provided to the function.
907 : *
908 : * @return an array of features that must be freed with CPLFree
909 : */
910 :
911 2793850 : void **CPLQuadTreeSearch(const CPLQuadTree *hQuadTree, const CPLRectObj *pAoi,
912 : int *pnFeatureCount)
913 : {
914 2793850 : CPLAssert(hQuadTree);
915 2793850 : CPLAssert(pAoi);
916 :
917 2793850 : int nFeatureCount = 0;
918 2793850 : if (pnFeatureCount == nullptr)
919 0 : pnFeatureCount = &nFeatureCount;
920 :
921 2793850 : *pnFeatureCount = 0;
922 :
923 2793850 : int nMaxFeatures = 0;
924 2793850 : void **ppFeatureList = nullptr;
925 2793850 : CPLQuadTreeCollectFeatures(hQuadTree, hQuadTree->psRoot, pAoi,
926 : pnFeatureCount, &nMaxFeatures, &ppFeatureList);
927 :
928 2803400 : return ppFeatureList;
929 : }
930 :
931 : /************************************************************************/
932 : /* CPLQuadTreeHasMatch() */
933 : /************************************************************************/
934 :
935 430 : static bool CPLQuadTreeHasMatch(const CPLQuadTree *hQuadTree,
936 : const QuadTreeNode *psNode,
937 : const CPLRectObj *pAoi)
938 : {
939 : /* -------------------------------------------------------------------- */
940 : /* Does this psNode overlap the area of interest at all? */
941 : /* -------------------------------------------------------------------- */
942 430 : if (!CPL_RectOverlap(&psNode->rect, pAoi))
943 0 : return false;
944 :
945 : /* -------------------------------------------------------------------- */
946 : /* Check the local features. */
947 : /* -------------------------------------------------------------------- */
948 10877 : for (int i = 0; i < psNode->nFeatures; i++)
949 : {
950 10455 : if (hQuadTree->pfnGetBounds == nullptr &&
951 10455 : hQuadTree->pfnGetBoundsEx == nullptr)
952 : {
953 10455 : if (CPL_RectOverlap(&psNode->pasBounds[i], pAoi))
954 8 : return true;
955 : }
956 : else
957 : {
958 : CPLRectObj bounds;
959 0 : if (hQuadTree->pfnGetBoundsEx)
960 0 : hQuadTree->pfnGetBoundsEx(psNode->pahFeatures[i],
961 0 : hQuadTree->pUserData, &bounds);
962 : else
963 0 : hQuadTree->pfnGetBounds(psNode->pahFeatures[i], &bounds);
964 :
965 0 : if (CPL_RectOverlap(&bounds, pAoi))
966 0 : return true;
967 : }
968 : }
969 :
970 : /* -------------------------------------------------------------------- */
971 : /* Recurse to subnodes if they exist. */
972 : /* -------------------------------------------------------------------- */
973 422 : for (int i = 0; i < psNode->nNumSubNodes; i++)
974 : {
975 0 : if (psNode->apSubNode[i])
976 : {
977 0 : if (CPLQuadTreeHasMatch(hQuadTree, psNode->apSubNode[i], pAoi))
978 : {
979 0 : return true;
980 : }
981 : }
982 : }
983 :
984 422 : return false;
985 : }
986 :
987 : /**
988 : * Returns whether the quadtree has at least one element whose bounding box
989 : * intersects the provided area of interest
990 : *
991 : * @param hQuadTree the quad tree
992 : * @param pAoi the pointer to the area of interest
993 : */
994 :
995 430 : bool CPLQuadTreeHasMatch(const CPLQuadTree *hQuadTree, const CPLRectObj *pAoi)
996 : {
997 430 : CPLAssert(hQuadTree);
998 430 : CPLAssert(pAoi);
999 :
1000 430 : return CPLQuadTreeHasMatch(hQuadTree, hQuadTree->psRoot, pAoi);
1001 : }
1002 :
1003 : /************************************************************************/
1004 : /* CPLQuadTreeNodeForeach() */
1005 : /************************************************************************/
1006 :
1007 25 : static bool CPLQuadTreeNodeForeach(const QuadTreeNode *psNode,
1008 : CPLQuadTreeForeachFunc pfnForeach,
1009 : void *pUserData)
1010 : {
1011 49 : for (int i = 0; i < psNode->nNumSubNodes; i++)
1012 : {
1013 24 : if (!CPLQuadTreeNodeForeach(psNode->apSubNode[i], pfnForeach,
1014 : pUserData))
1015 0 : return false;
1016 : }
1017 :
1018 50 : for (int i = 0; i < psNode->nFeatures; i++)
1019 : {
1020 25 : if (pfnForeach(psNode->pahFeatures[i], pUserData) == FALSE)
1021 0 : return false;
1022 : }
1023 :
1024 25 : return true;
1025 : }
1026 :
1027 : /************************************************************************/
1028 : /* CPLQuadTreeForeach() */
1029 : /************************************************************************/
1030 :
1031 : /**
1032 : * Walk through the quadtree and runs the provided function on all the
1033 : * elements
1034 : *
1035 : * This function is provided with the user_data argument of pfnForeach.
1036 : * It must return TRUE to go on the walk through the hash set, or FALSE to
1037 : * make it stop.
1038 : *
1039 : * Note : the structure of the quadtree must *NOT* be modified during the
1040 : * walk.
1041 : *
1042 : * @param hQuadTree the quad tree
1043 : * @param pfnForeach the function called on each element.
1044 : * @param pUserData the user data provided to the function.
1045 : */
1046 :
1047 1 : void CPLQuadTreeForeach(const CPLQuadTree *hQuadTree,
1048 : CPLQuadTreeForeachFunc pfnForeach, void *pUserData)
1049 : {
1050 1 : CPLAssert(hQuadTree);
1051 1 : CPLAssert(pfnForeach);
1052 1 : CPLQuadTreeNodeForeach(hQuadTree->psRoot, pfnForeach, pUserData);
1053 1 : }
1054 :
1055 : /************************************************************************/
1056 : /* CPLQuadTreeDumpNode() */
1057 : /************************************************************************/
1058 :
1059 0 : static void CPLQuadTreeDumpNode(const QuadTreeNode *psNode, int nIndentLevel,
1060 : CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc,
1061 : void *pUserData)
1062 : {
1063 0 : if (psNode->nNumSubNodes)
1064 : {
1065 0 : for (int count = nIndentLevel; --count >= 0;)
1066 : {
1067 0 : printf(" "); /*ok*/
1068 : }
1069 0 : printf("SubhQuadTrees :\n"); /*ok*/
1070 0 : for (int i = 0; i < psNode->nNumSubNodes; i++)
1071 : {
1072 0 : for (int count = nIndentLevel + 1; --count >= 0;)
1073 : {
1074 0 : printf(" "); /*ok*/
1075 : }
1076 0 : printf("SubhQuadTree %d :\n", i + 1); /*ok*/
1077 0 : CPLQuadTreeDumpNode(psNode->apSubNode[i], nIndentLevel + 2,
1078 : pfnDumpFeatureFunc, pUserData);
1079 : }
1080 : }
1081 0 : if (psNode->nFeatures)
1082 : {
1083 0 : for (int count = nIndentLevel; --count >= 0;)
1084 0 : printf(" "); /*ok*/
1085 0 : printf("Leaves (%d):\n", psNode->nFeatures); /*ok*/
1086 0 : for (int i = 0; i < psNode->nFeatures; i++)
1087 : {
1088 0 : if (pfnDumpFeatureFunc)
1089 : {
1090 0 : pfnDumpFeatureFunc(psNode->pahFeatures[i], nIndentLevel + 2,
1091 : pUserData);
1092 : }
1093 : else
1094 : {
1095 0 : for (int count = nIndentLevel + 1; --count >= 0;)
1096 : {
1097 0 : printf(" "); /*ok*/
1098 : }
1099 0 : printf("%p\n", psNode->pahFeatures[i]); /*ok*/
1100 : }
1101 : }
1102 : }
1103 0 : }
1104 :
1105 : /************************************************************************/
1106 : /* CPLQuadTreeDump() */
1107 : /************************************************************************/
1108 :
1109 : /** Dump quad tree */
1110 0 : void CPLQuadTreeDump(const CPLQuadTree *hQuadTree,
1111 : CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc,
1112 : void *pUserData)
1113 : {
1114 0 : CPLQuadTreeDumpNode(hQuadTree->psRoot, 0, pfnDumpFeatureFunc, pUserData);
1115 0 : }
1116 :
1117 : /************************************************************************/
1118 : /* CPLQuadTreeGetStatsNode() */
1119 : /************************************************************************/
1120 :
1121 341 : static void CPLQuadTreeGetStatsNode(const QuadTreeNode *psNode, int nDepthLevel,
1122 : int *pnNodeCount, int *pnMaxDepth,
1123 : int *pnMaxBucketCapacity)
1124 : {
1125 341 : (*pnNodeCount)++;
1126 341 : if (nDepthLevel > *pnMaxDepth)
1127 4 : *pnMaxDepth = nDepthLevel;
1128 341 : if (psNode->nFeatures > *pnMaxBucketCapacity)
1129 3 : *pnMaxBucketCapacity = psNode->nFeatures;
1130 :
1131 681 : for (int i = 0; i < psNode->nNumSubNodes; i++)
1132 : {
1133 340 : CPLQuadTreeGetStatsNode(psNode->apSubNode[i], nDepthLevel + 1,
1134 : pnNodeCount, pnMaxDepth, pnMaxBucketCapacity);
1135 : }
1136 341 : }
1137 :
1138 : /************************************************************************/
1139 : /* CPLQuadTreeGetStats() */
1140 : /************************************************************************/
1141 :
1142 : /** Get stats */
1143 1 : void CPLQuadTreeGetStats(const CPLQuadTree *hQuadTree, int *pnFeatureCount,
1144 : int *pnNodeCount, int *pnMaxDepth,
1145 : int *pnMaxBucketCapacity)
1146 : {
1147 1 : CPLAssert(hQuadTree);
1148 :
1149 1 : int nFeatureCount = 0;
1150 1 : if (pnFeatureCount == nullptr)
1151 0 : pnFeatureCount = &nFeatureCount;
1152 1 : int nNodeCount = 0;
1153 1 : if (pnNodeCount == nullptr)
1154 0 : pnNodeCount = &nNodeCount;
1155 1 : int nMaxDepth = 0;
1156 1 : if (pnMaxDepth == nullptr)
1157 0 : pnMaxDepth = &nMaxDepth;
1158 1 : int nMaxBucketCapacity = 0;
1159 1 : if (pnMaxBucketCapacity == nullptr)
1160 0 : pnMaxBucketCapacity = &nMaxBucketCapacity;
1161 :
1162 1 : *pnFeatureCount = hQuadTree->nFeatures;
1163 1 : *pnNodeCount = 0;
1164 1 : *pnMaxDepth = 1;
1165 1 : *pnMaxBucketCapacity = 0;
1166 :
1167 1 : CPLQuadTreeGetStatsNode(hQuadTree->psRoot, 0, pnNodeCount, pnMaxDepth,
1168 : pnMaxBucketCapacity);
1169 :
1170 : // TODO(schwehr): If any of the pointers were set to local vars,
1171 : // do they need to be reset to a nullptr?
1172 1 : }
|
