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 2194240 : static CPL_INLINE bool CPL_RectContained(const CPLRectObj *a,
78 : const CPLRectObj *b)
79 : {
80 3426080 : return a->minx >= b->minx && a->maxx <= b->maxx && a->miny >= b->miny &&
81 3426080 : a->maxy <= b->maxy;
82 : }
83 :
84 : /*
85 : ** Returns TRUE if rectangles a and b overlap
86 : */
87 22232800 : static CPL_INLINE bool CPL_RectOverlap(const CPLRectObj *a, const CPLRectObj *b)
88 : {
89 22232800 : if (a->minx > b->maxx)
90 7154990 : return false;
91 15077900 : if (a->maxx < b->minx)
92 6509810 : return false;
93 8568040 : if (a->miny > b->maxy)
94 1877520 : return false;
95 6690520 : if (a->maxy < b->miny)
96 1839890 : return false;
97 4850630 : return true;
98 : }
99 :
100 : /************************************************************************/
101 : /* CPLQuadTreeNodeCreate() */
102 : /************************************************************************/
103 :
104 42762 : static QuadTreeNode *CPLQuadTreeNodeCreate(const CPLRectObj *pRect)
105 : {
106 : QuadTreeNode *psNode =
107 42762 : static_cast<QuadTreeNode *>(CPLMalloc(sizeof(QuadTreeNode)));
108 :
109 42762 : psNode->nFeatures = 0;
110 42762 : psNode->pahFeatures = nullptr;
111 42762 : psNode->pasBounds = nullptr;
112 :
113 42762 : psNode->nNumSubNodes = 0;
114 :
115 42762 : memcpy(&(psNode->rect), pRect, sizeof(CPLRectObj));
116 :
117 42762 : 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 310 : CPLQuadTree *CPLQuadTreeCreate(const CPLRectObj *pGlobalBounds,
139 : CPLQuadTreeGetBoundsFunc pfnGetBounds)
140 : {
141 310 : CPLAssert(pGlobalBounds);
142 :
143 : /* -------------------------------------------------------------------- */
144 : /* Allocate the hQuadTree object */
145 : /* -------------------------------------------------------------------- */
146 : CPLQuadTree *hQuadTree =
147 310 : static_cast<CPLQuadTree *>(CPLMalloc(sizeof(CPLQuadTree)));
148 :
149 310 : hQuadTree->nFeatures = 0;
150 310 : hQuadTree->pfnGetBounds = pfnGetBounds;
151 310 : hQuadTree->pfnGetBoundsEx = nullptr;
152 310 : hQuadTree->nMaxDepth = 0;
153 310 : hQuadTree->nBucketCapacity = 8;
154 :
155 310 : hQuadTree->dfSplitRatio = DEFAULT_SPLIT_RATIO;
156 310 : hQuadTree->bForceUseOfSubNodes = false;
157 :
158 : /* -------------------------------------------------------------------- */
159 : /* Allocate the psRoot psNode. */
160 : /* -------------------------------------------------------------------- */
161 310 : hQuadTree->psRoot = CPLQuadTreeNodeCreate(pGlobalBounds);
162 :
163 310 : hQuadTree->pUserData = nullptr;
164 :
165 310 : 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 123 : int CPLQuadTreeGetAdvisedMaxDepth(int nExpectedFeatures)
232 : {
233 : /* -------------------------------------------------------------------- */
234 : /* Try to select a reasonable one */
235 : /* that implies approximately 8 shapes per node. */
236 : /* -------------------------------------------------------------------- */
237 123 : int nMaxDepth = 0;
238 123 : int nMaxNodeCount = 1;
239 :
240 138 : while (nMaxNodeCount < nExpectedFeatures / 4)
241 : {
242 15 : nMaxDepth += 1;
243 15 : nMaxNodeCount = nMaxNodeCount * 2;
244 : }
245 :
246 123 : 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 123 : 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 123 : 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 123 : void CPLQuadTreeSetMaxDepth(CPLQuadTree *hQuadTree, int nMaxDepth)
279 : {
280 123 : hQuadTree->nMaxDepth = nMaxDepth;
281 123 : }
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 29118 : void CPLQuadTreeInsert(CPLQuadTree *hQuadTree, void *hFeature)
331 : {
332 29118 : 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 29118 : hQuadTree->nFeatures++;
340 : CPLRectObj bounds;
341 29118 : if (hQuadTree->pfnGetBoundsEx)
342 1062 : hQuadTree->pfnGetBoundsEx(hFeature, hQuadTree->pUserData, &bounds);
343 : else
344 28056 : hQuadTree->pfnGetBounds(hFeature, &bounds);
345 29118 : 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 94988 : void CPLQuadTreeInsertWithBounds(CPLQuadTree *hQuadTree, void *hFeature,
360 : const CPLRectObj *psBounds)
361 : {
362 94988 : hQuadTree->nFeatures++;
363 94988 : CPLQuadTreeAddFeatureInternal(hQuadTree, hFeature, psBounds);
364 94988 : }
365 :
366 : /************************************************************************/
367 : /* CPLQuadTreeRemove() */
368 : /************************************************************************/
369 :
370 24011 : static bool CPLQuadTreeRemoveInternal(QuadTreeNode *psNode, void *hFeature,
371 : const CPLRectObj *psBounds)
372 : {
373 24011 : bool bRemoved = false;
374 :
375 480605 : for (int i = 0; i < psNode->nFeatures; i++)
376 : {
377 458617 : if (psNode->pahFeatures[i] == hFeature)
378 : {
379 2023 : if (i < psNode->nFeatures - 1)
380 : {
381 1901 : memmove(psNode->pahFeatures + i, psNode->pahFeatures + i + 1,
382 1901 : (psNode->nFeatures - 1 - i) * sizeof(void *));
383 1901 : if (psNode->pasBounds)
384 : {
385 1901 : memmove(psNode->pasBounds + i, psNode->pasBounds + i + 1,
386 1901 : (psNode->nFeatures - 1 - i) * sizeof(CPLRectObj));
387 : }
388 : }
389 2023 : bRemoved = true;
390 2023 : psNode->nFeatures--;
391 2023 : break;
392 : }
393 : }
394 24011 : if (psNode->nFeatures == 0 && psNode->pahFeatures != nullptr)
395 : {
396 122 : CPLFree(psNode->pahFeatures);
397 122 : CPLFree(psNode->pasBounds);
398 122 : psNode->pahFeatures = nullptr;
399 122 : psNode->pasBounds = nullptr;
400 : }
401 :
402 : /* -------------------------------------------------------------------- */
403 : /* Recurse to subnodes if they exist. */
404 : /* -------------------------------------------------------------------- */
405 62797 : for (int i = 0; i < psNode->nNumSubNodes; i++)
406 : {
407 77572 : if (psNode->apSubNode[i] &&
408 38786 : CPL_RectOverlap(&(psNode->apSubNode[i]->rect), psBounds))
409 : {
410 21988 : bRemoved |= CPLQuadTreeRemoveInternal(psNode->apSubNode[i],
411 : hFeature, psBounds);
412 :
413 21988 : if (psNode->apSubNode[i]->nFeatures == 0 &&
414 646 : psNode->apSubNode[i]->nNumSubNodes == 0)
415 : {
416 120 : CPLQuadTreeNodeDestroy(psNode->apSubNode[i]);
417 120 : if (i < psNode->nNumSubNodes - 1)
418 : {
419 : #ifdef CSA_BUILD
420 : for (int j = 0; j < psNode->nNumSubNodes - 1 - i; ++j)
421 : psNode->apSubNode[i + j] = psNode->apSubNode[i + j + 1];
422 : #else
423 77 : memmove(psNode->apSubNode + i, psNode->apSubNode + i + 1,
424 77 : (psNode->nNumSubNodes - 1 - i) *
425 : sizeof(QuadTreeNode *));
426 : #endif
427 : }
428 120 : i--;
429 120 : psNode->nNumSubNodes--;
430 : }
431 : }
432 : }
433 :
434 24011 : return bRemoved;
435 : }
436 :
437 : /**
438 : * Remove a feature from a quadtree.
439 : *
440 : * Currently the quadtree is not re-balanced.
441 : *
442 : * @param hQuadTree the quad tree
443 : * @param hFeature the feature to remove
444 : * @param psBounds bounds of the feature (or NULL if pfnGetBounds has been
445 : * filled)
446 : */
447 2023 : void CPLQuadTreeRemove(CPLQuadTree *hQuadTree, void *hFeature,
448 : const CPLRectObj *psBounds)
449 : {
450 2023 : if (psBounds == nullptr && hQuadTree->pfnGetBounds == nullptr &&
451 0 : hQuadTree->pfnGetBoundsEx == nullptr)
452 : {
453 0 : CPLError(CE_Failure, CPLE_AppDefined,
454 : "hQuadTree->pfnGetBounds == NULL");
455 0 : return;
456 : }
457 : CPLRectObj bounds; // keep variable in this outer scope
458 2023 : if (psBounds == nullptr)
459 : {
460 0 : if (hQuadTree->pfnGetBoundsEx)
461 0 : hQuadTree->pfnGetBoundsEx(hFeature, hQuadTree->pUserData, &bounds);
462 : else
463 0 : hQuadTree->pfnGetBounds(hFeature, &bounds);
464 0 : psBounds = &bounds;
465 : }
466 2023 : if (CPLQuadTreeRemoveInternal(hQuadTree->psRoot, hFeature, psBounds))
467 : {
468 2023 : hQuadTree->nFeatures--;
469 : }
470 : }
471 :
472 : /************************************************************************/
473 : /* CPLQuadTreeNodeDestroy() */
474 : /************************************************************************/
475 :
476 42762 : static void CPLQuadTreeNodeDestroy(QuadTreeNode *psNode)
477 : {
478 85090 : for (int i = 0; i < psNode->nNumSubNodes; i++)
479 : {
480 42328 : if (psNode->apSubNode[i])
481 42328 : CPLQuadTreeNodeDestroy(psNode->apSubNode[i]);
482 : }
483 :
484 42762 : if (psNode->pahFeatures)
485 : {
486 29865 : CPLFree(psNode->pahFeatures);
487 29865 : CPLFree(psNode->pasBounds);
488 : }
489 :
490 42762 : CPLFree(psNode);
491 42762 : }
492 :
493 : /************************************************************************/
494 : /* CPLQuadTreeDestroy() */
495 : /************************************************************************/
496 :
497 : /**
498 : * Destroy a quadtree
499 : *
500 : * @param hQuadTree the quad tree to destroy
501 : */
502 :
503 314 : void CPLQuadTreeDestroy(CPLQuadTree *hQuadTree)
504 : {
505 314 : CPLAssert(hQuadTree);
506 314 : CPLQuadTreeNodeDestroy(hQuadTree->psRoot);
507 314 : CPLFree(hQuadTree);
508 314 : }
509 :
510 : /************************************************************************/
511 : /* CPLQuadTreeSplitBounds() */
512 : /************************************************************************/
513 :
514 47439 : static void CPLQuadTreeSplitBounds(double dfSplitRatio, const CPLRectObj *in,
515 : CPLRectObj *out1, CPLRectObj *out2)
516 : {
517 : /* -------------------------------------------------------------------- */
518 : /* The output bounds will be very similar to the input bounds, */
519 : /* so just copy over to start. */
520 : /* -------------------------------------------------------------------- */
521 47439 : memcpy(out1, in, sizeof(CPLRectObj));
522 47439 : memcpy(out2, in, sizeof(CPLRectObj));
523 :
524 : /* -------------------------------------------------------------------- */
525 : /* Split in X direction. */
526 : /* -------------------------------------------------------------------- */
527 47439 : if ((in->maxx - in->minx) > (in->maxy - in->miny))
528 : {
529 20369 : const double range = in->maxx - in->minx;
530 :
531 20369 : out1->maxx = in->minx + range * dfSplitRatio;
532 20369 : out2->minx = in->maxx - range * dfSplitRatio;
533 : }
534 :
535 : /* -------------------------------------------------------------------- */
536 : /* Otherwise split in Y direction. */
537 : /* -------------------------------------------------------------------- */
538 : else
539 : {
540 27070 : const double range = in->maxy - in->miny;
541 :
542 27070 : out1->maxy = in->miny + range * dfSplitRatio;
543 27070 : out2->miny = in->maxy - range * dfSplitRatio;
544 : }
545 47439 : }
546 :
547 : /************************************************************************/
548 : /* CPLQuadTreeNodeAddFeatureAlg1() */
549 : /************************************************************************/
550 :
551 985922 : static void CPLQuadTreeNodeAddFeatureAlg1(CPLQuadTree *hQuadTree,
552 : QuadTreeNode *psNode, void *hFeature,
553 : const CPLRectObj *pRect)
554 : {
555 985922 : if (psNode->nNumSubNodes == 0)
556 : {
557 : // If we have reached the max bucket capacity, try to insert
558 : // in a subnode if possible.
559 195634 : if (psNode->nFeatures >= hQuadTree->nBucketCapacity)
560 : {
561 15811 : CPLRectObj half1 = {0.0, 0.0, 0.0, 0.0};
562 15811 : CPLRectObj half2 = {0.0, 0.0, 0.0, 0.0};
563 15811 : CPLRectObj quad1 = {0.0, 0.0, 0.0, 0.0};
564 15811 : CPLRectObj quad2 = {0.0, 0.0, 0.0, 0.0};
565 15811 : CPLRectObj quad3 = {0.0, 0.0, 0.0, 0.0};
566 15811 : CPLRectObj quad4 = {0.0, 0.0, 0.0, 0.0};
567 :
568 15811 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &psNode->rect,
569 : &half1, &half2);
570 15811 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half1, &quad1,
571 : &quad2);
572 15811 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half2, &quad3,
573 : &quad4);
574 :
575 47433 : if (memcmp(&psNode->rect, &quad1, sizeof(CPLRectObj)) != 0 &&
576 15811 : memcmp(&psNode->rect, &quad2, sizeof(CPLRectObj)) != 0 &&
577 15811 : memcmp(&psNode->rect, &quad3, sizeof(CPLRectObj)) != 0 &&
578 47433 : memcmp(&psNode->rect, &quad4, sizeof(CPLRectObj)) != 0 &&
579 31514 : (hQuadTree->bForceUseOfSubNodes ||
580 30327 : CPL_RectContained(pRect, &quad1) ||
581 27029 : CPL_RectContained(pRect, &quad2) ||
582 21917 : CPL_RectContained(pRect, &quad3) ||
583 9512 : CPL_RectContained(pRect, &quad4)))
584 : {
585 10610 : psNode->nNumSubNodes = 4;
586 10610 : psNode->apSubNode[0] = CPLQuadTreeNodeCreate(&quad1);
587 10610 : psNode->apSubNode[1] = CPLQuadTreeNodeCreate(&quad2);
588 10610 : psNode->apSubNode[2] = CPLQuadTreeNodeCreate(&quad3);
589 10610 : psNode->apSubNode[3] = CPLQuadTreeNodeCreate(&quad4);
590 :
591 10610 : const int oldNumFeatures = psNode->nFeatures;
592 10610 : void **oldFeatures = psNode->pahFeatures;
593 10610 : CPLRectObj *pasOldBounds = psNode->pasBounds;
594 10610 : psNode->nFeatures = 0;
595 10610 : psNode->pahFeatures = nullptr;
596 10610 : psNode->pasBounds = nullptr;
597 :
598 : // Redispatch existing pahFeatures in apSubNodes.
599 97783 : for (int i = 0; i < oldNumFeatures; i++)
600 : {
601 87173 : if (hQuadTree->pfnGetBounds == nullptr &&
602 64017 : hQuadTree->pfnGetBoundsEx == nullptr)
603 63153 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, psNode,
604 63153 : oldFeatures[i],
605 63153 : &pasOldBounds[i]);
606 : else
607 : {
608 : CPLRectObj bounds;
609 24020 : if (hQuadTree->pfnGetBoundsEx)
610 864 : hQuadTree->pfnGetBoundsEx(
611 864 : oldFeatures[i], hQuadTree->pUserData, &bounds);
612 : else
613 23156 : hQuadTree->pfnGetBounds(oldFeatures[i], &bounds);
614 24020 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, psNode,
615 24020 : oldFeatures[i], &bounds);
616 : }
617 : }
618 :
619 10610 : CPLFree(oldFeatures);
620 10610 : CPLFree(pasOldBounds);
621 :
622 : /* recurse back on this psNode now that it has apSubNodes */
623 10610 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, psNode, hFeature,
624 : pRect);
625 10610 : return;
626 : }
627 : }
628 : }
629 : else
630 : {
631 : /* --------------------------------------------------------------------
632 : */
633 : /* If there are apSubNodes, then consider whether this object */
634 : /* will fit in them. */
635 : /* --------------------------------------------------------------------
636 : */
637 2169020 : for (int i = 0; i < psNode->nNumSubNodes; i++)
638 : {
639 2141990 : if (CPL_RectContained(pRect, &psNode->apSubNode[i]->rect))
640 : {
641 763251 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, psNode->apSubNode[i],
642 : hFeature, pRect);
643 763251 : return;
644 : }
645 : }
646 27037 : if (hQuadTree->bForceUseOfSubNodes)
647 : {
648 : bool overlaps[4];
649 576 : bool overlapAll = true;
650 2880 : for (int i = 0; i < psNode->nNumSubNodes; i++)
651 : {
652 2304 : overlaps[i] =
653 2304 : CPL_RectOverlap(pRect, &psNode->apSubNode[i]->rect);
654 2304 : if (!overlaps[i])
655 1142 : overlapAll = false;
656 : }
657 576 : if (!overlapAll)
658 : {
659 2440 : for (int i = 0; i < psNode->nNumSubNodes; i++)
660 : {
661 1952 : if (overlaps[i])
662 : {
663 : CPLRectObj intersection;
664 810 : intersection.minx = std::max(
665 810 : pRect->minx, psNode->apSubNode[i]->rect.minx);
666 810 : intersection.miny = std::max(
667 810 : pRect->miny, psNode->apSubNode[i]->rect.miny);
668 810 : intersection.maxx = std::min(
669 810 : pRect->maxx, psNode->apSubNode[i]->rect.maxx);
670 810 : intersection.maxy = std::min(
671 810 : pRect->maxy, psNode->apSubNode[i]->rect.maxy);
672 810 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree,
673 : psNode->apSubNode[i],
674 : hFeature, &intersection);
675 : }
676 : }
677 488 : return;
678 : }
679 : }
680 : }
681 :
682 : /* -------------------------------------------------------------------- */
683 : /* If none of that worked, just add it to this psNodes list. */
684 : /* -------------------------------------------------------------------- */
685 211573 : psNode->nFeatures++;
686 :
687 211573 : if (psNode->nFeatures == 1)
688 : {
689 40593 : CPLAssert(psNode->pahFeatures == nullptr);
690 40593 : psNode->pahFeatures = static_cast<void **>(
691 40593 : CPLMalloc(hQuadTree->nBucketCapacity * sizeof(void *)));
692 40593 : if (hQuadTree->pfnGetBounds == nullptr &&
693 29605 : hQuadTree->pfnGetBoundsEx == nullptr)
694 29099 : psNode->pasBounds = static_cast<CPLRectObj *>(
695 29099 : CPLMalloc(hQuadTree->nBucketCapacity * sizeof(CPLRectObj)));
696 : }
697 170980 : else if (psNode->nFeatures > hQuadTree->nBucketCapacity)
698 : {
699 17024 : psNode->pahFeatures = static_cast<void **>(CPLRealloc(
700 8512 : psNode->pahFeatures, sizeof(void *) * psNode->nFeatures));
701 8512 : if (hQuadTree->pfnGetBounds == nullptr &&
702 8512 : hQuadTree->pfnGetBoundsEx == nullptr)
703 8512 : psNode->pasBounds = static_cast<CPLRectObj *>(CPLRealloc(
704 8512 : psNode->pasBounds, sizeof(CPLRectObj) * psNode->nFeatures));
705 : }
706 211573 : psNode->pahFeatures[psNode->nFeatures - 1] = hFeature;
707 211573 : if (hQuadTree->pfnGetBounds == nullptr &&
708 160361 : hQuadTree->pfnGetBoundsEx == nullptr)
709 158113 : psNode->pasBounds[psNode->nFeatures - 1] = *pRect;
710 :
711 211573 : return;
712 : }
713 :
714 : /************************************************************************/
715 : /* CPLQuadTreeNodeAddFeatureAlg2() */
716 : /************************************************************************/
717 :
718 32 : static void CPLQuadTreeNodeAddFeatureAlg2(CPLQuadTree *hQuadTree,
719 : QuadTreeNode *psNode, void *hFeature,
720 : const CPLRectObj *pRect,
721 : int nMaxDepth)
722 : {
723 : /* -------------------------------------------------------------------- */
724 : /* If there are apSubNodes, then consider whether this object */
725 : /* will fit in them. */
726 : /* -------------------------------------------------------------------- */
727 32 : if (nMaxDepth > 1 && psNode->nNumSubNodes > 0)
728 : {
729 2 : for (int i = 0; i < psNode->nNumSubNodes; i++)
730 : {
731 2 : if (CPL_RectContained(pRect, &psNode->apSubNode[i]->rect))
732 : {
733 2 : CPLQuadTreeNodeAddFeatureAlg2(hQuadTree, psNode->apSubNode[i],
734 : hFeature, pRect, nMaxDepth - 1);
735 2 : return;
736 : }
737 0 : }
738 : }
739 :
740 : /* -------------------------------------------------------------------- */
741 : /* Otherwise, consider creating four apSubNodes if could fit into */
742 : /* them, and adding to the appropriate apSubNode. */
743 : /* -------------------------------------------------------------------- */
744 30 : else if (nMaxDepth > 1 && psNode->nNumSubNodes == 0)
745 : {
746 : CPLRectObj half1, half2, quad1, quad2, quad3, quad4;
747 :
748 2 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &psNode->rect, &half1,
749 : &half2);
750 2 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half1, &quad1, &quad2);
751 2 : CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half2, &quad3, &quad4);
752 :
753 6 : if (memcmp(&psNode->rect, &quad1, sizeof(CPLRectObj)) != 0 &&
754 2 : memcmp(&psNode->rect, &quad2, sizeof(CPLRectObj)) != 0 &&
755 2 : memcmp(&psNode->rect, &quad3, sizeof(CPLRectObj)) != 0 &&
756 6 : memcmp(&psNode->rect, &quad4, sizeof(CPLRectObj)) != 0 &&
757 2 : (CPL_RectContained(pRect, &quad1) ||
758 0 : CPL_RectContained(pRect, &quad2) ||
759 0 : CPL_RectContained(pRect, &quad3) ||
760 0 : CPL_RectContained(pRect, &quad4)))
761 : {
762 2 : psNode->nNumSubNodes = 4;
763 2 : psNode->apSubNode[0] = CPLQuadTreeNodeCreate(&quad1);
764 2 : psNode->apSubNode[1] = CPLQuadTreeNodeCreate(&quad2);
765 2 : psNode->apSubNode[2] = CPLQuadTreeNodeCreate(&quad3);
766 2 : psNode->apSubNode[3] = CPLQuadTreeNodeCreate(&quad4);
767 :
768 : /* recurse back on this psNode now that it has apSubNodes */
769 2 : CPLQuadTreeNodeAddFeatureAlg2(hQuadTree, psNode, hFeature, pRect,
770 : nMaxDepth);
771 2 : return;
772 : }
773 : }
774 :
775 : /* -------------------------------------------------------------------- */
776 : /* If none of that worked, just add it to this psNodes list. */
777 : /* -------------------------------------------------------------------- */
778 28 : psNode->nFeatures++;
779 :
780 28 : psNode->pahFeatures = static_cast<void **>(
781 28 : CPLRealloc(psNode->pahFeatures, sizeof(void *) * psNode->nFeatures));
782 28 : if (hQuadTree->pfnGetBounds == nullptr &&
783 28 : hQuadTree->pfnGetBoundsEx == nullptr)
784 : {
785 28 : psNode->pasBounds = static_cast<CPLRectObj *>(CPLRealloc(
786 28 : psNode->pasBounds, sizeof(CPLRectObj) * psNode->nFeatures));
787 : }
788 28 : psNode->pahFeatures[psNode->nFeatures - 1] = hFeature;
789 28 : if (hQuadTree->pfnGetBounds == nullptr &&
790 28 : hQuadTree->pfnGetBoundsEx == nullptr)
791 : {
792 28 : psNode->pasBounds[psNode->nFeatures - 1] = *pRect;
793 : }
794 : }
795 :
796 : /************************************************************************/
797 : /* CPLQuadTreeAddFeatureInternal() */
798 : /************************************************************************/
799 :
800 124106 : static void CPLQuadTreeAddFeatureInternal(CPLQuadTree *hQuadTree,
801 : void *hFeature,
802 : const CPLRectObj *pRect)
803 : {
804 124106 : if (hQuadTree->nMaxDepth == 0)
805 : {
806 124078 : CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, hQuadTree->psRoot, hFeature,
807 : pRect);
808 : }
809 : else
810 : {
811 28 : CPLQuadTreeNodeAddFeatureAlg2(hQuadTree, hQuadTree->psRoot, hFeature,
812 : pRect, hQuadTree->nMaxDepth);
813 : }
814 124106 : }
815 :
816 : /************************************************************************/
817 : /* CPLQuadTreeCollectFeatures() */
818 : /************************************************************************/
819 :
820 10514500 : static void CPLQuadTreeCollectFeatures(const CPLQuadTree *hQuadTree,
821 : const QuadTreeNode *psNode,
822 : const CPLRectObj *pAoi,
823 : int *pnFeatureCount, int *pnMaxFeatures,
824 : void ***pppFeatureList)
825 : {
826 : /* -------------------------------------------------------------------- */
827 : /* Does this psNode overlap the area of interest at all? If not, */
828 : /* return without adding to the list at all. */
829 : /* -------------------------------------------------------------------- */
830 10514500 : if (!CPL_RectOverlap(&psNode->rect, pAoi))
831 6813290 : return;
832 :
833 : /* -------------------------------------------------------------------- */
834 : /* Grow the list to hold the features on this psNode. */
835 : /* -------------------------------------------------------------------- */
836 3699680 : if (*pnFeatureCount + psNode->nFeatures > *pnMaxFeatures)
837 : {
838 : // TODO(schwehr): Symbolic constant.
839 251271 : *pnMaxFeatures = (*pnFeatureCount + psNode->nFeatures) * 2 + 20;
840 251275 : *pppFeatureList = static_cast<void **>(
841 251271 : CPLRealloc(*pppFeatureList, sizeof(void *) * *pnMaxFeatures));
842 : }
843 :
844 : /* -------------------------------------------------------------------- */
845 : /* Add the local features to the list. */
846 : /* -------------------------------------------------------------------- */
847 15404900 : for (int i = 0; i < psNode->nFeatures; i++)
848 : {
849 11700200 : if (hQuadTree->pfnGetBounds == nullptr &&
850 10991100 : hQuadTree->pfnGetBoundsEx == nullptr)
851 : {
852 10990900 : if (CPL_RectOverlap(&psNode->pasBounds[i], pAoi))
853 803651 : (*pppFeatureList)[(*pnFeatureCount)++] = psNode->pahFeatures[i];
854 : }
855 : else
856 : {
857 : CPLRectObj bounds;
858 709238 : if (hQuadTree->pfnGetBoundsEx)
859 188 : hQuadTree->pfnGetBoundsEx(psNode->pahFeatures[i],
860 188 : hQuadTree->pUserData, &bounds);
861 : else
862 709050 : hQuadTree->pfnGetBounds(psNode->pahFeatures[i], &bounds);
863 :
864 708634 : if (CPL_RectOverlap(&bounds, pAoi))
865 365595 : (*pppFeatureList)[(*pnFeatureCount)++] = psNode->pahFeatures[i];
866 : }
867 : }
868 :
869 : /* -------------------------------------------------------------------- */
870 : /* Recurse to subnodes if they exist. */
871 : /* -------------------------------------------------------------------- */
872 13975000 : for (int i = 0; i < psNode->nNumSubNodes; i++)
873 : {
874 10270700 : if (psNode->apSubNode[i])
875 10271000 : CPLQuadTreeCollectFeatures(hQuadTree, psNode->apSubNode[i], pAoi,
876 : pnFeatureCount, pnMaxFeatures,
877 : pppFeatureList);
878 : }
879 : }
880 :
881 : /************************************************************************/
882 : /* CPLQuadTreeSearch() */
883 : /************************************************************************/
884 :
885 : /**
886 : * Returns all the elements inserted whose bounding box intersects the
887 : * provided area of interest
888 : *
889 : * @param hQuadTree the quad tree
890 : * @param pAoi the pointer to the area of interest
891 : * @param pnFeatureCount the user data provided to the function.
892 : *
893 : * @return an array of features that must be freed with CPLFree
894 : */
895 :
896 245287 : void **CPLQuadTreeSearch(const CPLQuadTree *hQuadTree, const CPLRectObj *pAoi,
897 : int *pnFeatureCount)
898 : {
899 245287 : CPLAssert(hQuadTree);
900 245287 : CPLAssert(pAoi);
901 :
902 245287 : int nFeatureCount = 0;
903 245287 : if (pnFeatureCount == nullptr)
904 0 : pnFeatureCount = &nFeatureCount;
905 :
906 245287 : *pnFeatureCount = 0;
907 :
908 245287 : int nMaxFeatures = 0;
909 245287 : void **ppFeatureList = nullptr;
910 245287 : CPLQuadTreeCollectFeatures(hQuadTree, hQuadTree->psRoot, pAoi,
911 : pnFeatureCount, &nMaxFeatures, &ppFeatureList);
912 :
913 245242 : return ppFeatureList;
914 : }
915 :
916 : /************************************************************************/
917 : /* CPLQuadTreeHasMatch() */
918 : /************************************************************************/
919 :
920 419 : static bool CPLQuadTreeHasMatch(const CPLQuadTree *hQuadTree,
921 : const QuadTreeNode *psNode,
922 : const CPLRectObj *pAoi)
923 : {
924 : /* -------------------------------------------------------------------- */
925 : /* Does this psNode overlap the area of interest at all? */
926 : /* -------------------------------------------------------------------- */
927 419 : if (!CPL_RectOverlap(&psNode->rect, pAoi))
928 0 : return false;
929 :
930 : /* -------------------------------------------------------------------- */
931 : /* Check the local features. */
932 : /* -------------------------------------------------------------------- */
933 10864 : for (int i = 0; i < psNode->nFeatures; i++)
934 : {
935 10451 : if (hQuadTree->pfnGetBounds == nullptr &&
936 10451 : hQuadTree->pfnGetBoundsEx == nullptr)
937 : {
938 10451 : if (CPL_RectOverlap(&psNode->pasBounds[i], pAoi))
939 6 : return true;
940 : }
941 : else
942 : {
943 : CPLRectObj bounds;
944 0 : if (hQuadTree->pfnGetBoundsEx)
945 0 : hQuadTree->pfnGetBoundsEx(psNode->pahFeatures[i],
946 0 : hQuadTree->pUserData, &bounds);
947 : else
948 0 : hQuadTree->pfnGetBounds(psNode->pahFeatures[i], &bounds);
949 :
950 0 : if (CPL_RectOverlap(&bounds, pAoi))
951 0 : return true;
952 : }
953 : }
954 :
955 : /* -------------------------------------------------------------------- */
956 : /* Recurse to subnodes if they exist. */
957 : /* -------------------------------------------------------------------- */
958 413 : for (int i = 0; i < psNode->nNumSubNodes; i++)
959 : {
960 0 : if (psNode->apSubNode[i])
961 : {
962 0 : if (CPLQuadTreeHasMatch(hQuadTree, psNode->apSubNode[i], pAoi))
963 : {
964 0 : return true;
965 : }
966 : }
967 : }
968 :
969 413 : return false;
970 : }
971 :
972 : /**
973 : * Returns whether the quadtree has at least one element whose bounding box
974 : * intersects the provided area of interest
975 : *
976 : * @param hQuadTree the quad tree
977 : * @param pAoi the pointer to the area of interest
978 : */
979 :
980 419 : bool CPLQuadTreeHasMatch(const CPLQuadTree *hQuadTree, const CPLRectObj *pAoi)
981 : {
982 419 : CPLAssert(hQuadTree);
983 419 : CPLAssert(pAoi);
984 :
985 419 : return CPLQuadTreeHasMatch(hQuadTree, hQuadTree->psRoot, pAoi);
986 : }
987 :
988 : /************************************************************************/
989 : /* CPLQuadTreeNodeForeach() */
990 : /************************************************************************/
991 :
992 25 : static bool CPLQuadTreeNodeForeach(const QuadTreeNode *psNode,
993 : CPLQuadTreeForeachFunc pfnForeach,
994 : void *pUserData)
995 : {
996 49 : for (int i = 0; i < psNode->nNumSubNodes; i++)
997 : {
998 24 : if (!CPLQuadTreeNodeForeach(psNode->apSubNode[i], pfnForeach,
999 : pUserData))
1000 0 : return false;
1001 : }
1002 :
1003 50 : for (int i = 0; i < psNode->nFeatures; i++)
1004 : {
1005 25 : if (pfnForeach(psNode->pahFeatures[i], pUserData) == FALSE)
1006 0 : return false;
1007 : }
1008 :
1009 25 : return true;
1010 : }
1011 :
1012 : /************************************************************************/
1013 : /* CPLQuadTreeForeach() */
1014 : /************************************************************************/
1015 :
1016 : /**
1017 : * Walk through the quadtree and runs the provided function on all the
1018 : * elements
1019 : *
1020 : * This function is provided with the user_data argument of pfnForeach.
1021 : * It must return TRUE to go on the walk through the hash set, or FALSE to
1022 : * make it stop.
1023 : *
1024 : * Note : the structure of the quadtree must *NOT* be modified during the
1025 : * walk.
1026 : *
1027 : * @param hQuadTree the quad tree
1028 : * @param pfnForeach the function called on each element.
1029 : * @param pUserData the user data provided to the function.
1030 : */
1031 :
1032 1 : void CPLQuadTreeForeach(const CPLQuadTree *hQuadTree,
1033 : CPLQuadTreeForeachFunc pfnForeach, void *pUserData)
1034 : {
1035 1 : CPLAssert(hQuadTree);
1036 1 : CPLAssert(pfnForeach);
1037 1 : CPLQuadTreeNodeForeach(hQuadTree->psRoot, pfnForeach, pUserData);
1038 1 : }
1039 :
1040 : /************************************************************************/
1041 : /* CPLQuadTreeDumpNode() */
1042 : /************************************************************************/
1043 :
1044 0 : static void CPLQuadTreeDumpNode(const QuadTreeNode *psNode, int nIndentLevel,
1045 : CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc,
1046 : void *pUserData)
1047 : {
1048 0 : if (psNode->nNumSubNodes)
1049 : {
1050 0 : for (int count = nIndentLevel; --count >= 0;)
1051 : {
1052 0 : printf(" "); /*ok*/
1053 : }
1054 0 : printf("SubhQuadTrees :\n"); /*ok*/
1055 0 : for (int i = 0; i < psNode->nNumSubNodes; i++)
1056 : {
1057 0 : for (int count = nIndentLevel + 1; --count >= 0;)
1058 : {
1059 0 : printf(" "); /*ok*/
1060 : }
1061 0 : printf("SubhQuadTree %d :\n", i + 1); /*ok*/
1062 0 : CPLQuadTreeDumpNode(psNode->apSubNode[i], nIndentLevel + 2,
1063 : pfnDumpFeatureFunc, pUserData);
1064 : }
1065 : }
1066 0 : if (psNode->nFeatures)
1067 : {
1068 0 : for (int count = nIndentLevel; --count >= 0;)
1069 0 : printf(" "); /*ok*/
1070 0 : printf("Leaves (%d):\n", psNode->nFeatures); /*ok*/
1071 0 : for (int i = 0; i < psNode->nFeatures; i++)
1072 : {
1073 0 : if (pfnDumpFeatureFunc)
1074 : {
1075 0 : pfnDumpFeatureFunc(psNode->pahFeatures[i], nIndentLevel + 2,
1076 : pUserData);
1077 : }
1078 : else
1079 : {
1080 0 : for (int count = nIndentLevel + 1; --count >= 0;)
1081 : {
1082 0 : printf(" "); /*ok*/
1083 : }
1084 0 : printf("%p\n", psNode->pahFeatures[i]); /*ok*/
1085 : }
1086 : }
1087 : }
1088 0 : }
1089 :
1090 : /************************************************************************/
1091 : /* CPLQuadTreeDump() */
1092 : /************************************************************************/
1093 :
1094 : /** Dump quad tree */
1095 0 : void CPLQuadTreeDump(const CPLQuadTree *hQuadTree,
1096 : CPLQuadTreeDumpFeatureFunc pfnDumpFeatureFunc,
1097 : void *pUserData)
1098 : {
1099 0 : CPLQuadTreeDumpNode(hQuadTree->psRoot, 0, pfnDumpFeatureFunc, pUserData);
1100 0 : }
1101 :
1102 : /************************************************************************/
1103 : /* CPLQuadTreeGetStatsNode() */
1104 : /************************************************************************/
1105 :
1106 0 : static void CPLQuadTreeGetStatsNode(const QuadTreeNode *psNode, int nDepthLevel,
1107 : int *pnNodeCount, int *pnMaxDepth,
1108 : int *pnMaxBucketCapacity)
1109 : {
1110 0 : (*pnNodeCount)++;
1111 0 : if (nDepthLevel > *pnMaxDepth)
1112 0 : *pnMaxDepth = nDepthLevel;
1113 0 : if (psNode->nFeatures > *pnMaxBucketCapacity)
1114 0 : *pnMaxBucketCapacity = psNode->nFeatures;
1115 :
1116 0 : for (int i = 0; i < psNode->nNumSubNodes; i++)
1117 : {
1118 0 : CPLQuadTreeGetStatsNode(psNode->apSubNode[i], nDepthLevel + 1,
1119 : pnNodeCount, pnMaxDepth, pnMaxBucketCapacity);
1120 : }
1121 0 : }
1122 :
1123 : /************************************************************************/
1124 : /* CPLQuadTreeGetStats() */
1125 : /************************************************************************/
1126 :
1127 : /** Get stats */
1128 0 : void CPLQuadTreeGetStats(const CPLQuadTree *hQuadTree, int *pnFeatureCount,
1129 : int *pnNodeCount, int *pnMaxDepth,
1130 : int *pnMaxBucketCapacity)
1131 : {
1132 0 : CPLAssert(hQuadTree);
1133 :
1134 0 : int nFeatureCount = 0;
1135 0 : if (pnFeatureCount == nullptr)
1136 0 : pnFeatureCount = &nFeatureCount;
1137 0 : int nNodeCount = 0;
1138 0 : if (pnNodeCount == nullptr)
1139 0 : pnNodeCount = &nNodeCount;
1140 0 : int nMaxDepth = 0;
1141 0 : if (pnMaxDepth == nullptr)
1142 0 : pnMaxDepth = &nMaxDepth;
1143 0 : int nMaxBucketCapacity = 0;
1144 0 : if (pnMaxBucketCapacity == nullptr)
1145 0 : pnMaxBucketCapacity = &nMaxBucketCapacity;
1146 :
1147 0 : *pnFeatureCount = hQuadTree->nFeatures;
1148 0 : *pnNodeCount = 0;
1149 0 : *pnMaxDepth = 1;
1150 0 : *pnMaxBucketCapacity = 0;
1151 :
1152 0 : CPLQuadTreeGetStatsNode(hQuadTree->psRoot, 0, pnNodeCount, pnMaxDepth,
1153 : pnMaxBucketCapacity);
1154 :
1155 : // TODO(schwehr): If any of the pointers were set to local vars,
1156 : // do they need to be reset to a nullptr?
1157 0 : }
|
