48 if (m_level == insertionLevel)
return NodePtr(
this, &(m_pTree->m_indexPool));
50 pathBuffer.push(m_identifier);
54 switch (m_pTree->m_treeVariant)
74 assert(child != std::numeric_limits<uint32_t>::max());
76 NodePtr n = m_pTree->readNode(m_pIdentifier[child]);
77 NodePtr ret = n->chooseSubtree(mbr, insertionLevel, pathBuffer);
86 pathBuffer.push(m_identifier);
88 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
90 if (m_ptrMBR[cChild]->containsRegion(mbr))
92 NodePtr n = m_pTree->readNode(m_pIdentifier[cChild]);
93 NodePtr l = n->findLeaf(mbr,
id, pathBuffer);
95 if (l.
get() !=
nullptr)
return l;
106 ++(m_pTree->m_stats.m_u64Splits);
108 std::vector<uint32_t> g1, g2;
110 switch (m_pTree->m_treeVariant)
114 rtreeSplit(dataLength, pData, mbr,
id, g1, g2);
117 rstarSplit(dataLength, pData, mbr,
id, g1, g2);
123 ptrLeft = m_pTree->m_indexPool.acquire();
124 ptrRight = m_pTree->m_indexPool.acquire();
126 if (ptrLeft.
get() ==
nullptr) ptrLeft =
NodePtr(
new Index(m_pTree, m_identifier, m_level), &(m_pTree->m_indexPool));
127 if (ptrRight.
get() ==
nullptr) ptrRight =
NodePtr(
new Index(m_pTree, -1, m_level), &(m_pTree->m_indexPool));
129 ptrLeft->m_nodeMBR = m_pTree->m_infiniteRegion;
130 ptrRight->m_nodeMBR = m_pTree->m_infiniteRegion;
134 for (cIndex = 0; cIndex < g1.size(); ++cIndex)
136 ptrLeft->insertEntry(0,
nullptr, *(m_ptrMBR[g1[cIndex]]), m_pIdentifier[g1[cIndex]]);
139 for (cIndex = 0; cIndex < g2.size(); ++cIndex)
141 ptrRight->insertEntry(0,
nullptr, *(m_ptrMBR[g2[cIndex]]), m_pIdentifier[g2[cIndex]]);
147 double area = std::numeric_limits<double>::infinity();
148 uint32_t best = std::numeric_limits<uint32_t>::max();
150 RegionPtr t = m_pTree->m_regionPool.acquire();
152 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
156 double a = m_ptrMBR[cChild]->getArea();
164 else if (enl == area)
168 if (enl == std::numeric_limits<double>::infinity()
169 || a < m_ptrMBR[best]->getArea()) best = cChild;
180 double leastOverlap = std::numeric_limits<double>::max();
181 double me = std::numeric_limits<double>::max();
185 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
193 for (uint32_t i = 0; i < cChild; ++i)
delete entries[i];
198 entries[cChild]->
m_index = cChild;
199 entries[cChild]->
m_original = m_ptrMBR[cChild];
200 entries[cChild]->
m_combined = m_pTree->m_regionPool.acquire();
206 if (entries[cChild]->m_enlargement < me)
209 best = entries[cChild];
211 else if (entries[cChild]->m_enlargement == me && entries[cChild]->m_oa < best->m_oa)
213 best = entries[cChild];
217 if (me < -std::numeric_limits<double>::epsilon() || me > std::numeric_limits<double>::epsilon())
219 uint32_t cIterations;
221 if (m_children > m_pTree->m_nearMinimumOverlapFactor)
224 ::qsort(entries, m_children,
227 assert(entries[0]->m_enlargement <= entries[m_children - 1]->m_enlargement);
229 cIterations = m_pTree->m_nearMinimumOverlapFactor;
233 cIterations = m_children;
237 for (uint32_t cIndex = 0; cIndex < cIterations; ++cIndex)
242 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
251 if (dif < leastOverlap)
254 best = entries[cIndex];
256 else if (dif == leastOverlap)
274 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
276 delete entries[cChild];
285 ++(m_pTree->m_stats.m_u64Adjustments);
289 for (child = 0; child < m_children; ++child)
291 if (m_pIdentifier[child] == n->m_identifier)
break;
297 bool bContained = m_nodeMBR.containsRegion(n->m_nodeMBR);
298 bool bTouches = m_nodeMBR.touchesRegion(*(m_ptrMBR[child]));
299 bool bRecompute = (! bContained || (bTouches && m_pTree->m_bTightMBRs));
301 *(m_ptrMBR[child]) = n->m_nodeMBR;
303 if (bRecompute || force)
305 for (uint32_t cDim = 0; cDim < m_nodeMBR.m_dimension; ++cDim)
307 m_nodeMBR.
m_pLow[cDim] = std::numeric_limits<double>::max();
308 m_nodeMBR.m_pHigh[cDim] = -std::numeric_limits<double>::max();
310 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
312 m_nodeMBR.m_pLow[cDim] = std::min(m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->m_pLow[cDim]);
313 m_nodeMBR.m_pHigh[cDim] = std::max(m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->m_pHigh[cDim]);
318 m_pTree->writeNode(
this);
320 if ((bRecompute || force) && (! pathBuffer.empty()))
322 id_type cParent = pathBuffer.top(); pathBuffer.pop();
323 NodePtr ptrN = m_pTree->readNode(cParent);
331 ++(m_pTree->m_stats.m_u64Adjustments);
335 for (child = 0; child < m_children; ++child)
337 if (m_pIdentifier[child] == n1->m_identifier)
break;
343 bool bContained1 = m_nodeMBR.containsRegion(n1->m_nodeMBR);
344 bool bContained2 = m_nodeMBR.containsRegion(n2->m_nodeMBR);
345 bool bContained = bContained1 && bContained2;
346 bool bTouches = m_nodeMBR.touchesRegion(*(m_ptrMBR[child]));
347 bool bRecompute = (! bContained || (bTouches && m_pTree->m_bTightMBRs));
349 *(m_ptrMBR[child]) = n1->m_nodeMBR;
353 for (uint32_t cDim = 0; cDim < m_nodeMBR.m_dimension; ++cDim)
355 m_nodeMBR.
m_pLow[cDim] = std::numeric_limits<double>::max();
356 m_nodeMBR.m_pHigh[cDim] = -std::numeric_limits<double>::max();
358 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
360 m_nodeMBR.m_pLow[cDim] = std::min(m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->m_pLow[cDim]);
361 m_nodeMBR.m_pHigh[cDim] = std::max(m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->m_pHigh[cDim]);
369 bool bAdjusted = insertData(0,
nullptr, n2->m_nodeMBR, n2->m_identifier, pathBuffer, overflowTable);
374 if ((! bAdjusted) && bRecompute && (! pathBuffer.empty()))
376 id_type cParent = pathBuffer.top(); pathBuffer.pop();
377 NodePtr ptrN = m_pTree->readNode(cParent);
uint32_t findLeastEnlargement(const Region &) const
void adjustTree(Node *, std::stack< id_type > &, bool force=false)
static int compareEntries(const void *pv1, const void *pv2)
NodePtr chooseSubtree(const Region &mbr, uint32_t level, std::stack< id_type > &pathBuffer) override
virtual double getIntersectingArea(const Region &in) const
virtual void getCombinedRegion(Region &out, const Region &in) const
uint32_t findLeastOverlap(const Region &) const
double getArea() const override
Tools::PoolPointer< Node > NodePtr
Index(RTree *pTree, id_type id, uint32_t level)
void split(uint32_t dataLength, uint8_t *pData, Region &mbr, id_type id, NodePtr &left, NodePtr &right) override
NodePtr findLeaf(const Region &mbr, id_type id, std::stack< id_type > &pathBuffer) override