| 716 | /************************************************************************/ |
| 717 | |
| 718 | 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 | if (nMaxDepth > 1 && psNode->nNumSubNodes > 0) |
| 728 | { |
| 729 | for (int i = 0; i < psNode->nNumSubNodes; i++) |
| 730 | { |
| 731 | if (CPL_RectContained(pRect, &psNode->apSubNode[i]->rect)) |
| 732 | { |
| 733 | CPLQuadTreeNodeAddFeatureAlg2(hQuadTree, psNode->apSubNode[i], |
| 734 | hFeature, pRect, nMaxDepth - 1); |
| 735 | return; |
| 736 | } |
| 737 | } |
| 738 | } |
| 739 | |
| 740 | /* -------------------------------------------------------------------- */ |
| 741 | /* Otherwise, consider creating four apSubNodes if could fit into */ |
| 742 | /* them, and adding to the appropriate apSubNode. */ |
| 743 | /* -------------------------------------------------------------------- */ |
| 744 | else if (nMaxDepth > 1 && psNode->nNumSubNodes == 0) |
| 745 | { |
| 746 | CPLRectObj half1, half2, quad1, quad2, quad3, quad4; |
| 747 | |
| 748 | CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &psNode->rect, &half1, |
| 749 | &half2); |
| 750 | CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half1, &quad1, &quad2); |
| 751 | CPLQuadTreeSplitBounds(hQuadTree->dfSplitRatio, &half2, &quad3, &quad4); |
| 752 | |
| 753 | if (memcmp(&psNode->rect, &quad1, sizeof(CPLRectObj)) != 0 && |
| 754 | memcmp(&psNode->rect, &quad2, sizeof(CPLRectObj)) != 0 && |
| 755 | memcmp(&psNode->rect, &quad3, sizeof(CPLRectObj)) != 0 && |
| 756 | memcmp(&psNode->rect, &quad4, sizeof(CPLRectObj)) != 0 && |
| 757 | (CPL_RectContained(pRect, &quad1) || |
| 758 | CPL_RectContained(pRect, &quad2) || |
| 759 | CPL_RectContained(pRect, &quad3) || |
| 760 | CPL_RectContained(pRect, &quad4))) |
| 761 | { |
| 762 | psNode->nNumSubNodes = 4; |
| 763 | psNode->apSubNode[0] = CPLQuadTreeNodeCreate(&quad1); |
| 764 | psNode->apSubNode[1] = CPLQuadTreeNodeCreate(&quad2); |
| 765 | psNode->apSubNode[2] = CPLQuadTreeNodeCreate(&quad3); |
| 766 | psNode->apSubNode[3] = CPLQuadTreeNodeCreate(&quad4); |
| 767 | |
| 768 | /* recurse back on this psNode now that it has apSubNodes */ |
| 769 | CPLQuadTreeNodeAddFeatureAlg2(hQuadTree, psNode, hFeature, pRect, |
| 770 | nMaxDepth); |
| 771 | return; |
| 772 | } |
| 773 | } |
| 774 | |
| 775 | /* -------------------------------------------------------------------- */ |
no test coverage detected