13 #define ASSERT assert // RTree uses ASSERT( condition )
21 #define RTREE_TEMPLATE template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>
22 #define RTREE_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES>
24 #define RTREE_DONT_USE_MEMPOOLS // This version does not contain a fixed memory allocator, fill in lines with EXAMPLE to implement one.
25 #define RTREE_USE_SPHERICAL_VOLUME // Better split classification, may be slower on some systems
47 template<
class DATATYPE,
class ELEMTYPE,
int NUMDIMS,
48 class ELEMTYPEREAL = ELEMTYPE,
int TMAXNODES = 8,
int TMINNODES = TMAXNODES / 2>
75 void Insert(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE& a_dataId);
81 void Remove(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE& a_dataId);
90 int Search(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
bool __cdecl a_resultCallback(DATATYPE a_data,
void* a_context),
void* a_context);
99 bool Load(
const char* a_fileName);
105 bool Save(
const char* a_fileName);
114 enum { MAX_STACK = 32 };
147 StackElement& curTos = m_stack[m_tos - 1];
148 return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
155 StackElement& curTos = m_stack[m_tos - 1];
156 return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
162 return FindNextData();
166 void GetBounds(ELEMTYPE a_min[NUMDIMS], ELEMTYPE a_max[NUMDIMS])
169 StackElement& curTos = m_stack[m_tos - 1];
170 Branch& curBranch = curTos.m_node->m_branch[curTos.m_branchIndex];
172 for (
int index = 0; index < NUMDIMS; ++index)
196 StackElement curTos = Pop();
198 if (curTos.m_node->IsLeaf())
201 if (curTos.m_branchIndex+1 < curTos.m_node->m_count)
204 Push(curTos.m_node, curTos.m_branchIndex + 1);
211 if (curTos.m_branchIndex+1 < curTos.m_node->m_count)
215 Push(curTos.m_node, curTos.m_branchIndex + 1);
218 Node* nextLevelnode = curTos.m_node->m_branch[curTos.m_branchIndex].m_child;
219 Push(nextLevelnode, 0);
222 if (nextLevelnode->IsLeaf())
231 void Push(Node* a_node,
int a_branchIndex)
233 m_stack[m_tos].m_node = a_node;
234 m_stack[m_tos].m_branchIndex = a_branchIndex;
236 ASSERT(m_tos <= MAX_STACK);
244 return m_stack[m_tos];
247 StackElement m_stack[MAX_STACK];
260 if (first->IsInternalNode() && first->m_count > 1)
264 else if (first->IsLeaf())
285 return a_it.IsNull();
319 bool IsInternalNode()
349 ELEMTYPEREAL m_area[2];
354 ELEMTYPEREAL m_coverSplitArea;
358 void FreeNode(
Node* a_node);
359 void InitNode(
Node* a_node);
360 void InitRect(
Rect* a_rect);
361 bool InsertRectRec(
Rect* a_rect,
const DATATYPE& a_id,
Node* a_node,
Node** a_newNode,
int a_level);
362 bool InsertRect(
Rect* a_rect,
const DATATYPE& a_id,
Node** a_root,
int a_level);
365 void DisconnectBranch(
Node* a_node,
int a_index);
366 int PickBranch(
Rect* a_rect,
Node* a_node);
369 ELEMTYPEREAL RectSphericalVolume(
Rect* a_rect);
370 ELEMTYPEREAL RectVolume(
Rect* a_rect);
371 ELEMTYPEREAL CalcRectVolume(
Rect* a_rect);
373 void ChoosePartition(
PartitionVars* a_parVars,
int a_minFill);
375 void InitParVars(
PartitionVars* a_parVars,
int a_maxRects,
int a_minFill);
377 void Classify(
int a_index,
int a_group,
PartitionVars* a_parVars);
378 bool RemoveRect(
Rect* a_rect,
const DATATYPE& a_id,
Node** a_root);
379 bool RemoveRectRec(
Rect* a_rect,
const DATATYPE& a_id,
Node* a_node,
ListNode** a_listNode);
381 void FreeListNode(
ListNode* a_listNode);
382 bool Overlap(
Rect* a_rectA,
Rect* a_rectB);
384 bool Search(
Node* a_node,
Rect* a_rect,
int& a_foundCount,
bool __cdecl a_resultCallback(DATATYPE a_data,
void* a_context),
void* a_context);
385 void RemoveAllRec(
Node* a_node);
387 void CountRec(
Node* a_node,
int& a_count);
416 bool OpenRead(
const char* a_fileName)
418 if (fopen_s(&m_file, a_fileName,
"rb") != 0)
429 bool OpenWrite(
const char* a_fileName)
431 if (fopen_s(&m_file, a_fileName,
"wb") != 0)
451 template<
typename TYPE >
452 size_t Write(
const TYPE& a_value)
455 return fwrite((
void*)&a_value,
sizeof(a_value), 1, m_file);
458 template<
typename TYPE >
459 size_t WriteArray(
const TYPE* a_array,
int a_count)
462 return fwrite((
void*)a_array,
sizeof(TYPE) * a_count, 1, m_file);
465 template<
typename TYPE >
466 size_t Read(TYPE& a_value)
469 return fread((
void*)&a_value,
sizeof(a_value), 1, m_file);
472 template<
typename TYPE >
473 size_t ReadArray(TYPE* a_array,
int a_count)
476 return fread((
void*)a_array,
sizeof(TYPE) * a_count, 1, m_file);
484 ASSERT(MAXNODES > MINNODES);
485 ASSERT(MINNODES > 0);
490 ASSERT(
sizeof(DATATYPE) ==
sizeof(
void*) ||
sizeof(DATATYPE) ==
sizeof(
int));
493 const float UNIT_SPHERE_VOLUMES[] =
495 0.000000f, 2.000000f, 3.141593f,
496 4.188790f, 4.934802f, 5.263789f,
497 5.167713f, 4.724766f, 4.058712f,
498 3.298509f, 2.550164f, 1.884104f,
499 1.335263f, 0.910629f, 0.599265f,
500 0.381443f, 0.235331f, 0.140981f,
501 0.082146f, 0.046622f, 0.025807f,
504 m_root = AllocNode();
506 m_unitSphereVolume = (ELEMTYPEREAL)UNIT_SPHERE_VOLUMES[NUMDIMS];
518 void RTREE_QUAL::Insert(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE& a_dataId)
521 for (
int index=0; index<NUMDIMS; ++index)
523 ASSERT(a_min[index] <= a_max[index]);
529 for (
int axis=0; axis<NUMDIMS; ++axis)
531 rect.m_min[axis] = a_min[axis];
532 rect.m_max[axis] = a_max[axis];
535 InsertRect(&rect, a_dataId, &m_root, 0);
540 void RTREE_QUAL::Remove(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE& a_dataId)
543 for (
int index=0; index<NUMDIMS; ++index)
545 ASSERT(a_min[index] <= a_max[index]);
551 for (
int axis=0; axis<NUMDIMS; ++axis)
553 rect.m_min[axis] = a_min[axis];
554 rect.m_max[axis] = a_max[axis];
557 RemoveRect(&rect, a_dataId, &m_root);
562 int RTREE_QUAL::Search(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
bool __cdecl a_resultCallback(DATATYPE a_data,
void* a_context),
566 for (
int index=0; index<NUMDIMS; ++index)
568 ASSERT(a_min[index] <= a_max[index]);
574 for (
int axis=0; axis<NUMDIMS; ++axis)
576 rect.m_min[axis] = a_min[axis];
577 rect.m_max[axis] = a_max[axis];
583 Search(m_root, &rect, foundCount, a_resultCallback, a_context);
590 int RTREE_QUAL::Count()
593 CountRec(m_root, count);
601 void RTREE_QUAL::CountRec(Node* a_node,
int& a_count)
603 if (a_node->IsInternalNode())
605 for (
int index = 0; index < a_node->m_count; ++index)
607 CountRec(a_node->m_branch[index].m_child, a_count);
612 a_count += a_node->m_count;
618 bool RTREE_QUAL::Load(
const char* a_fileName)
623 if (!stream.OpenRead(a_fileName))
628 bool result = Load(stream);
638 bool RTREE_QUAL::Load(RTFileStream& a_stream)
641 int _dataFileId = (
'R'<<0)|(
'T'<<8)|(
'R'<<16)|(
'E'<<24);
642 int _dataSize =
sizeof(DATATYPE);
643 int _dataNumDims = NUMDIMS;
644 int _dataElemSize =
sizeof(ELEMTYPE);
645 int _dataElemRealSize =
sizeof(ELEMTYPEREAL);
646 int _dataMaxNodes = TMAXNODES;
647 int _dataMinNodes = TMINNODES;
652 int dataElemSize = 0;
653 int dataElemRealSize = 0;
654 int dataMaxNodes = 0;
655 int dataMinNodes = 0;
657 a_stream.Read(dataFileId);
658 a_stream.Read(dataSize);
659 a_stream.Read(dataNumDims);
660 a_stream.Read(dataElemSize);
661 a_stream.Read(dataElemRealSize);
662 a_stream.Read(dataMaxNodes);
663 a_stream.Read(dataMinNodes);
668 if ((dataFileId == _dataFileId)
669 && (dataSize == _dataSize)
670 && (dataNumDims == _dataNumDims)
671 && (dataElemSize == _dataElemSize)
672 && (dataElemRealSize == _dataElemRealSize)
673 && (dataMaxNodes == _dataMaxNodes)
674 && (dataMinNodes == _dataMinNodes)
678 result = LoadRec(m_root, a_stream);
686 bool RTREE_QUAL::LoadRec(Node* a_node, RTFileStream& a_stream)
688 a_stream.Read(a_node->m_level);
689 a_stream.Read(a_node->m_count);
691 if (a_node->IsInternalNode())
693 for (
int index = 0; index < a_node->m_count; ++index)
695 Branch* curBranch = &a_node->m_branch[index];
697 a_stream.ReadArray(curBranch->m_rect.m_min, NUMDIMS);
698 a_stream.ReadArray(curBranch->m_rect.m_max, NUMDIMS);
700 curBranch->m_child = AllocNode();
701 LoadRec(curBranch->m_child, a_stream);
706 for (
int index = 0; index < a_node->m_count; ++index)
708 Branch* curBranch = &a_node->m_branch[index];
710 a_stream.ReadArray(curBranch->m_rect.m_min, NUMDIMS);
711 a_stream.ReadArray(curBranch->m_rect.m_max, NUMDIMS);
713 a_stream.Read(curBranch->m_data);
722 bool RTREE_QUAL::Save(
const char* a_fileName)
725 if (!stream.OpenWrite(a_fileName))
730 bool result = Save(stream);
739 bool RTREE_QUAL::Save(RTFileStream& a_stream)
742 int dataFileId = (
'R'<<0)|(
'T'<<8)|(
'R'<<16)|(
'E'<<24);
743 int dataSize =
sizeof(DATATYPE);
744 int dataNumDims = NUMDIMS;
745 int dataElemSize =
sizeof(ELEMTYPE);
746 int dataElemRealSize =
sizeof(ELEMTYPEREAL);
747 int dataMaxNodes = TMAXNODES;
748 int dataMinNodes = TMINNODES;
750 a_stream.Write(dataFileId);
751 a_stream.Write(dataSize);
752 a_stream.Write(dataNumDims);
753 a_stream.Write(dataElemSize);
754 a_stream.Write(dataElemRealSize);
755 a_stream.Write(dataMaxNodes);
756 a_stream.Write(dataMinNodes);
759 bool result = SaveRec(m_root, a_stream);
766 bool RTREE_QUAL::SaveRec(Node* a_node, RTFileStream& a_stream)
768 a_stream.Write(a_node->m_level);
769 a_stream.Write(a_node->m_count);
771 if (a_node->IsInternalNode())
773 for (
int index = 0; index < a_node->m_count; ++index)
775 Branch* curBranch = &a_node->m_branch[index];
777 a_stream.WriteArray(curBranch->m_rect.m_min, NUMDIMS);
778 a_stream.WriteArray(curBranch->m_rect.m_max, NUMDIMS);
780 SaveRec(curBranch->m_child, a_stream);
785 for (
int index = 0; index < a_node->m_count; ++index)
787 Branch* curBranch = &a_node->m_branch[index];
789 a_stream.WriteArray(curBranch->m_rect.m_min, NUMDIMS);
790 a_stream.WriteArray(curBranch->m_rect.m_max, NUMDIMS);
792 a_stream.Write(curBranch->m_data);
801 void RTREE_QUAL::RemoveAll()
806 m_root = AllocNode();
812 void RTREE_QUAL::Reset()
814 #ifdef RTREE_DONT_USE_MEMPOOLS
816 RemoveAllRec(m_root);
817 #else // RTREE_DONT_USE_MEMPOOLS
820 #endif // RTREE_DONT_USE_MEMPOOLS
825 void RTREE_QUAL::RemoveAllRec(Node* a_node)
828 ASSERT(a_node->m_level >= 0);
830 if (a_node->IsInternalNode())
832 for (
int index=0; index < a_node->m_count; ++index)
834 RemoveAllRec(a_node->m_branch[index].m_child);
842 typename RTREE_QUAL::Node* RTREE_QUAL::AllocNode()
845 #ifdef RTREE_DONT_USE_MEMPOOLS
846 newNode = VF_NEW Node;
847 #else // RTREE_DONT_USE_MEMPOOLS
849 #endif // RTREE_DONT_USE_MEMPOOLS
856 void RTREE_QUAL::FreeNode(Node* a_node)
860 #ifdef RTREE_DONT_USE_MEMPOOLS
862 #else // RTREE_DONT_USE_MEMPOOLS
864 #endif // RTREE_DONT_USE_MEMPOOLS
871 typename RTREE_QUAL::ListNode* RTREE_QUAL::AllocListNode()
873 #ifdef RTREE_DONT_USE_MEMPOOLS
874 return VF_NEW ListNode;
875 #else // RTREE_DONT_USE_MEMPOOLS
877 #endif // RTREE_DONT_USE_MEMPOOLS
882 void RTREE_QUAL::FreeListNode(ListNode* a_listNode)
884 #ifdef RTREE_DONT_USE_MEMPOOLS
885 VF_DELETE a_listNode;
886 #else // RTREE_DONT_USE_MEMPOOLS
888 #endif // RTREE_DONT_USE_MEMPOOLS
893 void RTREE_QUAL::InitNode(Node* a_node)
896 a_node->m_level = -1;
901 void RTREE_QUAL::InitRect(Rect* a_rect)
903 for (
int index = 0; index < NUMDIMS; ++index)
905 a_rect->m_min[index] = (ELEMTYPE)0;
906 a_rect->m_max[index] = (ELEMTYPE)0;
919 bool RTREE_QUAL::InsertRectRec(Rect* a_rect,
const DATATYPE& a_id, Node* a_node, Node** a_newNode,
int a_level)
921 ASSERT(a_rect && a_node && a_newNode);
922 ASSERT(a_level >= 0 && a_level <= a_node->m_level);
929 if (a_node->m_level > a_level)
931 index = PickBranch(a_rect, a_node);
932 if (!InsertRectRec(a_rect, a_id, a_node->m_branch[index].m_child, &otherNode, a_level))
935 a_node->m_branch[index].m_rect = CombineRect(a_rect, &(a_node->m_branch[index].m_rect));
940 a_node->m_branch[index].m_rect = NodeCover(a_node->m_branch[index].m_child);
941 branch.m_child = otherNode;
942 branch.m_rect = NodeCover(otherNode);
943 return AddBranch(&branch, a_node, a_newNode);
946 else if (a_node->m_level == a_level)
948 branch.m_rect = *a_rect;
949 branch.m_child = (Node*) a_id;
951 return AddBranch(&branch, a_node, a_newNode);
970 bool RTREE_QUAL::InsertRect(Rect* a_rect,
const DATATYPE& a_id, Node** a_root,
int a_level)
972 ASSERT(a_rect && a_root);
973 ASSERT(a_level >= 0 && a_level <= (*a_root)->m_level);
975 for (
int index=0; index < NUMDIMS; ++index)
977 ASSERT(a_rect->m_min[index] <= a_rect->m_max[index]);
985 if (InsertRectRec(a_rect, a_id, *a_root, &newNode, a_level))
987 newRoot = AllocNode();
988 newRoot->m_level = (*a_root)->m_level + 1;
989 branch.m_rect = NodeCover(*a_root);
990 branch.m_child = *a_root;
991 AddBranch(&branch, newRoot, NULL);
992 branch.m_rect = NodeCover(newNode);
993 branch.m_child = newNode;
994 AddBranch(&branch, newRoot, NULL);
1005 typename RTREE_QUAL::Rect RTREE_QUAL::NodeCover(Node* a_node)
1009 int firstTime =
true;
1013 for (
int index = 0; index < a_node->m_count; ++index)
1017 rect = a_node->m_branch[index].m_rect;
1022 rect = CombineRect(&rect, &(a_node->m_branch[index].m_rect));
1035 bool RTREE_QUAL::AddBranch(Branch* a_branch, Node* a_node, Node** a_newNode)
1040 if (a_node->m_count < MAXNODES)
1042 a_node->m_branch[a_node->m_count] = *a_branch;
1051 SplitNode(a_node, a_branch, a_newNode);
1060 void RTREE_QUAL::DisconnectBranch(Node* a_node,
int a_index)
1062 ASSERT(a_node && (a_index >= 0) && (a_index < MAXNODES));
1063 ASSERT(a_node->m_count > 0);
1066 a_node->m_branch[a_index] = a_node->m_branch[a_node->m_count - 1];
1078 int RTREE_QUAL::PickBranch(Rect* a_rect, Node* a_node)
1080 ASSERT(a_rect && a_node);
1082 bool firstTime =
true;
1083 ELEMTYPEREAL increase;
1084 ELEMTYPEREAL bestIncr = (ELEMTYPEREAL)-1;
1086 ELEMTYPEREAL bestArea;
1090 for (
int index=0; index < a_node->m_count; ++index)
1092 Rect* curRect = &a_node->m_branch[index].m_rect;
1093 area = CalcRectVolume(curRect);
1094 tempRect = CombineRect(a_rect, curRect);
1095 increase = CalcRectVolume(&tempRect) - area;
1096 if ((increase < bestIncr) || firstTime)
1100 bestIncr = increase;
1103 else if ((increase == bestIncr) && (area < bestArea))
1107 bestIncr = increase;
1116 typename RTREE_QUAL::Rect RTREE_QUAL::CombineRect(Rect* a_rectA, Rect* a_rectB)
1118 ASSERT(a_rectA && a_rectB);
1122 for (
int index = 0; index < NUMDIMS; ++index)
1124 newRect.m_min[index] = min(a_rectA->m_min[index], a_rectB->m_min[index]);
1125 newRect.m_max[index] = max(a_rectA->m_max[index], a_rectB->m_max[index]);
1138 void RTREE_QUAL::SplitNode(Node* a_node, Branch* a_branch, Node** a_newNode)
1144 PartitionVars localVars;
1145 PartitionVars* parVars = &localVars;
1149 level = a_node->m_level;
1150 GetBranches(a_node, a_branch, parVars);
1153 ChoosePartition(parVars, MINNODES);
1156 *a_newNode = AllocNode();
1157 (*a_newNode)->m_level = a_node->m_level = level;
1158 LoadNodes(a_node, *a_newNode, parVars);
1160 ASSERT((a_node->m_count + (*a_newNode)->m_count) == parVars->m_total);
1166 ELEMTYPEREAL RTREE_QUAL::RectVolume(Rect* a_rect)
1170 ELEMTYPEREAL volume = (ELEMTYPEREAL)1;
1172 for (
int index=0; index<NUMDIMS; ++index)
1174 volume *= a_rect->m_max[index] - a_rect->m_min[index];
1177 ASSERT(volume >= (ELEMTYPEREAL)0);
1185 ELEMTYPEREAL RTREE_QUAL::RectSphericalVolume(Rect* a_rect)
1189 ELEMTYPEREAL sumOfSquares = (ELEMTYPEREAL)0;
1190 ELEMTYPEREAL radius;
1192 for (
int index=0; index < NUMDIMS; ++index)
1194 ELEMTYPEREAL halfExtent = ((ELEMTYPEREAL)a_rect->m_max[index] - (ELEMTYPEREAL)a_rect->m_min[index]) * 0.5f;
1195 sumOfSquares += halfExtent * halfExtent;
1198 radius = (ELEMTYPEREAL)sqrt(sumOfSquares);
1203 return (radius * radius * radius * m_unitSphereVolume);
1205 else if (NUMDIMS == 2)
1207 return (radius * radius * m_unitSphereVolume);
1211 return (ELEMTYPEREAL)(pow(radius, NUMDIMS) * m_unitSphereVolume);
1218 ELEMTYPEREAL RTREE_QUAL::CalcRectVolume(Rect* a_rect)
1220 #ifdef RTREE_USE_SPHERICAL_VOLUME
1221 return RectSphericalVolume(a_rect);
1222 #else // RTREE_USE_SPHERICAL_VOLUME
1223 return RectVolume(a_rect);
1224 #endif // RTREE_USE_SPHERICAL_VOLUME
1230 void RTREE_QUAL::GetBranches(Node* a_node, Branch* a_branch, PartitionVars* a_parVars)
1235 ASSERT(a_node->m_count == MAXNODES);
1238 for (
int index=0; index < MAXNODES; ++index)
1240 a_parVars->m_branchBuf[index] = a_node->m_branch[index];
1242 a_parVars->m_branchBuf[MAXNODES] = *a_branch;
1243 a_parVars->m_branchCount = MAXNODES + 1;
1246 a_parVars->m_coverSplit = a_parVars->m_branchBuf[0].m_rect;
1247 for (
int index=1; index < MAXNODES+1; ++index)
1249 a_parVars->m_coverSplit = CombineRect(&a_parVars->m_coverSplit, &a_parVars->m_branchBuf[index].m_rect);
1251 a_parVars->m_coverSplitArea = CalcRectVolume(&a_parVars->m_coverSplit);
1269 void RTREE_QUAL::ChoosePartition(PartitionVars* a_parVars,
int a_minFill)
1273 ELEMTYPEREAL biggestDiff;
1274 int group, chosen, betterGroup;
1277 InitParVars(a_parVars, a_parVars->m_branchCount, a_minFill);
1278 PickSeeds(a_parVars);
1280 while (((a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total)
1281 && (a_parVars->m_count[0] < (a_parVars->m_total - a_parVars->m_minFill))
1282 && (a_parVars->m_count[1] < (a_parVars->m_total - a_parVars->m_minFill)))
1284 biggestDiff = (ELEMTYPEREAL) -1;
1285 for (
int index=0; index<a_parVars->m_total; ++index)
1287 if (!a_parVars->m_taken[index])
1289 Rect* curRect = &a_parVars->m_branchBuf[index].m_rect;
1290 Rect rect0 = CombineRect(curRect, &a_parVars->m_cover[0]);
1291 Rect rect1 = CombineRect(curRect, &a_parVars->m_cover[1]);
1292 ELEMTYPEREAL growth0 = CalcRectVolume(&rect0) - a_parVars->m_area[0];
1293 ELEMTYPEREAL growth1 = CalcRectVolume(&rect1) - a_parVars->m_area[1];
1294 ELEMTYPEREAL diff = growth1 - growth0;
1305 if (diff > biggestDiff)
1309 betterGroup = group;
1311 else if ((diff == biggestDiff) && (a_parVars->m_count[group] < a_parVars->m_count[betterGroup]))
1314 betterGroup = group;
1318 Classify(chosen, betterGroup, a_parVars);
1322 if ((a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total)
1324 if (a_parVars->m_count[0] >= a_parVars->m_total - a_parVars->m_minFill)
1332 for (
int index=0; index<a_parVars->m_total; ++index)
1334 if (!a_parVars->m_taken[index])
1336 Classify(index, group, a_parVars);
1341 ASSERT((a_parVars->m_count[0] + a_parVars->m_count[1]) == a_parVars->m_total);
1342 ASSERT((a_parVars->m_count[0] >= a_parVars->m_minFill) &&
1343 (a_parVars->m_count[1] >= a_parVars->m_minFill));
1349 void RTREE_QUAL::LoadNodes(Node* a_nodeA, Node* a_nodeB, PartitionVars* a_parVars)
1355 for (
int index=0; index < a_parVars->m_total; ++index)
1357 ASSERT(a_parVars->m_partition[index] == 0 || a_parVars->m_partition[index] == 1);
1359 if (a_parVars->m_partition[index] == 0)
1361 AddBranch(&a_parVars->m_branchBuf[index], a_nodeA, NULL);
1363 else if (a_parVars->m_partition[index] == 1)
1365 AddBranch(&a_parVars->m_branchBuf[index], a_nodeB, NULL);
1373 void RTREE_QUAL::InitParVars(PartitionVars* a_parVars,
int a_maxRects,
int a_minFill)
1377 a_parVars->m_count[0] = a_parVars->m_count[1] = 0;
1378 a_parVars->m_area[0] = a_parVars->m_area[1] = (ELEMTYPEREAL)0;
1379 a_parVars->m_total = a_maxRects;
1380 a_parVars->m_minFill = a_minFill;
1381 for (
int index=0; index < a_maxRects; ++index)
1383 a_parVars->m_taken[index] =
false;
1384 a_parVars->m_partition[index] = -1;
1390 void RTREE_QUAL::PickSeeds(PartitionVars* a_parVars)
1395 ELEMTYPEREAL worst, waste;
1396 ELEMTYPEREAL area[MAXNODES+1];
1398 for (
int index=0; index<a_parVars->m_total; ++index)
1400 area[index] = CalcRectVolume(&a_parVars->m_branchBuf[index].m_rect);
1403 worst = -a_parVars->m_coverSplitArea - 1;
1404 for (
int indexA=0; indexA < a_parVars->m_total-1; ++indexA)
1406 for (
int indexB = indexA+1; indexB < a_parVars->m_total; ++indexB)
1408 Rect oneRect = CombineRect(&a_parVars->m_branchBuf[indexA].m_rect, &a_parVars->m_branchBuf[indexB].m_rect);
1409 waste = CalcRectVolume(&oneRect) - area[indexA] - area[indexB];
1418 Classify(seed0, 0, a_parVars);
1419 Classify(seed1, 1, a_parVars);
1425 void RTREE_QUAL::Classify(
int a_index,
int a_group, PartitionVars* a_parVars)
1428 ASSERT(!a_parVars->m_taken[a_index]);
1430 a_parVars->m_partition[a_index] = a_group;
1431 a_parVars->m_taken[a_index] =
true;
1433 if (a_parVars->m_count[a_group] == 0)
1435 a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect;
1439 a_parVars->m_cover[a_group] = CombineRect(&a_parVars->m_branchBuf[a_index].m_rect, &a_parVars->m_cover[a_group]);
1441 a_parVars->m_area[a_group] = CalcRectVolume(&a_parVars->m_cover[a_group]);
1442 ++a_parVars->m_count[a_group];
1451 bool RTREE_QUAL::RemoveRect(Rect* a_rect,
const DATATYPE& a_id, Node** a_root)
1453 ASSERT(a_rect && a_root);
1457 ListNode* reInsertList = NULL;
1459 if (!RemoveRectRec(a_rect, a_id, *a_root, &reInsertList))
1463 while (reInsertList)
1465 tempNode = reInsertList->m_node;
1467 for (
int index = 0; index < tempNode->m_count; ++index)
1469 InsertRect(&(tempNode->m_branch[index].m_rect),
1470 tempNode->m_branch[index].m_data,
1475 ListNode* remLNode = reInsertList;
1476 reInsertList = reInsertList->m_next;
1478 FreeNode(remLNode->m_node);
1479 FreeListNode(remLNode);
1483 if ((*a_root)->m_count == 1 && (*a_root)->IsInternalNode())
1485 tempNode = (*a_root)->m_branch[0].m_child;
1505 bool RTREE_QUAL::RemoveRectRec(Rect* a_rect,
const DATATYPE& a_id, Node* a_node, ListNode** a_listNode)
1507 ASSERT(a_rect && a_node && a_listNode);
1508 ASSERT(a_node->m_level >= 0);
1510 if (a_node->IsInternalNode())
1512 for (
int index = 0; index < a_node->m_count; ++index)
1514 if (Overlap(a_rect, &(a_node->m_branch[index].m_rect)))
1516 if (!RemoveRectRec(a_rect, a_id, a_node->m_branch[index].m_child, a_listNode))
1518 if (a_node->m_branch[index].m_child->m_count >= MINNODES)
1521 a_node->m_branch[index].m_rect = NodeCover(a_node->m_branch[index].m_child);
1526 ReInsert(a_node->m_branch[index].m_child, a_listNode);
1527 DisconnectBranch(a_node, index);
1537 for (
int index = 0; index < a_node->m_count; ++index)
1539 if (a_node->m_branch[index].m_child == (Node*)a_id)
1541 DisconnectBranch(a_node, index);
1552 bool RTREE_QUAL::Overlap(Rect* a_rectA, Rect* a_rectB)
1554 ASSERT(a_rectA && a_rectB);
1556 for (
int index=0; index < NUMDIMS; ++index)
1558 if (a_rectA->m_min[index] > a_rectB->m_max[index] ||
1559 a_rectB->m_min[index] > a_rectA->m_max[index])
1571 void RTREE_QUAL::ReInsert(Node* a_node, ListNode** a_listNode)
1573 ListNode* newListNode;
1575 newListNode = AllocListNode();
1576 newListNode->m_node = a_node;
1577 newListNode->m_next = *a_listNode;
1578 *a_listNode = newListNode;
1584 bool RTREE_QUAL::Search(Node* a_node, Rect* a_rect,
int& a_foundCount,
bool __cdecl a_resultCallback(DATATYPE a_data,
void* a_context),
void* a_context)
1587 ASSERT(a_node->m_level >= 0);
1590 if (a_node->IsInternalNode())
1592 for (
int index=0; index < a_node->m_count; ++index)
1594 if (Overlap(a_rect, &a_node->m_branch[index].m_rect))
1596 if (!Search(a_node->m_branch[index].m_child, a_rect, a_foundCount, a_resultCallback, a_context))
1605 for (
int index=0; index < a_node->m_count; ++index)
1607 if (Overlap(a_rect, &a_node->m_branch[index].m_rect))
1609 DATATYPE&
id = a_node->m_branch[index].m_data;
1612 if (&a_resultCallback)
1615 if (!a_resultCallback(
id, a_context))
1629 #undef RTREE_TEMPLATE
void GetFirst(Iterator &a_it)
Get 'first' for iteration.
A link list of nodes for reinsertion after a delete operation.
Variables for finding a split partition.
DATATYPE & operator*()
Access the current data element. Caller must be sure iterator is not NULL first.
bool IsNull()
Is iterator invalid.
Node * m_child
Child node.
Contains all classes and functions for the VoxelFarm engine.
ELEMTYPEREAL m_unitSphereVolume
Unit sphere constant for required number of dimensions.
DATATYPE m_data
Data Id or Ptr.
Minimal bounding rectangle (n-dimensional)
Branch m_branch[MAXNODES]
Branch.
Iterator is not remove safe.
bool IsNull(Iterator &a_it)
Is iterator NULL, or at end?
void Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
Node for each branch level.
DATATYPE & GetAt(Iterator &a_it)
Get object at iterator position.
int m_level
Leaf is zero, others positive.
int Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], bool __cdecl a_resultCallback(DATATYPE a_data, void *a_context), void *a_context)
bool Save(const char *a_fileName)
Save tree contents to file.
ELEMTYPE m_min[NUMDIMS]
Min dimensions of bounding box.
ELEMTYPE m_max[NUMDIMS]
Max dimensions of bounding box.
void Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
int Count()
Count the data elements in this container. This is slow as no internal counter is maintained...
bool operator++()
Find the next data element.
ListNode * m_next
Next in list.
void GetBounds(ELEMTYPE a_min[NUMDIMS], ELEMTYPE a_max[NUMDIMS])
Get the bounds for this node.
const DATATYPE & operator*() const
Access the current data element. Caller must be sure iterator is not NULL first.
void GetNext(Iterator &a_it)
Get Next for iteration.
Node * m_root
Root of tree.
bool Load(const char *a_fileName)
Load tree contents from file.
bool IsNotNull()
Is iterator pointing to valid data.
void RemoveAll()
Remove all entries from tree.