49 if (m_level == insertionLevel)
return NodePtr(
this, &(m_pTree->m_indexPool));
51 pathBuffer.push(m_identifier);
55 switch (m_pTree->m_treeVariant)
71 assert(child != std::numeric_limits<uint32_t>::max());
73 NodePtr n = m_pTree->readNode(m_pIdentifier[child]);
74 NodePtr ret = n->chooseSubtree(mbr, insertionLevel, pathBuffer);
83 pathBuffer.push(m_identifier);
85 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
87 if (m_ptrMBR[cChild]->containsRegionAfterTime(m_pTree->m_currentTime, mbr))
89 NodePtr n = m_pTree->readNode(m_pIdentifier[cChild]);
90 NodePtr l = n->findLeaf(mbr,
id, pathBuffer);
92 if (l.
get() !=
nullptr)
return l;
103 ++(m_pTree->m_stats.m_splits);
105 std::vector<uint32_t> g1, g2;
107 switch (m_pTree->m_treeVariant)
110 rstarSplit(dataLength, pData, mbr,
id, g1, g2);
116 pLeft = m_pTree->m_indexPool.acquire();
117 pRight = m_pTree->m_indexPool.acquire();
119 if (pLeft.
get() ==
nullptr) pLeft =
NodePtr(
new Index(m_pTree, m_identifier, m_level), &(m_pTree->m_indexPool));
120 if (pRight.
get() ==
nullptr) pRight =
NodePtr(
new Index(m_pTree, -1, m_level), &(m_pTree->m_indexPool));
122 pLeft->m_nodeMBR = m_pTree->m_infiniteRegion;
123 pRight->m_nodeMBR = m_pTree->m_infiniteRegion;
127 for (cIndex = 0; cIndex < g1.size(); ++cIndex)
129 pLeft->insertEntry(0,
nullptr, *(m_ptrMBR[g1[cIndex]]), m_pIdentifier[g1[cIndex]]);
132 for (cIndex = 0; cIndex < g2.size(); ++cIndex)
134 pRight->insertEntry(0,
nullptr, *(m_ptrMBR[g2[cIndex]]), m_pIdentifier[g2[cIndex]]);
140 double area = std::numeric_limits<double>::max();
141 uint32_t best = std::numeric_limits<uint32_t>::max();
144 Tools::Interval ivT(m_pTree->m_currentTime, m_pTree->m_currentTime + m_pTree->m_horizon);
146 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
149 m_ptrMBR[cChild]->getCombinedRegionAfterTime(ivT.getLowerBound(), *t, r);
151 double a = m_ptrMBR[cChild]->getAreaInTime(ivT);
160 else if (enl == area)
164 if (a < m_ptrMBR[best]->getAreaInTime(ivT)) best = cChild;
173 OverlapEntry** entries =
new OverlapEntry*[m_children];
175 double leastOverlap = std::numeric_limits<double>::max();
176 double me = std::numeric_limits<double>::max();
177 OverlapEntry* best =
nullptr;
179 Tools::Interval ivT(m_pTree->m_currentTime, m_pTree->m_currentTime + m_pTree->m_horizon);
182 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
186 entries[cChild] =
new OverlapEntry();
190 for (uint32_t i = 0; i < cChild; ++i)
delete entries[i];
195 entries[cChild]->m_index = cChild;
196 entries[cChild]->m_original = m_ptrMBR[cChild];
197 entries[cChild]->m_combined = m_pTree->m_regionPool.acquire();
198 m_ptrMBR[cChild]->getCombinedRegionAfterTime(m_pTree->m_currentTime, *(entries[cChild]->m_combined), r);
199 entries[cChild]->m_oa = entries[cChild]->m_original->getAreaInTime(ivT);
200 entries[cChild]->m_ca = entries[cChild]->m_combined->getAreaInTime(ivT);
201 entries[cChild]->m_enlargement = entries[cChild]->m_ca - entries[cChild]->m_oa;
203 if (entries[cChild]->m_enlargement < me)
205 me = entries[cChild]->m_enlargement;
206 best = entries[cChild];
208 else if (entries[cChild]->m_enlargement == me && entries[cChild]->m_oa < best->m_oa)
210 best = entries[cChild];
214 if (me < -std::numeric_limits<double>::epsilon() || me > std::numeric_limits<double>::epsilon())
216 uint32_t cIterations;
218 if (m_children > m_pTree->m_nearMinimumOverlapFactor)
221 ::qsort(entries, m_children,
222 sizeof(OverlapEntry*),
224 assert(entries[0]->m_enlargement <= entries[m_children - 1]->m_enlargement);
226 cIterations = m_pTree->m_nearMinimumOverlapFactor;
230 cIterations = m_children;
234 for (uint32_t cIndex = 0; cIndex < cIterations; ++cIndex)
237 OverlapEntry* e = entries[cIndex];
239 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
241 if (e->m_index != cChild)
243 double f = e->m_combined->getIntersectingAreaInTime(ivT, *(m_ptrMBR[cChild]));
244 if (f != 0.0) dif += f - e->m_original->getIntersectingAreaInTime(ivT, *(m_ptrMBR[cChild]));
248 if (dif < leastOverlap)
251 best = entries[cIndex];
253 else if (dif == leastOverlap)
255 if (e->m_enlargement == best->m_enlargement)
258 if (e->m_original->getAreaInTime(ivT) < best->m_original->getAreaInTime(ivT)) best = entries[cIndex];
263 if (e->m_enlargement < best->m_enlargement) best = entries[cIndex];
269 uint32_t ret = best->m_index;
271 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
273 delete entries[cChild];
282 ++(m_pTree->m_stats.m_adjustments);
286 for (child = 0; child < m_children; ++child)
288 if (m_pIdentifier[child] == n->m_identifier)
break;
290 assert(child < m_children);
298 *(m_ptrMBR[child]) = n->m_nodeMBR;
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();
309 m_nodeMBR.m_pVLow[cDim] = std::numeric_limits<double>::max();
310 m_nodeMBR.m_pVHigh[cDim] = -std::numeric_limits<double>::max();
312 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
314 m_nodeMBR.m_pLow[cDim] = std::min(m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->getExtrapolatedLow(cDim, m_nodeMBR.m_startTime));
315 m_nodeMBR.m_pHigh[cDim] = std::max(m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->getExtrapolatedHigh(cDim, m_nodeMBR.m_startTime));
316 m_nodeMBR.m_pVLow[cDim] = std::min(m_nodeMBR.m_pVLow[cDim], m_ptrMBR[cChild]->m_pVLow[cDim]);
317 m_nodeMBR.m_pVHigh[cDim] = std::max(m_nodeMBR.m_pVHigh[cDim], m_ptrMBR[cChild]->m_pVHigh[cDim]);
319 m_nodeMBR.m_pLow[cDim] -= 2.0 * std::numeric_limits<double>::epsilon();
320 m_nodeMBR.m_pHigh[cDim] += 2.0 * std::numeric_limits<double>::epsilon();
325 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
327 assert(m_nodeMBR.containsRegionAfterTime(m_pTree->m_currentTime, *(m_ptrMBR[cChild])) ==
true);
331 m_pTree->writeNode(
this);
333 if ( ! pathBuffer.empty())
335 id_type cParent = pathBuffer.top(); pathBuffer.pop();
336 NodePtr ptrN = m_pTree->readNode(cParent);
338 p->adjustTree(
this, pathBuffer);
344 ++(m_pTree->m_stats.m_adjustments);
348 for (child = 0; child < m_children; ++child)
350 if (m_pIdentifier[child] == n1->m_identifier)
break;
352 assert(child < m_children);
360 *(m_ptrMBR[child]) = n1->m_nodeMBR;
366 for (uint32_t cDim = 0; cDim < m_nodeMBR.m_dimension; ++cDim)
368 m_nodeMBR.m_pLow[cDim] = std::numeric_limits<double>::max();
369 m_nodeMBR.m_pHigh[cDim] = -std::numeric_limits<double>::max();
370 m_nodeMBR.m_pVLow[cDim] = std::numeric_limits<double>::max();
371 m_nodeMBR.m_pVHigh[cDim] = -std::numeric_limits<double>::max();
373 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
375 m_nodeMBR.m_pLow[cDim] = std::min(m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->getExtrapolatedLow(cDim, m_nodeMBR.m_startTime));
376 m_nodeMBR.m_pHigh[cDim] = std::max(m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->getExtrapolatedHigh(cDim, m_nodeMBR.m_startTime));
377 m_nodeMBR.m_pVLow[cDim] = std::min(m_nodeMBR.m_pVLow[cDim], m_ptrMBR[cChild]->m_pVLow[cDim]);
378 m_nodeMBR.m_pVHigh[cDim] = std::max(m_nodeMBR.m_pVHigh[cDim], m_ptrMBR[cChild]->m_pVHigh[cDim]);
380 m_nodeMBR.m_pLow[cDim] -= 2.0 * std::numeric_limits<double>::epsilon();
381 m_nodeMBR.m_pHigh[cDim] += 2.0 * std::numeric_limits<double>::epsilon();
386 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
388 assert(m_nodeMBR.containsRegionAfterTime(m_pTree->m_currentTime, *(m_ptrMBR[cChild])) ==
true);
395 bool bAdjusted = insertData(0,
nullptr, n2->m_nodeMBR, n2->m_identifier, pathBuffer, overflowTable);
400 if (! bAdjusted && ! pathBuffer.empty())
402 id_type cParent = pathBuffer.top(); pathBuffer.pop();
403 NodePtr ptrN = m_pTree->readNode(cParent);
405 p->adjustTree(
this, pathBuffer);
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
Index(const Tools::PropertySet &poProperties)
uint32_t findLeastOverlap(const Region &) const
double getAreaInTime() 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