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