| 549 | /************************************************************************/ |
| 550 | |
| 551 | static void CPLQuadTreeNodeAddFeatureAlg1(CPLQuadTree *hQuadTree, |
| 552 | QuadTreeNode *psNode, void *hFeature, |
| 553 | const CPLRectObj *pRect) |
| 554 | { |
| 555 | if (psNode->nNumSubNodes == 0) |
| 556 | { |
| 557 | // If we have reached the max bucket capacity, try to insert |
| 558 | // in a subnode if possible. |
| 559 | if (psNode->nFeatures >= hQuadTree->nBucketCapacity) |
| 560 | { |
| 561 | CPLRectObj half1 = {0.0, 0.0, 0.0, 0.0}; |
| 562 | CPLRectObj half2 = {0.0, 0.0, 0.0, 0.0}; |
| 563 | CPLRectObj quad1 = {0.0, 0.0, 0.0, 0.0}; |
| 564 | CPLRectObj quad2 = {0.0, 0.0, 0.0, 0.0}; |
| 565 | CPLRectObj quad3 = {0.0, 0.0, 0.0, 0.0}; |
| 566 | CPLRectObj quad4 = {0.0, 0.0, 0.0, 0.0}; |
| 567 | |
| 568 | CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &psNode->rect, |
| 569 | &half1, &half2); |
| 570 | CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half1, &quad1, |
| 571 | &quad2); |
| 572 | CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half2, &quad3, |
| 573 | &quad4); |
| 574 | |
| 575 | if (memcmp(&psNode->rect, &quad1, sizeof(CPLRectObj)) != 0 && |
| 576 | memcmp(&psNode->rect, &quad2, sizeof(CPLRectObj)) != 0 && |
| 577 | memcmp(&psNode->rect, &quad3, sizeof(CPLRectObj)) != 0 && |
| 578 | memcmp(&psNode->rect, &quad4, sizeof(CPLRectObj)) != 0 && |
| 579 | (hQuadTree->bForceUseOfSubNodes || |
| 580 | CPL_RectContained(pRect, &quad1) || |
| 581 | CPL_RectContained(pRect, &quad2) || |
| 582 | CPL_RectContained(pRect, &quad3) || |
| 583 | CPL_RectContained(pRect, &quad4))) |
| 584 | { |
| 585 | psNode->nNumSubNodes = 4; |
| 586 | psNode->apSubNode[0] = CPLQuadTreeNodeCreate(&quad1); |
| 587 | psNode->apSubNode[1] = CPLQuadTreeNodeCreate(&quad2); |
| 588 | psNode->apSubNode[2] = CPLQuadTreeNodeCreate(&quad3); |
| 589 | psNode->apSubNode[3] = CPLQuadTreeNodeCreate(&quad4); |
| 590 | |
| 591 | const int oldNumFeatures = psNode->nFeatures; |
| 592 | void **oldFeatures = psNode->pahFeatures; |
| 593 | CPLRectObj *pasOldBounds = psNode->pasBounds; |
| 594 | psNode->nFeatures = 0; |
| 595 | psNode->pahFeatures = nullptr; |
| 596 | psNode->pasBounds = nullptr; |
| 597 | |
| 598 | // Redispatch existing pahFeatures in apSubNodes. |
| 599 | for (int i = 0; i < oldNumFeatures; i++) |
| 600 | { |
| 601 | if (hQuadTree->pfnGetBounds == nullptr && |
| 602 | hQuadTree->pfnGetBoundsEx == nullptr) |
| 603 | CPLQuadTreeNodeAddFeatureAlg1(hQuadTree, psNode, |
| 604 | oldFeatures[i], |
| 605 | &pasOldBounds[i]); |
| 606 | else |
| 607 | { |
| 608 | CPLRectObj bounds; |
no test coverage detected