20 #define rtree_min(a,b) (a<b?a:b)
21 #define rtree_max(a,b) (a>b?a:b)
29 #define RTREE_TEMPLATE template<class DATATYPE, class DATATYPENP, class ELEMTYPE, int NUMDIMS, class CONTEXT, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
30 #define RTREE_QUAL RTree<DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES>
32 #define RTREE_DONT_USE_MEMPOOLS
33 #define RTREE_USE_SPHERICAL_VOLUME
59 template<
class DATATYPE,
class DATATYPENP,
class ELEMTYPE,
int NUMDIMS,
class CONTEXT,
60 class ELEMTYPEREAL = ELEMTYPE,
int TMAXNODES = 8,
int TMINNODES = TMAXNODES / 2>
79 typedef void(DATATYPENP::*
Operation)(
const CONTEXT &)
const;
88 virtual void Insert(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE& a_dataId);
94 virtual void Remove(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE& a_dataId);
107 virtual int Search(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const CONTEXT &c)
const;
117 #ifdef RTREE_WANTS_IO
119 bool Load(
const char* a_fileName);
121 bool Load(RTFileStream& a_stream);
125 bool Save(
const char* a_fileName);
127 bool Save(RTFileStream& a_stream);
211 Push(nextLevelnode, 0);
214 if(nextLevelnode->
IsLeaf())
242 friend class RTree<DATATYPE, DATATYPENP, ELEMTYPE, NUMDIMS, CONTEXT, ELEMTYPEREAL, TMAXNODES, TMINNODES>;
349 bool Search(
Node* a_node,
Rect* a_rect,
int& a_foundCount,
const CONTEXT &c)
const;
354 #ifdef RTREE_WANTS_IO
355 bool SaveRec(
Node* a_node, RTFileStream& a_stream);
356 bool LoadRec(
Node* a_node, RTFileStream& a_stream);
365 #ifdef RTREE_WANTS_IO
385 bool OpenRead(
const char* a_fileName)
387 m_file = fopen(a_fileName,
"rb");
395 bool OpenWrite(
const char* a_fileName)
397 m_file = fopen(a_fileName,
"wb");
414 template<
typename TYPE >
415 size_t Write(
const TYPE& a_value)
418 return fwrite((
void*)&a_value,
sizeof(a_value), 1, m_file);
421 template<
typename TYPE >
422 size_t WriteArray(
const TYPE* a_array,
int a_count)
425 return fwrite((
void*)a_array,
sizeof(TYPE) * a_count, 1, m_file);
428 template<
typename TYPE >
429 size_t Read(TYPE& a_value)
432 return fread((
void*)&a_value,
sizeof(a_value), 1, m_file);
435 template<
typename TYPE >
436 size_t ReadArray(TYPE* a_array,
int a_count)
439 return fread((
void*)a_array,
sizeof(TYPE) * a_count, 1, m_file);
446 RTREE_QUAL::RTree(Operation operation)
447 : myOperation(operation)
455 ASSERT(
sizeof(DATATYPE) ==
sizeof(
void*) ||
sizeof(DATATYPE) ==
sizeof(
int));
458 const float UNIT_SPHERE_VOLUMES[] = {
459 0.000000f, 2.000000f, 3.141593f,
460 4.188790f, 4.934802f, 5.263789f,
461 5.167713f, 4.724766f, 4.058712f,
462 3.298509f, 2.550164f, 1.884104f,
463 1.335263f, 0.910629f, 0.599265f,
464 0.381443f, 0.235331f, 0.140981f,
465 0.082146f, 0.046622f, 0.025807f,
482 void RTREE_QUAL::Insert(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE& a_dataId)
485 for(
int index=0; index<NUMDIMS; ++index)
487 ASSERT(a_min[index] <= a_max[index]);
493 for(
int axis=0; axis<NUMDIMS; ++axis)
495 rect.m_min[axis] = a_min[axis];
496 rect.m_max[axis] = a_max[axis];
499 InsertRect(&rect, a_dataId, &m_root, 0);
504 void RTREE_QUAL::Remove(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE& a_dataId)
507 for(
int index=0; index<NUMDIMS; ++index)
509 ASSERT(a_min[index] <= a_max[index]);
515 for(
int axis=0; axis<NUMDIMS; ++axis)
517 rect.m_min[axis] = a_min[axis];
518 rect.m_max[axis] = a_max[axis];
521 RemoveRect(&rect, a_dataId, &m_root);
527 int RTREE_QUAL::Search(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const CONTEXT &c)
const
530 for(
int index=0; index<NUMDIMS; ++index)
532 ASSERT(a_min[index] <= a_max[index]);
538 for(
int axis=0; axis<NUMDIMS; ++axis)
540 rect.m_min[axis] = a_min[axis];
541 rect.m_max[axis] = a_max[axis];
547 Search(m_root, &rect, foundCount, c);
558 int RTREE_QUAL::Count()
561 CountRec(m_root, count);
569 void RTREE_QUAL::CountRec(
Node* a_node,
int& a_count)
571 if(a_node->IsInternalNode())
573 for(
int index = 0; index < a_node->m_count; ++index)
575 CountRec(a_node->m_branch[index].m_child, a_count);
580 a_count += a_node->m_count;
585 #ifdef RTREE_WANTS_IO
587 bool RTREE_QUAL::Load(
const char* a_fileName)
592 if(!stream.OpenRead(a_fileName))
597 bool result = Load(stream);
607 bool RTREE_QUAL::Load(RTFileStream& a_stream)
610 int _dataFileId = (
'R'<<0)|(
'T'<<8)|(
'R'<<16)|(
'E'<<24);
611 int _dataSize =
sizeof(DATATYPE);
612 int _dataNumDims = NUMDIMS;
613 int _dataElemSize =
sizeof(ELEMTYPE);
614 int _dataElemRealSize =
sizeof(ELEMTYPEREAL);
615 int _dataMaxNodes = TMAXNODES;
616 int _dataMinNodes = TMINNODES;
621 int dataElemSize = 0;
622 int dataElemRealSize = 0;
623 int dataMaxNodes = 0;
624 int dataMinNodes = 0;
626 a_stream.Read(dataFileId);
627 a_stream.Read(dataSize);
628 a_stream.Read(dataNumDims);
629 a_stream.Read(dataElemSize);
630 a_stream.Read(dataElemRealSize);
631 a_stream.Read(dataMaxNodes);
632 a_stream.Read(dataMinNodes);
637 if( (dataFileId == _dataFileId)
638 && (dataSize == _dataSize)
639 && (dataNumDims == _dataNumDims)
640 && (dataElemSize == _dataElemSize)
641 && (dataElemRealSize == _dataElemRealSize)
642 && (dataMaxNodes == _dataMaxNodes)
643 && (dataMinNodes == _dataMinNodes)
647 result = LoadRec(m_root, a_stream);
655 bool RTREE_QUAL::LoadRec(
Node* a_node, RTFileStream& a_stream)
657 a_stream.Read(a_node->m_level);
658 a_stream.Read(a_node->m_count);
660 if(a_node->IsInternalNode())
662 for(
int index = 0; index < a_node->m_count; ++index)
664 Branch* curBranch = &a_node->m_branch[index];
666 a_stream.ReadArray(curBranch->m_rect.m_min, NUMDIMS);
667 a_stream.ReadArray(curBranch->m_rect.m_max, NUMDIMS);
669 curBranch->m_child = AllocNode();
670 LoadRec(curBranch->m_child, a_stream);
675 for(
int index = 0; index < a_node->m_count; ++index)
677 Branch* curBranch = &a_node->m_branch[index];
679 a_stream.ReadArray(curBranch->m_rect.m_min, NUMDIMS);
680 a_stream.ReadArray(curBranch->m_rect.m_max, NUMDIMS);
682 a_stream.Read(curBranch->m_data);
691 bool RTREE_QUAL::Save(
const char* a_fileName)
694 if(!stream.OpenWrite(a_fileName))
699 bool result = Save(stream);
708 bool RTREE_QUAL::Save(RTFileStream& a_stream)
711 int dataFileId = (
'R'<<0)|(
'T'<<8)|(
'R'<<16)|(
'E'<<24);
712 int dataSize =
sizeof(DATATYPE);
713 int dataNumDims = NUMDIMS;
714 int dataElemSize =
sizeof(ELEMTYPE);
715 int dataElemRealSize =
sizeof(ELEMTYPEREAL);
716 int dataMaxNodes = TMAXNODES;
717 int dataMinNodes = TMINNODES;
719 a_stream.Write(dataFileId);
720 a_stream.Write(dataSize);
721 a_stream.Write(dataNumDims);
722 a_stream.Write(dataElemSize);
723 a_stream.Write(dataElemRealSize);
724 a_stream.Write(dataMaxNodes);
725 a_stream.Write(dataMinNodes);
728 bool result = SaveRec(m_root, a_stream);
735 bool RTREE_QUAL::SaveRec(
Node* a_node, RTFileStream& a_stream)
737 a_stream.Write(a_node->m_level);
738 a_stream.Write(a_node->m_count);
740 if(a_node->IsInternalNode())
742 for(
int index = 0; index < a_node->m_count; ++index)
744 Branch* curBranch = &a_node->m_branch[index];
746 a_stream.WriteArray(curBranch->m_rect.m_min, NUMDIMS);
747 a_stream.WriteArray(curBranch->m_rect.m_max, NUMDIMS);
749 SaveRec(curBranch->m_child, a_stream);
754 for(
int index = 0; index < a_node->m_count; ++index)
756 Branch* curBranch = &a_node->m_branch[index];
758 a_stream.WriteArray(curBranch->m_rect.m_min, NUMDIMS);
759 a_stream.WriteArray(curBranch->m_rect.m_max, NUMDIMS);
761 a_stream.Write(curBranch->m_data);
771 void RTREE_QUAL::RemoveAll()
776 m_root = AllocNode();
782 void RTREE_QUAL::Reset()
784 #ifdef RTREE_DONT_USE_MEMPOOLS
786 RemoveAllRec(m_root);
795 void RTREE_QUAL::RemoveAllRec(
Node* a_node)
798 ASSERT(a_node->m_level >= 0);
800 if(a_node->IsInternalNode())
802 for(
int index=0; index < a_node->m_count; ++index)
804 RemoveAllRec(a_node->m_branch[index].m_child);
812 typename RTREE_QUAL::Node* RTREE_QUAL::AllocNode()
815 #ifdef RTREE_DONT_USE_MEMPOOLS
826 void RTREE_QUAL::FreeNode(
Node* a_node)
830 #ifdef RTREE_DONT_USE_MEMPOOLS
841 typename RTREE_QUAL::ListNode* RTREE_QUAL::AllocListNode()
843 #ifdef RTREE_DONT_USE_MEMPOOLS
852 void RTREE_QUAL::FreeListNode(ListNode* a_listNode)
854 #ifdef RTREE_DONT_USE_MEMPOOLS
863 void RTREE_QUAL::InitNode(
Node* a_node)
866 a_node->m_level = -1;
871 void RTREE_QUAL::InitRect(Rect* a_rect)
873 for(
int index = 0; index < NUMDIMS; ++index)
875 a_rect->m_min[index] = (ELEMTYPE)0;
876 a_rect->m_max[index] = (ELEMTYPE)0;
889 bool RTREE_QUAL::InsertRectRec(Rect* a_rect,
const DATATYPE& a_id,
Node* a_node,
Node** a_newNode,
int a_level)
891 ASSERT(a_rect && a_node && a_newNode);
892 ASSERT(a_level >= 0 && a_level <= a_node->m_level);
899 if(a_node->m_level > a_level)
901 index = PickBranch(a_rect, a_node);
902 if (!InsertRectRec(a_rect, a_id, a_node->m_branch[index].m_child, &otherNode, a_level))
905 a_node->m_branch[index].m_rect = CombineRect(a_rect, &(a_node->m_branch[index].m_rect));
910 a_node->m_branch[index].m_rect = NodeCover(a_node->m_branch[index].m_child);
911 branch.m_child = otherNode;
912 branch.m_rect = NodeCover(otherNode);
913 return AddBranch(&branch, a_node, a_newNode);
916 else if(a_node->m_level == a_level)
918 branch.m_rect = *a_rect;
919 branch.m_child = (
Node*) a_id;
921 return AddBranch(&branch, a_node, a_newNode);
940 bool RTREE_QUAL::InsertRect(Rect* a_rect,
const DATATYPE& a_id,
Node** a_root,
int a_level)
943 ASSERT(a_level >= 0 && a_level <= (*a_root)->m_level);
945 for(
int index=0; index < NUMDIMS; ++index)
947 ASSERT(a_rect->m_min[index] <= a_rect->m_max[index]);
955 if(InsertRectRec(a_rect, a_id, *a_root, &newNode, a_level))
957 newRoot = AllocNode();
958 newRoot->m_level = (*a_root)->m_level + 1;
959 branch.m_rect = NodeCover(*a_root);
960 branch.m_child = *a_root;
961 AddBranch(&branch, newRoot, NULL);
962 branch.m_rect = NodeCover(newNode);
963 branch.m_child = newNode;
964 AddBranch(&branch, newRoot, NULL);
975 typename RTREE_QUAL::Rect RTREE_QUAL::NodeCover(
Node* a_node)
979 int firstTime =
true;
983 for(
int index = 0; index < a_node->m_count; ++index)
987 rect = a_node->m_branch[index].m_rect;
992 rect = CombineRect(&rect, &(a_node->m_branch[index].m_rect));
1005 bool RTREE_QUAL::AddBranch(Branch* a_branch,
Node* a_node,
Node** a_newNode)
1010 if(a_node->m_count < MAXNODES)
1012 a_node->m_branch[a_node->m_count] = *a_branch;
1021 SplitNode(a_node, a_branch, a_newNode);
1030 void RTREE_QUAL::DisconnectBranch(
Node* a_node,
int a_index)
1032 ASSERT(a_node && (a_index >= 0) && (a_index < MAXNODES));
1033 ASSERT(a_node->m_count > 0);
1036 a_node->m_branch[a_index] = a_node->m_branch[a_node->m_count - 1];
1048 int RTREE_QUAL::PickBranch(Rect* a_rect,
Node* a_node)
1050 ASSERT(a_rect && a_node);
1052 bool firstTime =
true;
1053 ELEMTYPEREAL increase;
1054 ELEMTYPEREAL bestIncr = (ELEMTYPEREAL)-1;
1056 ELEMTYPEREAL bestArea = 0;
1060 for(
int index=0; index < a_node->m_count; ++index)
1062 Rect* curRect = &a_node->m_branch[index].m_rect;
1063 area = CalcRectVolume(curRect);
1064 tempRect = CombineRect(a_rect, curRect);
1065 increase = CalcRectVolume(&tempRect) - area;
1066 if((increase < bestIncr) || firstTime)
1070 bestIncr = increase;
1073 else if((increase == bestIncr) && (area < bestArea))
1077 bestIncr = increase;
1086 typename RTREE_QUAL::Rect RTREE_QUAL::CombineRect(Rect* a_rectA, Rect* a_rectB)
1088 ASSERT(a_rectA && a_rectB);
1092 for(
int index = 0; index < NUMDIMS; ++index)
1094 newRect.m_min[index] =
rtree_min(a_rectA->m_min[index], a_rectB->m_min[index]);
1095 newRect.m_max[index] =
rtree_max(a_rectA->m_max[index], a_rectB->m_max[index]);
1108 void RTREE_QUAL::SplitNode(
Node* a_node, Branch* a_branch,
Node** a_newNode)
1114 PartitionVars localVars;
1115 PartitionVars* parVars = &localVars;
1119 level = a_node->m_level;
1120 GetBranches(a_node, a_branch, parVars);
1123 ChoosePartition(parVars, MINNODES);
1126 *a_newNode = AllocNode();
1127 (*a_newNode)->m_level = a_node->m_level = level;
1128 LoadNodes(a_node, *a_newNode, parVars);
1130 ASSERT((a_node->m_count + (*a_newNode)->m_count) == parVars->m_total);
1136 ELEMTYPEREAL RTREE_QUAL::RectVolume(Rect* a_rect)
1140 ELEMTYPEREAL volume = (ELEMTYPEREAL)1;
1142 for(
int index=0; index<NUMDIMS; ++index)
1144 volume *= a_rect->m_max[index] - a_rect->m_min[index];
1147 ASSERT(volume >= (ELEMTYPEREAL)0);
1155 ELEMTYPEREAL RTREE_QUAL::RectSphericalVolume(Rect* a_rect)
1159 ELEMTYPEREAL sumOfSquares = (ELEMTYPEREAL)0;
1160 ELEMTYPEREAL radius;
1162 for(
int index=0; index < NUMDIMS; ++index)
1164 ELEMTYPEREAL halfExtent = ((ELEMTYPEREAL)a_rect->m_max[index] - (ELEMTYPEREAL)a_rect->m_min[index]) * 0.5f;
1165 sumOfSquares += halfExtent * halfExtent;
1168 radius = (ELEMTYPEREAL)sqrt(sumOfSquares);
1173 return (radius * radius * radius * m_unitSphereVolume);
1175 else if(NUMDIMS == 2)
1177 return (radius * radius * m_unitSphereVolume);
1181 return (ELEMTYPEREAL)(pow(radius, NUMDIMS) * m_unitSphereVolume);
1188 ELEMTYPEREAL RTREE_QUAL::CalcRectVolume(Rect* a_rect)
1190 #ifdef RTREE_USE_SPHERICAL_VOLUME
1191 return RectSphericalVolume(a_rect);
1193 return RectVolume(a_rect);
1200 void RTREE_QUAL::GetBranches(
Node* a_node, Branch* a_branch, PartitionVars* a_parVars)
1205 ASSERT(a_node->m_count == MAXNODES);
1209 for(index=0; index < MAXNODES; ++index)
1211 a_parVars->m_branchBuf[index] = a_node->m_branch[index];
1213 a_parVars->m_branchBuf[MAXNODES] = *a_branch;
1214 a_parVars->m_branchCount = MAXNODES + 1;
1217 a_parVars->m_coverSplit = a_parVars->m_branchBuf[0].m_rect;
1218 for(index=1; index < MAXNODES+1; ++index)
1220 a_parVars->m_coverSplit = CombineRect(&a_parVars->m_coverSplit, &a_parVars->m_branchBuf[index].m_rect);
1222 a_parVars->m_coverSplitArea = CalcRectVolume(&a_parVars->m_coverSplit);
1240 void RTREE_QUAL::ChoosePartition(PartitionVars* a_parVars,
int a_minFill)
1244 ELEMTYPEREAL biggestDiff;
1245 int group, chosen = 0, betterGroup = 0;
1247 InitParVars(a_parVars, a_parVars->m_branchCount, a_minFill);
1248 PickSeeds(a_parVars);
1250 while (((a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total)
1251 && (a_parVars->m_count[0] < (a_parVars->m_total - a_parVars->m_minFill))
1252 && (a_parVars->m_count[1] < (a_parVars->m_total - a_parVars->m_minFill)))
1254 biggestDiff = (ELEMTYPEREAL) -1;
1255 for(
int index=0; index<a_parVars->m_total; ++index)
1257 if(!a_parVars->m_taken[index])
1259 Rect* curRect = &a_parVars->m_branchBuf[index].m_rect;
1260 Rect rect0 = CombineRect(curRect, &a_parVars->m_cover[0]);
1261 Rect rect1 = CombineRect(curRect, &a_parVars->m_cover[1]);
1262 ELEMTYPEREAL growth0 = CalcRectVolume(&rect0) - a_parVars->m_area[0];
1263 ELEMTYPEREAL growth1 = CalcRectVolume(&rect1) - a_parVars->m_area[1];
1264 ELEMTYPEREAL diff = growth1 - growth0;
1275 if(diff > biggestDiff)
1279 betterGroup = group;
1281 else if((diff == biggestDiff) && (a_parVars->m_count[group] < a_parVars->m_count[betterGroup]))
1284 betterGroup = group;
1288 Classify(chosen, betterGroup, a_parVars);
1292 if((a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total)
1294 if(a_parVars->m_count[0] >= a_parVars->m_total - a_parVars->m_minFill)
1302 for(
int index=0; index<a_parVars->m_total; ++index)
1304 if(!a_parVars->m_taken[index])
1306 Classify(index, group, a_parVars);
1311 ASSERT((a_parVars->m_count[0] + a_parVars->m_count[1]) == a_parVars->m_total);
1312 ASSERT((a_parVars->m_count[0] >= a_parVars->m_minFill) &&
1313 (a_parVars->m_count[1] >= a_parVars->m_minFill));
1319 void RTREE_QUAL::LoadNodes(
Node* a_nodeA,
Node* a_nodeB, PartitionVars* a_parVars)
1325 for(
int index=0; index < a_parVars->m_total; ++index)
1327 ASSERT(a_parVars->m_partition[index] == 0 || a_parVars->m_partition[index] == 1);
1329 if(a_parVars->m_partition[index] == 0)
1331 AddBranch(&a_parVars->m_branchBuf[index], a_nodeA, NULL);
1333 else if(a_parVars->m_partition[index] == 1)
1335 AddBranch(&a_parVars->m_branchBuf[index], a_nodeB, NULL);
1343 void RTREE_QUAL::InitParVars(PartitionVars* a_parVars,
int a_maxRects,
int a_minFill)
1347 a_parVars->m_count[0] = a_parVars->m_count[1] = 0;
1348 a_parVars->m_area[0] = a_parVars->m_area[1] = (ELEMTYPEREAL)0;
1349 a_parVars->m_total = a_maxRects;
1350 a_parVars->m_minFill = a_minFill;
1351 for(
int index=0; index < a_maxRects; ++index)
1353 a_parVars->m_taken[index] =
false;
1354 a_parVars->m_partition[index] = -1;
1360 void RTREE_QUAL::PickSeeds(PartitionVars* a_parVars)
1362 int seed0=0, seed1=1;
1363 ELEMTYPEREAL worst, waste;
1364 ELEMTYPEREAL area[MAXNODES+1];
1366 for(
int index=0; index<a_parVars->m_total; ++index)
1368 area[index] = CalcRectVolume(&a_parVars->m_branchBuf[index].m_rect);
1371 worst = -a_parVars->m_coverSplitArea - 1;
1372 for(
int indexA=0; indexA < a_parVars->m_total-1; ++indexA)
1374 for(
int indexB = indexA+1; indexB < a_parVars->m_total; ++indexB)
1376 Rect oneRect = CombineRect(&a_parVars->m_branchBuf[indexA].m_rect, &a_parVars->m_branchBuf[indexB].m_rect);
1377 waste = CalcRectVolume(&oneRect) - area[indexA] - area[indexB];
1386 Classify(seed0, 0, a_parVars);
1387 Classify(seed1, 1, a_parVars);
1393 void RTREE_QUAL::Classify(
int a_index,
int a_group, PartitionVars* a_parVars)
1396 ASSERT(!a_parVars->m_taken[a_index]);
1398 a_parVars->m_partition[a_index] = a_group;
1399 a_parVars->m_taken[a_index] =
true;
1401 if (a_parVars->m_count[a_group] == 0)
1403 a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect;
1407 a_parVars->m_cover[a_group] = CombineRect(&a_parVars->m_branchBuf[a_index].m_rect, &a_parVars->m_cover[a_group]);
1409 a_parVars->m_area[a_group] = CalcRectVolume(&a_parVars->m_cover[a_group]);
1410 ++a_parVars->m_count[a_group];
1419 bool RTREE_QUAL::RemoveRect(Rect* a_rect,
const DATATYPE& a_id,
Node** a_root)
1421 ASSERT(a_rect && a_root);
1425 ListNode* reInsertList = NULL;
1427 if(!RemoveRectRec(a_rect, a_id, *a_root, &reInsertList))
1433 tempNode = reInsertList->m_node;
1435 for(
int index = 0; index < tempNode->m_count; ++index)
1437 InsertRect(&(tempNode->m_branch[index].m_rect),
1438 tempNode->m_branch[index].m_data,
1443 ListNode* remLNode = reInsertList;
1444 reInsertList = reInsertList->m_next;
1446 FreeNode(remLNode->m_node);
1447 FreeListNode(remLNode);
1451 if((*a_root)->m_count == 1 && (*a_root)->IsInternalNode())
1453 tempNode = (*a_root)->m_branch[0].m_child;
1473 bool RTREE_QUAL::RemoveRectRec(Rect* a_rect,
const DATATYPE& a_id,
Node* a_node, ListNode** a_listNode)
1475 ASSERT(a_rect && a_node && a_listNode);
1476 ASSERT(a_node->m_level >= 0);
1478 if(a_node->IsInternalNode())
1480 for(
int index = 0; index < a_node->m_count; ++index)
1482 if(Overlap(a_rect, &(a_node->m_branch[index].m_rect)))
1484 if(!RemoveRectRec(a_rect, a_id, a_node->m_branch[index].m_child, a_listNode))
1486 if(a_node->m_branch[index].m_child->m_count >= MINNODES)
1489 a_node->m_branch[index].m_rect = NodeCover(a_node->m_branch[index].m_child);
1494 ReInsert(a_node->m_branch[index].m_child, a_listNode);
1495 DisconnectBranch(a_node, index);
1505 for(
int index = 0; index < a_node->m_count; ++index)
1507 if(a_node->m_branch[index].m_child == (
Node*)a_id)
1509 DisconnectBranch(a_node, index);
1520 bool RTREE_QUAL::Overlap(Rect* a_rectA, Rect* a_rectB)
const
1522 ASSERT(a_rectA && a_rectB);
1524 for(
int index=0; index < NUMDIMS; ++index)
1526 if (a_rectA->m_min[index] > a_rectB->m_max[index] ||
1527 a_rectB->m_min[index] > a_rectA->m_max[index])
1539 void RTREE_QUAL::ReInsert(
Node* a_node, ListNode** a_listNode)
1541 ListNode* newListNode;
1543 newListNode = AllocListNode();
1544 newListNode->m_node = a_node;
1545 newListNode->m_next = *a_listNode;
1546 *a_listNode = newListNode;
1553 bool RTREE_QUAL::Search(
Node* a_node, Rect* a_rect,
int& a_foundCount,
const CONTEXT &c)
const
1556 ASSERT(a_node->m_level >= 0);
1559 if(a_node->IsInternalNode())
1561 for(
int index=0; index < a_node->m_count; ++index)
1563 if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
1565 if(!Search(a_node->m_branch[index].m_child, a_rect, a_foundCount, c))
1574 for(
int index=0; index < a_node->m_count; ++index)
1576 if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
1578 DATATYPE&
id = a_node->m_branch[index].m_data;
1584 (
id->*myOperation)(c);
1602 #undef RTREE_TEMPLATE
Iterator is not remove safe.
StackElement m_stack[MAX_STACK]
Stack as we are doing iteration instead of recursion.
DATATYPE & operator*()
Access the current data element. Caller must be sure iterator is not NULL first.
StackElement & Pop()
Pop element off iteration stack (For internal use only)
bool IsNull()
Is iterator invalid.
void Init()
Reset iterator.
int m_tos
Top Of Stack index.
bool operator++()
Find the next data element.
const DATATYPE & operator*() const
Access the current data element. Caller must be sure iterator is not NULL first.
void Push(Node *a_node, int a_branchIndex)
Push node and branch onto iteration stack (For internal use only)
bool FindNextData()
Find the next data element in the tree (For internal use only)
bool IsNotNull()
Is iterator pointing to valid data.
ListNode * AllocListNode()
ELEMTYPEREAL m_unitSphereVolume
Unit sphere constant for required number of dimensions.
virtual void Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
void SplitNode(Node *a_node, Branch *a_branch, Node **a_newNode)
void RemoveAll()
DK 15.10.2008 - end.
ELEMTYPEREAL CalcRectVolume(Rect *a_rect)
bool Search(Node *a_node, Rect *a_rect, int &a_foundCount, const CONTEXT &c) const
ELEMTYPEREAL RectSphericalVolume(Rect *a_rect)
bool InsertRect(Rect *a_rect, const DATATYPE &a_id, Node **a_root, int a_level)
void DisconnectBranch(Node *a_node, int a_index)
@ MINNODES
Min elements in node.
@ MAXNODES
Max elements in node.
void InitRect(Rect *a_rect)
bool AddBranch(Branch *a_branch, Node *a_node, Node **a_newNode)
bool InsertRectRec(Rect *a_rect, const DATATYPE &a_id, Node *a_node, Node **a_newNode, int a_level)
void FreeListNode(ListNode *a_listNode)
int Count()
Count the data elements in this container. This is slow as no internal counter is maintained.
int PickBranch(Rect *a_rect, Node *a_node)
RTree(Operation operation)
bool RemoveRect(Rect *a_rect, const DATATYPE &a_id, Node **a_root)
void FreeNode(Node *a_node)
void InitNode(Node *a_node)
DATATYPE & GetAt(Iterator &a_it)
Get object at iterator position.
virtual int Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const CONTEXT &c) const
DK 15.10.2008 - begin.
void GetNext(Iterator &a_it)
Get Next for iteration.
void CountRec(Node *a_node, int &a_count)
void GetFirst(Iterator &a_it)
Get 'first' for iteration.
void Classify(int a_index, int a_group, PartitionVars *a_parVars)
void RemoveAllRec(Node *a_node)
ELEMTYPEREAL RectVolume(Rect *a_rect)
void PickSeeds(PartitionVars *a_parVars)
void GetBranches(Node *a_node, Branch *a_branch, PartitionVars *a_parVars)
void ReInsert(Node *a_node, ListNode **a_listNode)
void ChoosePartition(PartitionVars *a_parVars, int a_minFill)
virtual void Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
bool RemoveRectRec(Rect *a_rect, const DATATYPE &a_id, Node *a_node, ListNode **a_listNode)
void LoadNodes(Node *a_nodeA, Node *a_nodeB, PartitionVars *a_parVars)
Rect CombineRect(Rect *a_rectA, Rect *a_rectB)
void InitParVars(PartitionVars *a_parVars, int a_maxRects, int a_minFill)
void(DATATYPENP::* Operation)(const CONTEXT &) const
bool IsNull(Iterator &a_it)
Is iterator NULL, or at end?
Rect NodeCover(Node *a_node)
bool Overlap(Rect *a_rectA, Rect *a_rectB) const
Node * m_root
Root of tree.
DATATYPE m_data
Data Id or Ptr.
Node * m_child
Child node.
A link list of nodes for reinsertion after a delete operation.
ListNode * m_next
Next in list.
Node for each branch level.
Branch m_branch[MAXNODES]
Branch.
bool IsInternalNode() const
int m_level
Leaf is zero, others positive.
Variables for finding a split partition.
int m_partition[MAXNODES+1]
Branch m_branchBuf[MAXNODES+1]
ELEMTYPEREAL m_coverSplitArea
Minimal bounding rectangle (n-dimensional)
ELEMTYPE m_max[NUMDIMS]
Max dimensions of bounding box.
ELEMTYPE m_min[NUMDIMS]
Min dimensions of bounding box.