RTree.h
1 #ifndef RTREE_H
2 #define RTREE_H
3 
4 // NOTE This file compiles under MSVC 6 SP5 and MSVC .Net 2003 it may not work on other compilers without modification.
5 
6 // NOTE These next few lines may be win32 specific, you may need to modify them to compile on other platform
7 #include <stdio.h>
8 #include <math.h>
9 #include <assert.h>
10 #include <stdlib.h>
11 #include <minmax.h>
12 
13 #define ASSERT assert // RTree uses ASSERT( condition )
14 
15 //
16 // RTree.h
17 //
18 namespace VoxelFarm
19 {
20 
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>
23 
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
26 
27 // Fwd decl
28  class RTFileStream; // File I/O helper class, look below for implementation and notes.
29 
30 
47  template<class DATATYPE, class ELEMTYPE, int NUMDIMS,
48  class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>
49  class RTree
50  {
51  public:
52 
53  struct Node; // Fwd decl. Used by other internal structs and iterator
54 
55  public:
56 
57  // These constant must be declared after Branch and before Node struct
58  // Stuck up here for MSVC 6 compiler. NSVC .NET 2003 is much happier.
59  enum
60  {
61  MAXNODES = TMAXNODES,
62  MINNODES = TMINNODES,
63  };
64 
65 
66  public:
67 
68  RTree();
69  virtual ~RTree();
70 
75  void Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId);
76 
81  void Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId);
82 
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);
91 
93  void RemoveAll();
94 
96  int Count();
97 
99  bool Load(const char* a_fileName);
101  bool Load(RTFileStream& a_stream);
102 
103 
105  bool Save(const char* a_fileName);
107  bool Save(RTFileStream& a_stream);
108 
110  class Iterator
111  {
112  private:
113 
114  enum { MAX_STACK = 32 }; // Max stack size. Allows almost n^32 where n is number of branches in node
115 
116  struct StackElement
117  {
118  Node* m_node;
119  int m_branchIndex;
120  };
121 
122  public:
123 
124  Iterator() : m_stack()
125  {
126  Init();
127  }
128 
129  ~Iterator() { }
130 
132  bool IsNull()
133  {
134  return (m_tos <= 0);
135  }
136 
138  bool IsNotNull()
139  {
140  return (m_tos > 0);
141  }
142 
144  DATATYPE& operator*()
145  {
146  ASSERT(IsNotNull());
147  StackElement& curTos = m_stack[m_tos - 1];
148  return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
149  }
150 
152  const DATATYPE& operator*() const
153  {
154  ASSERT(IsNotNull());
155  StackElement& curTos = m_stack[m_tos - 1];
156  return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
157  }
158 
160  bool operator++()
161  {
162  return FindNextData();
163  }
164 
166  void GetBounds(ELEMTYPE a_min[NUMDIMS], ELEMTYPE a_max[NUMDIMS])
167  {
168  ASSERT(IsNotNull());
169  StackElement& curTos = m_stack[m_tos - 1];
170  Branch& curBranch = curTos.m_node->m_branch[curTos.m_branchIndex];
171 
172  for (int index = 0; index < NUMDIMS; ++index)
173  {
174  a_min[index] = curBranch.m_rect.m_min[index];
175  a_max[index] = curBranch.m_rect.m_max[index];
176  }
177  }
178 
179  private:
180 
182  void Init()
183  {
184  m_tos = 0;
185  }
186 
188  bool FindNextData()
189  {
190  for (;;)
191  {
192  if (m_tos <= 0)
193  {
194  return false;
195  }
196  StackElement curTos = Pop(); // Copy stack top cause it may change as we use it
197 
198  if (curTos.m_node->IsLeaf())
199  {
200  // Keep walking through data while we can
201  if (curTos.m_branchIndex+1 < curTos.m_node->m_count)
202  {
203  // There is more data, just point to the next one
204  Push(curTos.m_node, curTos.m_branchIndex + 1);
205  return true;
206  }
207  // No more data, so it will fall back to previous level
208  }
209  else
210  {
211  if (curTos.m_branchIndex+1 < curTos.m_node->m_count)
212  {
213  // Push sibling on for future tree walk
214  // This is the 'fall back' node when we finish with the current level
215  Push(curTos.m_node, curTos.m_branchIndex + 1);
216  }
217  // Since cur node is not a leaf, push first of next level to get deeper into the tree
218  Node* nextLevelnode = curTos.m_node->m_branch[curTos.m_branchIndex].m_child;
219  Push(nextLevelnode, 0);
220 
221  // If we pushed on a new leaf, exit as the data is ready at TOS
222  if (nextLevelnode->IsLeaf())
223  {
224  return true;
225  }
226  }
227  }
228  }
229 
231  void Push(Node* a_node, int a_branchIndex)
232  {
233  m_stack[m_tos].m_node = a_node;
234  m_stack[m_tos].m_branchIndex = a_branchIndex;
235  ++m_tos;
236  ASSERT(m_tos <= MAX_STACK);
237  }
238 
240  StackElement& Pop()
241  {
242  ASSERT(m_tos > 0);
243  --m_tos;
244  return m_stack[m_tos];
245  }
246 
247  StackElement m_stack[MAX_STACK];
248  int m_tos;
249 
250  friend RTree; // Allow hiding of non-public functions while allowing manipulation by logical owner
251  };
252 
254  void GetFirst(Iterator& a_it)
255  {
256  a_it.Init();
257  Node* first = m_root;
258  while (first)
259  {
260  if (first->IsInternalNode() && first->m_count > 1)
261  {
262  a_it.Push(first, 1); // Descend sibling branch later
263  }
264  else if (first->IsLeaf())
265  {
266  if (first->m_count)
267  {
268  a_it.Push(first, 0);
269  }
270  break;
271  }
272  first = first->m_branch[0].m_child;
273  }
274  }
275 
277  void GetNext(Iterator& a_it)
278  {
279  ++a_it;
280  }
281 
283  bool IsNull(Iterator& a_it)
284  {
285  return a_it.IsNull();
286  }
287 
289  DATATYPE& GetAt(Iterator& a_it)
290  {
291  return *a_it;
292  }
293 
294  public:
295 
297  struct Rect
298  {
299  ELEMTYPE m_min[NUMDIMS];
300  ELEMTYPE m_max[NUMDIMS];
301  };
302 
306  struct Branch
307  {
309  union
310  {
312  DATATYPE m_data;
313  };
314  };
315 
317  struct Node
318  {
319  bool IsInternalNode()
320  {
321  return (m_level > 0); // Not a leaf, but a internal node
322  }
323  bool IsLeaf()
324  {
325  return (m_level == 0); // A leaf, contains data
326  }
327 
328  int m_count;
329  int m_level;
331  };
332 
334  struct ListNode
335  {
338  };
339 
342  {
343  int m_partition[MAXNODES+1];
344  int m_total;
345  int m_minFill;
346  int m_taken[MAXNODES+1];
347  int m_count[2];
348  Rect m_cover[2];
349  ELEMTYPEREAL m_area[2];
350 
351  Branch m_branchBuf[MAXNODES+1];
352  int m_branchCount;
353  Rect m_coverSplit;
354  ELEMTYPEREAL m_coverSplitArea;
355  };
356 
357  Node* AllocNode();
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);
363  Rect NodeCover(Node* a_node);
364  bool AddBranch(Branch* a_branch, Node* a_node, Node** a_newNode);
365  void DisconnectBranch(Node* a_node, int a_index);
366  int PickBranch(Rect* a_rect, Node* a_node);
367  Rect CombineRect(Rect* a_rectA, Rect* a_rectB);
368  void SplitNode(Node* a_node, Branch* a_branch, Node** a_newNode);
369  ELEMTYPEREAL RectSphericalVolume(Rect* a_rect);
370  ELEMTYPEREAL RectVolume(Rect* a_rect);
371  ELEMTYPEREAL CalcRectVolume(Rect* a_rect);
372  void GetBranches(Node* a_node, Branch* a_branch, PartitionVars* a_parVars);
373  void ChoosePartition(PartitionVars* a_parVars, int a_minFill);
374  void LoadNodes(Node* a_nodeA, Node* a_nodeB, PartitionVars* a_parVars);
375  void InitParVars(PartitionVars* a_parVars, int a_maxRects, int a_minFill);
376  void PickSeeds(PartitionVars* a_parVars);
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);
380  ListNode* AllocListNode();
381  void FreeListNode(ListNode* a_listNode);
382  bool Overlap(Rect* a_rectA, Rect* a_rectB);
383  void ReInsert(Node* a_node, ListNode** a_listNode);
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);
386  void Reset();
387  void CountRec(Node* a_node, int& a_count);
388 
389  bool SaveRec(Node* a_node, RTFileStream& a_stream);
390  bool LoadRec(Node* a_node, RTFileStream& a_stream);
391 
392  Node* m_root;
393  ELEMTYPEREAL m_unitSphereVolume;
394  };
395 
396 
397 // Because there is not stream support, this is a quick and dirty file I/O helper.
398 // Users will likely replace its usage with a Stream implementation from their favorite API.
400  {
401  FILE* m_file;
402 
403  public:
404 
405 
406  RTFileStream()
407  {
408  m_file = NULL;
409  }
410 
411  ~RTFileStream()
412  {
413  Close();
414  }
415 
416  bool OpenRead(const char* a_fileName)
417  {
418  if (fopen_s(&m_file, a_fileName, "rb") != 0)
419  {
420  m_file = NULL;
421  }
422  if (!m_file)
423  {
424  return false;
425  }
426  return true;
427  }
428 
429  bool OpenWrite(const char* a_fileName)
430  {
431  if (fopen_s(&m_file, a_fileName, "wb") != 0)
432  {
433  m_file = NULL;
434  }
435  if (!m_file)
436  {
437  return false;
438  }
439  return true;
440  }
441 
442  void Close()
443  {
444  if (m_file)
445  {
446  fclose(m_file);
447  m_file = NULL;
448  }
449  }
450 
451  template< typename TYPE >
452  size_t Write(const TYPE& a_value)
453  {
454  ASSERT(m_file);
455  return fwrite((void*)&a_value, sizeof(a_value), 1, m_file);
456  }
457 
458  template< typename TYPE >
459  size_t WriteArray(const TYPE* a_array, int a_count)
460  {
461  ASSERT(m_file);
462  return fwrite((void*)a_array, sizeof(TYPE) * a_count, 1, m_file);
463  }
464 
465  template< typename TYPE >
466  size_t Read(TYPE& a_value)
467  {
468  ASSERT(m_file);
469  return fread((void*)&a_value, sizeof(a_value), 1, m_file);
470  }
471 
472  template< typename TYPE >
473  size_t ReadArray(TYPE* a_array, int a_count)
474  {
475  ASSERT(m_file);
476  return fread((void*)a_array, sizeof(TYPE) * a_count, 1, m_file);
477  }
478  };
479 
480 
481  RTREE_TEMPLATE
482  RTREE_QUAL::RTree()
483  {
484  ASSERT(MAXNODES > MINNODES);
485  ASSERT(MINNODES > 0);
486 
487 
488  // We only support machine word size simple data type eg. integer index or object pointer.
489  // Since we are storing as union with non data branch
490  ASSERT(sizeof(DATATYPE) == sizeof(void*) || sizeof(DATATYPE) == sizeof(int));
491 
492  // Precomputed volumes of the unit spheres for the first few dimensions
493  const float UNIT_SPHERE_VOLUMES[] =
494  {
495  0.000000f, 2.000000f, 3.141593f, // Dimension 0,1,2
496  4.188790f, 4.934802f, 5.263789f, // Dimension 3,4,5
497  5.167713f, 4.724766f, 4.058712f, // Dimension 6,7,8
498  3.298509f, 2.550164f, 1.884104f, // Dimension 9,10,11
499  1.335263f, 0.910629f, 0.599265f, // Dimension 12,13,14
500  0.381443f, 0.235331f, 0.140981f, // Dimension 15,16,17
501  0.082146f, 0.046622f, 0.025807f, // Dimension 18,19,20
502  };
503 
504  m_root = AllocNode();
505  m_root->m_level = 0;
506  m_unitSphereVolume = (ELEMTYPEREAL)UNIT_SPHERE_VOLUMES[NUMDIMS];
507  }
508 
509 
510  RTREE_TEMPLATE
511  RTREE_QUAL::~RTree()
512  {
513  Reset(); // Free, or reset node memory
514  }
515 
516 
517  RTREE_TEMPLATE
518  void RTREE_QUAL::Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId)
519  {
520 #ifdef _DEBUG
521  for (int index=0; index<NUMDIMS; ++index)
522  {
523  ASSERT(a_min[index] <= a_max[index]);
524  }
525 #endif //_DEBUG
526 
527  Rect rect;
528 
529  for (int axis=0; axis<NUMDIMS; ++axis)
530  {
531  rect.m_min[axis] = a_min[axis];
532  rect.m_max[axis] = a_max[axis];
533  }
534 
535  InsertRect(&rect, a_dataId, &m_root, 0);
536  }
537 
538 
539  RTREE_TEMPLATE
540  void RTREE_QUAL::Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId)
541  {
542 #ifdef _DEBUG
543  for (int index=0; index<NUMDIMS; ++index)
544  {
545  ASSERT(a_min[index] <= a_max[index]);
546  }
547 #endif //_DEBUG
548 
549  Rect rect;
550 
551  for (int axis=0; axis<NUMDIMS; ++axis)
552  {
553  rect.m_min[axis] = a_min[axis];
554  rect.m_max[axis] = a_max[axis];
555  }
556 
557  RemoveRect(&rect, a_dataId, &m_root);
558  }
559 
560 
561  RTREE_TEMPLATE
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),
563  void* a_context)
564  {
565 #ifdef _DEBUG
566  for (int index=0; index<NUMDIMS; ++index)
567  {
568  ASSERT(a_min[index] <= a_max[index]);
569  }
570 #endif //_DEBUG
571 
572  Rect rect;
573 
574  for (int axis=0; axis<NUMDIMS; ++axis)
575  {
576  rect.m_min[axis] = a_min[axis];
577  rect.m_max[axis] = a_max[axis];
578  }
579 
580  // NOTE: May want to return search result another way, perhaps returning the number of found elements here.
581 
582  int foundCount = 0;
583  Search(m_root, &rect, foundCount, a_resultCallback, a_context);
584 
585  return foundCount;
586  }
587 
588 
589  RTREE_TEMPLATE
590  int RTREE_QUAL::Count()
591  {
592  int count = 0;
593  CountRec(m_root, count);
594 
595  return count;
596  }
597 
598 
599 
600  RTREE_TEMPLATE
601  void RTREE_QUAL::CountRec(Node* a_node, int& a_count)
602  {
603  if (a_node->IsInternalNode()) // not a leaf node
604  {
605  for (int index = 0; index < a_node->m_count; ++index)
606  {
607  CountRec(a_node->m_branch[index].m_child, a_count);
608  }
609  }
610  else // A leaf node
611  {
612  a_count += a_node->m_count;
613  }
614  }
615 
616 
617  RTREE_TEMPLATE
618  bool RTREE_QUAL::Load(const char* a_fileName)
619  {
620  RemoveAll(); // Clear existing tree
621 
622  RTFileStream stream;
623  if (!stream.OpenRead(a_fileName))
624  {
625  return false;
626  }
627 
628  bool result = Load(stream);
629 
630  stream.Close();
631 
632  return result;
633  };
634 
635 
636 
637  RTREE_TEMPLATE
638  bool RTREE_QUAL::Load(RTFileStream& a_stream)
639  {
640  // Write some kind of header
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;
648 
649  int dataFileId = 0;
650  int dataSize = 0;
651  int dataNumDims = 0;
652  int dataElemSize = 0;
653  int dataElemRealSize = 0;
654  int dataMaxNodes = 0;
655  int dataMinNodes = 0;
656 
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);
664 
665  bool result = false;
666 
667  // Test if header was valid and compatible
668  if ((dataFileId == _dataFileId)
669  && (dataSize == _dataSize)
670  && (dataNumDims == _dataNumDims)
671  && (dataElemSize == _dataElemSize)
672  && (dataElemRealSize == _dataElemRealSize)
673  && (dataMaxNodes == _dataMaxNodes)
674  && (dataMinNodes == _dataMinNodes)
675  )
676  {
677  // Recursively load tree
678  result = LoadRec(m_root, a_stream);
679  }
680 
681  return result;
682  }
683 
684 
685  RTREE_TEMPLATE
686  bool RTREE_QUAL::LoadRec(Node* a_node, RTFileStream& a_stream)
687  {
688  a_stream.Read(a_node->m_level);
689  a_stream.Read(a_node->m_count);
690 
691  if (a_node->IsInternalNode()) // not a leaf node
692  {
693  for (int index = 0; index < a_node->m_count; ++index)
694  {
695  Branch* curBranch = &a_node->m_branch[index];
696 
697  a_stream.ReadArray(curBranch->m_rect.m_min, NUMDIMS);
698  a_stream.ReadArray(curBranch->m_rect.m_max, NUMDIMS);
699 
700  curBranch->m_child = AllocNode();
701  LoadRec(curBranch->m_child, a_stream);
702  }
703  }
704  else // A leaf node
705  {
706  for (int index = 0; index < a_node->m_count; ++index)
707  {
708  Branch* curBranch = &a_node->m_branch[index];
709 
710  a_stream.ReadArray(curBranch->m_rect.m_min, NUMDIMS);
711  a_stream.ReadArray(curBranch->m_rect.m_max, NUMDIMS);
712 
713  a_stream.Read(curBranch->m_data);
714  }
715  }
716 
717  return true; // Should do more error checking on I/O operations
718  }
719 
720 
721  RTREE_TEMPLATE
722  bool RTREE_QUAL::Save(const char* a_fileName)
723  {
724  RTFileStream stream;
725  if (!stream.OpenWrite(a_fileName))
726  {
727  return false;
728  }
729 
730  bool result = Save(stream);
731 
732  stream.Close();
733 
734  return result;
735  }
736 
737 
738  RTREE_TEMPLATE
739  bool RTREE_QUAL::Save(RTFileStream& a_stream)
740  {
741  // Write some kind of header
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;
749 
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);
757 
758  // Recursively save tree
759  bool result = SaveRec(m_root, a_stream);
760 
761  return result;
762  }
763 
764 
765  RTREE_TEMPLATE
766  bool RTREE_QUAL::SaveRec(Node* a_node, RTFileStream& a_stream)
767  {
768  a_stream.Write(a_node->m_level);
769  a_stream.Write(a_node->m_count);
770 
771  if (a_node->IsInternalNode()) // not a leaf node
772  {
773  for (int index = 0; index < a_node->m_count; ++index)
774  {
775  Branch* curBranch = &a_node->m_branch[index];
776 
777  a_stream.WriteArray(curBranch->m_rect.m_min, NUMDIMS);
778  a_stream.WriteArray(curBranch->m_rect.m_max, NUMDIMS);
779 
780  SaveRec(curBranch->m_child, a_stream);
781  }
782  }
783  else // A leaf node
784  {
785  for (int index = 0; index < a_node->m_count; ++index)
786  {
787  Branch* curBranch = &a_node->m_branch[index];
788 
789  a_stream.WriteArray(curBranch->m_rect.m_min, NUMDIMS);
790  a_stream.WriteArray(curBranch->m_rect.m_max, NUMDIMS);
791 
792  a_stream.Write(curBranch->m_data);
793  }
794  }
795 
796  return true; // Should do more error checking on I/O operations
797  }
798 
799 
800  RTREE_TEMPLATE
801  void RTREE_QUAL::RemoveAll()
802  {
803  // Delete all existing nodes
804  Reset();
805 
806  m_root = AllocNode();
807  m_root->m_level = 0;
808  }
809 
810 
811  RTREE_TEMPLATE
812  void RTREE_QUAL::Reset()
813  {
814 #ifdef RTREE_DONT_USE_MEMPOOLS
815  // Delete all existing nodes
816  RemoveAllRec(m_root);
817 #else // RTREE_DONT_USE_MEMPOOLS
818  // Just reset memory pools. We are not using complex types
819  // EXAMPLE
820 #endif // RTREE_DONT_USE_MEMPOOLS
821  }
822 
823 
824  RTREE_TEMPLATE
825  void RTREE_QUAL::RemoveAllRec(Node* a_node)
826  {
827  ASSERT(a_node);
828  ASSERT(a_node->m_level >= 0);
829 
830  if (a_node->IsInternalNode()) // This is an internal node in the tree
831  {
832  for (int index=0; index < a_node->m_count; ++index)
833  {
834  RemoveAllRec(a_node->m_branch[index].m_child);
835  }
836  }
837  FreeNode(a_node);
838  }
839 
840 
841  RTREE_TEMPLATE
842  typename RTREE_QUAL::Node* RTREE_QUAL::AllocNode()
843  {
844  Node* newNode;
845 #ifdef RTREE_DONT_USE_MEMPOOLS
846  newNode = VF_NEW Node;
847 #else // RTREE_DONT_USE_MEMPOOLS
848  // EXAMPLE
849 #endif // RTREE_DONT_USE_MEMPOOLS
850  InitNode(newNode);
851  return newNode;
852  }
853 
854 
855  RTREE_TEMPLATE
856  void RTREE_QUAL::FreeNode(Node* a_node)
857  {
858  ASSERT(a_node);
859 
860 #ifdef RTREE_DONT_USE_MEMPOOLS
861  VF_DELETE a_node;
862 #else // RTREE_DONT_USE_MEMPOOLS
863  // EXAMPLE
864 #endif // RTREE_DONT_USE_MEMPOOLS
865  }
866 
867 
868 // Allocate space for a node in the list used in DeletRect to
869 // store Nodes that are too empty.
870  RTREE_TEMPLATE
871  typename RTREE_QUAL::ListNode* RTREE_QUAL::AllocListNode()
872  {
873 #ifdef RTREE_DONT_USE_MEMPOOLS
874  return VF_NEW ListNode;
875 #else // RTREE_DONT_USE_MEMPOOLS
876  // EXAMPLE
877 #endif // RTREE_DONT_USE_MEMPOOLS
878  }
879 
880 
881  RTREE_TEMPLATE
882  void RTREE_QUAL::FreeListNode(ListNode* a_listNode)
883  {
884 #ifdef RTREE_DONT_USE_MEMPOOLS
885  VF_DELETE a_listNode;
886 #else // RTREE_DONT_USE_MEMPOOLS
887  // EXAMPLE
888 #endif // RTREE_DONT_USE_MEMPOOLS
889  }
890 
891 
892  RTREE_TEMPLATE
893  void RTREE_QUAL::InitNode(Node* a_node)
894  {
895  a_node->m_count = 0;
896  a_node->m_level = -1;
897  }
898 
899 
900  RTREE_TEMPLATE
901  void RTREE_QUAL::InitRect(Rect* a_rect)
902  {
903  for (int index = 0; index < NUMDIMS; ++index)
904  {
905  a_rect->m_min[index] = (ELEMTYPE)0;
906  a_rect->m_max[index] = (ELEMTYPE)0;
907  }
908  }
909 
910 
911 // Inserts a new data rectangle into the index structure.
912 // Recursively descends tree, propagates splits back up.
913 // Returns 0 if node was not split. Old node updated.
914 // If node was split, returns 1 and sets the pointer pointed to by
915 // new_node to point to the new node. Old node updated to become one of two.
916 // The level argument specifies the number of steps up from the leaf
917 // level to insert; e.g. a data rectangle goes in at level = 0.
918  RTREE_TEMPLATE
919  bool RTREE_QUAL::InsertRectRec(Rect* a_rect, const DATATYPE& a_id, Node* a_node, Node** a_newNode, int a_level)
920  {
921  ASSERT(a_rect && a_node && a_newNode);
922  ASSERT(a_level >= 0 && a_level <= a_node->m_level);
923 
924  int index;
925  Branch branch;
926  Node* otherNode;
927 
928  // Still above level for insertion, go down tree recursively
929  if (a_node->m_level > a_level)
930  {
931  index = PickBranch(a_rect, a_node);
932  if (!InsertRectRec(a_rect, a_id, a_node->m_branch[index].m_child, &otherNode, a_level))
933  {
934  // Child was not split
935  a_node->m_branch[index].m_rect = CombineRect(a_rect, &(a_node->m_branch[index].m_rect));
936  return false;
937  }
938  else // Child was split
939  {
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);
944  }
945  }
946  else if (a_node->m_level == a_level) // Have reached level for insertion. Add rect, split if necessary
947  {
948  branch.m_rect = *a_rect;
949  branch.m_child = (Node*) a_id;
950  // Child field of leaves contains id of data record
951  return AddBranch(&branch, a_node, a_newNode);
952  }
953  else
954  {
955  // Should never occur
956  ASSERT(0);
957  return false;
958  }
959  }
960 
961 
962 // Insert a data rectangle into an index structure.
963 // InsertRect provides for splitting the root;
964 // returns 1 if root was split, 0 if it was not.
965 // The level argument specifies the number of steps up from the leaf
966 // level to insert; e.g. a data rectangle goes in at level = 0.
967 // InsertRect2 does the recursion.
968 //
969  RTREE_TEMPLATE
970  bool RTREE_QUAL::InsertRect(Rect* a_rect, const DATATYPE& a_id, Node** a_root, int a_level)
971  {
972  ASSERT(a_rect && a_root);
973  ASSERT(a_level >= 0 && a_level <= (*a_root)->m_level);
974 #ifdef _DEBUG
975  for (int index=0; index < NUMDIMS; ++index)
976  {
977  ASSERT(a_rect->m_min[index] <= a_rect->m_max[index]);
978  }
979 #endif //_DEBUG
980 
981  Node* newRoot;
982  Node* newNode;
983  Branch branch;
984 
985  if (InsertRectRec(a_rect, a_id, *a_root, &newNode, a_level)) // Root split
986  {
987  newRoot = AllocNode(); // Grow tree taller and new root
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);
995  *a_root = newRoot;
996  return true;
997  }
998 
999  return false;
1000  }
1001 
1002 
1003 // Find the smallest rectangle that includes all rectangles in branches of a node.
1004  RTREE_TEMPLATE
1005  typename RTREE_QUAL::Rect RTREE_QUAL::NodeCover(Node* a_node)
1006  {
1007  ASSERT(a_node);
1008 
1009  int firstTime = true;
1010  Rect rect;
1011  InitRect(&rect);
1012 
1013  for (int index = 0; index < a_node->m_count; ++index)
1014  {
1015  if (firstTime)
1016  {
1017  rect = a_node->m_branch[index].m_rect;
1018  firstTime = false;
1019  }
1020  else
1021  {
1022  rect = CombineRect(&rect, &(a_node->m_branch[index].m_rect));
1023  }
1024  }
1025 
1026  return rect;
1027  }
1028 
1029 
1030 // Add a branch to a node. Split the node if necessary.
1031 // Returns 0 if node not split. Old node updated.
1032 // Returns 1 if node split, sets *new_node to address of new node.
1033 // Old node updated, becomes one of two.
1034  RTREE_TEMPLATE
1035  bool RTREE_QUAL::AddBranch(Branch* a_branch, Node* a_node, Node** a_newNode)
1036  {
1037  ASSERT(a_branch);
1038  ASSERT(a_node);
1039 
1040  if (a_node->m_count < MAXNODES) // Split won't be necessary
1041  {
1042  a_node->m_branch[a_node->m_count] = *a_branch;
1043  ++a_node->m_count;
1044 
1045  return false;
1046  }
1047  else
1048  {
1049  ASSERT(a_newNode);
1050 
1051  SplitNode(a_node, a_branch, a_newNode);
1052  return true;
1053  }
1054  }
1055 
1056 
1057 // Disconnect a dependent node.
1058 // Caller must return (or stop using iteration index) after this as count has changed
1059  RTREE_TEMPLATE
1060  void RTREE_QUAL::DisconnectBranch(Node* a_node, int a_index)
1061  {
1062  ASSERT(a_node && (a_index >= 0) && (a_index < MAXNODES));
1063  ASSERT(a_node->m_count > 0);
1064 
1065  // Remove element by swapping with the last element to prevent gaps in array
1066  a_node->m_branch[a_index] = a_node->m_branch[a_node->m_count - 1];
1067 
1068  --a_node->m_count;
1069  }
1070 
1071 
1072 // Pick a branch. Pick the one that will need the smallest increase
1073 // in area to accomodate the new rectangle. This will result in the
1074 // least total area for the covering rectangles in the current node.
1075 // In case of a tie, pick the one which was smaller before, to get
1076 // the best resolution when searching.
1077  RTREE_TEMPLATE
1078  int RTREE_QUAL::PickBranch(Rect* a_rect, Node* a_node)
1079  {
1080  ASSERT(a_rect && a_node);
1081 
1082  bool firstTime = true;
1083  ELEMTYPEREAL increase;
1084  ELEMTYPEREAL bestIncr = (ELEMTYPEREAL)-1;
1085  ELEMTYPEREAL area;
1086  ELEMTYPEREAL bestArea;
1087  int best = 0;
1088  Rect tempRect;
1089 
1090  for (int index=0; index < a_node->m_count; ++index)
1091  {
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)
1097  {
1098  best = index;
1099  bestArea = area;
1100  bestIncr = increase;
1101  firstTime = false;
1102  }
1103  else if ((increase == bestIncr) && (area < bestArea))
1104  {
1105  best = index;
1106  bestArea = area;
1107  bestIncr = increase;
1108  }
1109  }
1110  return best;
1111  }
1112 
1113 
1114 // Combine two rectangles into larger one containing both
1115  RTREE_TEMPLATE
1116  typename RTREE_QUAL::Rect RTREE_QUAL::CombineRect(Rect* a_rectA, Rect* a_rectB)
1117  {
1118  ASSERT(a_rectA && a_rectB);
1119 
1120  Rect newRect;
1121 
1122  for (int index = 0; index < NUMDIMS; ++index)
1123  {
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]);
1126  }
1127 
1128  return newRect;
1129  }
1130 
1131 
1132 
1133 // Split a node.
1134 // Divides the nodes branches and the extra one between two nodes.
1135 // Old node is one of the new ones, and one really new one is created.
1136 // Tries more than one method for choosing a partition, uses best result.
1137  RTREE_TEMPLATE
1138  void RTREE_QUAL::SplitNode(Node* a_node, Branch* a_branch, Node** a_newNode)
1139  {
1140  ASSERT(a_node);
1141  ASSERT(a_branch);
1142 
1143  // Could just use local here, but member or external is faster since it is reused
1144  PartitionVars localVars;
1145  PartitionVars* parVars = &localVars;
1146  int level;
1147 
1148  // Load all the branches into a buffer, initialize old node
1149  level = a_node->m_level;
1150  GetBranches(a_node, a_branch, parVars);
1151 
1152  // Find partition
1153  ChoosePartition(parVars, MINNODES);
1154 
1155  // Put branches from buffer into 2 nodes according to chosen partition
1156  *a_newNode = AllocNode();
1157  (*a_newNode)->m_level = a_node->m_level = level;
1158  LoadNodes(a_node, *a_newNode, parVars);
1159 
1160  ASSERT((a_node->m_count + (*a_newNode)->m_count) == parVars->m_total);
1161  }
1162 
1163 
1164 // Calculate the n-dimensional volume of a rectangle
1165  RTREE_TEMPLATE
1166  ELEMTYPEREAL RTREE_QUAL::RectVolume(Rect* a_rect)
1167  {
1168  ASSERT(a_rect);
1169 
1170  ELEMTYPEREAL volume = (ELEMTYPEREAL)1;
1171 
1172  for (int index=0; index<NUMDIMS; ++index)
1173  {
1174  volume *= a_rect->m_max[index] - a_rect->m_min[index];
1175  }
1176 
1177  ASSERT(volume >= (ELEMTYPEREAL)0);
1178 
1179  return volume;
1180  }
1181 
1182 
1183 // The exact volume of the bounding sphere for the given Rect
1184  RTREE_TEMPLATE
1185  ELEMTYPEREAL RTREE_QUAL::RectSphericalVolume(Rect* a_rect)
1186  {
1187  ASSERT(a_rect);
1188 
1189  ELEMTYPEREAL sumOfSquares = (ELEMTYPEREAL)0;
1190  ELEMTYPEREAL radius;
1191 
1192  for (int index=0; index < NUMDIMS; ++index)
1193  {
1194  ELEMTYPEREAL halfExtent = ((ELEMTYPEREAL)a_rect->m_max[index] - (ELEMTYPEREAL)a_rect->m_min[index]) * 0.5f;
1195  sumOfSquares += halfExtent * halfExtent;
1196  }
1197 
1198  radius = (ELEMTYPEREAL)sqrt(sumOfSquares);
1199 
1200  // Pow maybe slow, so test for common dims like 2,3 and just use x*x, x*x*x.
1201  if (NUMDIMS == 3)
1202  {
1203  return (radius * radius * radius * m_unitSphereVolume);
1204  }
1205  else if (NUMDIMS == 2)
1206  {
1207  return (radius * radius * m_unitSphereVolume);
1208  }
1209  else
1210  {
1211  return (ELEMTYPEREAL)(pow(radius, NUMDIMS) * m_unitSphereVolume);
1212  }
1213  }
1214 
1215 
1216 // Use one of the methods to calculate retangle volume
1217  RTREE_TEMPLATE
1218  ELEMTYPEREAL RTREE_QUAL::CalcRectVolume(Rect* a_rect)
1219  {
1220 #ifdef RTREE_USE_SPHERICAL_VOLUME
1221  return RectSphericalVolume(a_rect); // Slower but helps certain merge cases
1222 #else // RTREE_USE_SPHERICAL_VOLUME
1223  return RectVolume(a_rect); // Faster but can cause poor merges
1224 #endif // RTREE_USE_SPHERICAL_VOLUME
1225  }
1226 
1227 
1228 // Load branch buffer with branches from full node plus the extra branch.
1229  RTREE_TEMPLATE
1230  void RTREE_QUAL::GetBranches(Node* a_node, Branch* a_branch, PartitionVars* a_parVars)
1231  {
1232  ASSERT(a_node);
1233  ASSERT(a_branch);
1234 
1235  ASSERT(a_node->m_count == MAXNODES);
1236 
1237  // Load the branch buffer
1238  for (int index=0; index < MAXNODES; ++index)
1239  {
1240  a_parVars->m_branchBuf[index] = a_node->m_branch[index];
1241  }
1242  a_parVars->m_branchBuf[MAXNODES] = *a_branch;
1243  a_parVars->m_branchCount = MAXNODES + 1;
1244 
1245  // Calculate rect containing all in the set
1246  a_parVars->m_coverSplit = a_parVars->m_branchBuf[0].m_rect;
1247  for (int index=1; index < MAXNODES+1; ++index)
1248  {
1249  a_parVars->m_coverSplit = CombineRect(&a_parVars->m_coverSplit, &a_parVars->m_branchBuf[index].m_rect);
1250  }
1251  a_parVars->m_coverSplitArea = CalcRectVolume(&a_parVars->m_coverSplit);
1252 
1253  InitNode(a_node);
1254  }
1255 
1256 
1257 // Method #0 for choosing a partition:
1258 // As the seeds for the two groups, pick the two rects that would waste the
1259 // most area if covered by a single rectangle, i.e. evidently the worst pair
1260 // to have in the same group.
1261 // Of the remaining, one at a time is chosen to be put in one of the two groups.
1262 // The one chosen is the one with the greatest difference in area expansion
1263 // depending on which group - the rect most strongly attracted to one group
1264 // and repelled from the other.
1265 // If one group gets too full (more would force other group to violate min
1266 // fill requirement) then other group gets the rest.
1267 // These last are the ones that can go in either group most easily.
1268  RTREE_TEMPLATE
1269  void RTREE_QUAL::ChoosePartition(PartitionVars* a_parVars, int a_minFill)
1270  {
1271  ASSERT(a_parVars);
1272 
1273  ELEMTYPEREAL biggestDiff;
1274  int group, chosen, betterGroup;
1275  chosen = 0;
1276 
1277  InitParVars(a_parVars, a_parVars->m_branchCount, a_minFill);
1278  PickSeeds(a_parVars);
1279 
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)))
1283  {
1284  biggestDiff = (ELEMTYPEREAL) -1;
1285  for (int index=0; index<a_parVars->m_total; ++index)
1286  {
1287  if (!a_parVars->m_taken[index])
1288  {
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;
1295  if (diff >= 0)
1296  {
1297  group = 0;
1298  }
1299  else
1300  {
1301  group = 1;
1302  diff = -diff;
1303  }
1304 
1305  if (diff > biggestDiff)
1306  {
1307  biggestDiff = diff;
1308  chosen = index;
1309  betterGroup = group;
1310  }
1311  else if ((diff == biggestDiff) && (a_parVars->m_count[group] < a_parVars->m_count[betterGroup]))
1312  {
1313  chosen = index;
1314  betterGroup = group;
1315  }
1316  }
1317  }
1318  Classify(chosen, betterGroup, a_parVars);
1319  }
1320 
1321  // If one group too full, put remaining rects in the other
1322  if ((a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total)
1323  {
1324  if (a_parVars->m_count[0] >= a_parVars->m_total - a_parVars->m_minFill)
1325  {
1326  group = 1;
1327  }
1328  else
1329  {
1330  group = 0;
1331  }
1332  for (int index=0; index<a_parVars->m_total; ++index)
1333  {
1334  if (!a_parVars->m_taken[index])
1335  {
1336  Classify(index, group, a_parVars);
1337  }
1338  }
1339  }
1340 
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));
1344  }
1345 
1346 
1347 // Copy branches from the buffer into two nodes according to the partition.
1348  RTREE_TEMPLATE
1349  void RTREE_QUAL::LoadNodes(Node* a_nodeA, Node* a_nodeB, PartitionVars* a_parVars)
1350  {
1351  ASSERT(a_nodeA);
1352  ASSERT(a_nodeB);
1353  ASSERT(a_parVars);
1354 
1355  for (int index=0; index < a_parVars->m_total; ++index)
1356  {
1357  ASSERT(a_parVars->m_partition[index] == 0 || a_parVars->m_partition[index] == 1);
1358 
1359  if (a_parVars->m_partition[index] == 0)
1360  {
1361  AddBranch(&a_parVars->m_branchBuf[index], a_nodeA, NULL);
1362  }
1363  else if (a_parVars->m_partition[index] == 1)
1364  {
1365  AddBranch(&a_parVars->m_branchBuf[index], a_nodeB, NULL);
1366  }
1367  }
1368  }
1369 
1370 
1371 // Initialize a PartitionVars structure.
1372  RTREE_TEMPLATE
1373  void RTREE_QUAL::InitParVars(PartitionVars* a_parVars, int a_maxRects, int a_minFill)
1374  {
1375  ASSERT(a_parVars);
1376 
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)
1382  {
1383  a_parVars->m_taken[index] = false;
1384  a_parVars->m_partition[index] = -1;
1385  }
1386  }
1387 
1388 
1389  RTREE_TEMPLATE
1390  void RTREE_QUAL::PickSeeds(PartitionVars* a_parVars)
1391  {
1392  int seed0, seed1;
1393  seed0 = 0;
1394  seed1 = 0;
1395  ELEMTYPEREAL worst, waste;
1396  ELEMTYPEREAL area[MAXNODES+1];
1397 
1398  for (int index=0; index<a_parVars->m_total; ++index)
1399  {
1400  area[index] = CalcRectVolume(&a_parVars->m_branchBuf[index].m_rect);
1401  }
1402 
1403  worst = -a_parVars->m_coverSplitArea - 1;
1404  for (int indexA=0; indexA < a_parVars->m_total-1; ++indexA)
1405  {
1406  for (int indexB = indexA+1; indexB < a_parVars->m_total; ++indexB)
1407  {
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];
1410  if (waste > worst)
1411  {
1412  worst = waste;
1413  seed0 = indexA;
1414  seed1 = indexB;
1415  }
1416  }
1417  }
1418  Classify(seed0, 0, a_parVars);
1419  Classify(seed1, 1, a_parVars);
1420  }
1421 
1422 
1423 // Put a branch in one of the groups.
1424  RTREE_TEMPLATE
1425  void RTREE_QUAL::Classify(int a_index, int a_group, PartitionVars* a_parVars)
1426  {
1427  ASSERT(a_parVars);
1428  ASSERT(!a_parVars->m_taken[a_index]);
1429 
1430  a_parVars->m_partition[a_index] = a_group;
1431  a_parVars->m_taken[a_index] = true;
1432 
1433  if (a_parVars->m_count[a_group] == 0)
1434  {
1435  a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect;
1436  }
1437  else
1438  {
1439  a_parVars->m_cover[a_group] = CombineRect(&a_parVars->m_branchBuf[a_index].m_rect, &a_parVars->m_cover[a_group]);
1440  }
1441  a_parVars->m_area[a_group] = CalcRectVolume(&a_parVars->m_cover[a_group]);
1442  ++a_parVars->m_count[a_group];
1443  }
1444 
1445 
1446 // Delete a data rectangle from an index structure.
1447 // Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node.
1448 // Returns 1 if record not found, 0 if success.
1449 // RemoveRect provides for eliminating the root.
1450  RTREE_TEMPLATE
1451  bool RTREE_QUAL::RemoveRect(Rect* a_rect, const DATATYPE& a_id, Node** a_root)
1452  {
1453  ASSERT(a_rect && a_root);
1454  ASSERT(*a_root);
1455 
1456  Node* tempNode;
1457  ListNode* reInsertList = NULL;
1458 
1459  if (!RemoveRectRec(a_rect, a_id, *a_root, &reInsertList))
1460  {
1461  // Found and deleted a data item
1462  // Reinsert any branches from eliminated nodes
1463  while (reInsertList)
1464  {
1465  tempNode = reInsertList->m_node;
1466 
1467  for (int index = 0; index < tempNode->m_count; ++index)
1468  {
1469  InsertRect(&(tempNode->m_branch[index].m_rect),
1470  tempNode->m_branch[index].m_data,
1471  a_root,
1472  tempNode->m_level);
1473  }
1474 
1475  ListNode* remLNode = reInsertList;
1476  reInsertList = reInsertList->m_next;
1477 
1478  FreeNode(remLNode->m_node);
1479  FreeListNode(remLNode);
1480  }
1481 
1482  // Check for redundant root (not leaf, 1 child) and eliminate
1483  if ((*a_root)->m_count == 1 && (*a_root)->IsInternalNode())
1484  {
1485  tempNode = (*a_root)->m_branch[0].m_child;
1486 
1487  ASSERT(tempNode);
1488  FreeNode(*a_root);
1489  *a_root = tempNode;
1490  }
1491  return false;
1492  }
1493  else
1494  {
1495  return true;
1496  }
1497  }
1498 
1499 
1500 // Delete a rectangle from non-root part of an index structure.
1501 // Called by RemoveRect. Descends tree recursively,
1502 // merges branches on the way back up.
1503 // Returns 1 if record not found, 0 if success.
1504  RTREE_TEMPLATE
1505  bool RTREE_QUAL::RemoveRectRec(Rect* a_rect, const DATATYPE& a_id, Node* a_node, ListNode** a_listNode)
1506  {
1507  ASSERT(a_rect && a_node && a_listNode);
1508  ASSERT(a_node->m_level >= 0);
1509 
1510  if (a_node->IsInternalNode()) // not a leaf node
1511  {
1512  for (int index = 0; index < a_node->m_count; ++index)
1513  {
1514  if (Overlap(a_rect, &(a_node->m_branch[index].m_rect)))
1515  {
1516  if (!RemoveRectRec(a_rect, a_id, a_node->m_branch[index].m_child, a_listNode))
1517  {
1518  if (a_node->m_branch[index].m_child->m_count >= MINNODES)
1519  {
1520  // child removed, just resize parent rect
1521  a_node->m_branch[index].m_rect = NodeCover(a_node->m_branch[index].m_child);
1522  }
1523  else
1524  {
1525  // child removed, not enough entries in node, eliminate node
1526  ReInsert(a_node->m_branch[index].m_child, a_listNode);
1527  DisconnectBranch(a_node, index); // Must return after this call as count has changed
1528  }
1529  return false;
1530  }
1531  }
1532  }
1533  return true;
1534  }
1535  else // A leaf node
1536  {
1537  for (int index = 0; index < a_node->m_count; ++index)
1538  {
1539  if (a_node->m_branch[index].m_child == (Node*)a_id)
1540  {
1541  DisconnectBranch(a_node, index); // Must return after this call as count has changed
1542  return false;
1543  }
1544  }
1545  return true;
1546  }
1547  }
1548 
1549 
1550 // Decide whether two rectangles overlap.
1551  RTREE_TEMPLATE
1552  bool RTREE_QUAL::Overlap(Rect* a_rectA, Rect* a_rectB)
1553  {
1554  ASSERT(a_rectA && a_rectB);
1555 
1556  for (int index=0; index < NUMDIMS; ++index)
1557  {
1558  if (a_rectA->m_min[index] > a_rectB->m_max[index] ||
1559  a_rectB->m_min[index] > a_rectA->m_max[index])
1560  {
1561  return false;
1562  }
1563  }
1564  return true;
1565  }
1566 
1567 
1568 // Add a node to the reinsertion list. All its branches will later
1569 // be reinserted into the index structure.
1570  RTREE_TEMPLATE
1571  void RTREE_QUAL::ReInsert(Node* a_node, ListNode** a_listNode)
1572  {
1573  ListNode* newListNode;
1574 
1575  newListNode = AllocListNode();
1576  newListNode->m_node = a_node;
1577  newListNode->m_next = *a_listNode;
1578  *a_listNode = newListNode;
1579  }
1580 
1581 
1582 // Search in an index tree or subtree for all data retangles that overlap the argument rectangle.
1583  RTREE_TEMPLATE
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)
1585  {
1586  ASSERT(a_node);
1587  ASSERT(a_node->m_level >= 0);
1588  ASSERT(a_rect);
1589 
1590  if (a_node->IsInternalNode()) // This is an internal node in the tree
1591  {
1592  for (int index=0; index < a_node->m_count; ++index)
1593  {
1594  if (Overlap(a_rect, &a_node->m_branch[index].m_rect))
1595  {
1596  if (!Search(a_node->m_branch[index].m_child, a_rect, a_foundCount, a_resultCallback, a_context))
1597  {
1598  return false; // Don't continue searching
1599  }
1600  }
1601  }
1602  }
1603  else // This is a leaf node
1604  {
1605  for (int index=0; index < a_node->m_count; ++index)
1606  {
1607  if (Overlap(a_rect, &a_node->m_branch[index].m_rect))
1608  {
1609  DATATYPE& id = a_node->m_branch[index].m_data;
1610 
1611  // NOTE: There are different ways to return results. Here's where to modify
1612  if (&a_resultCallback)
1613  {
1614  ++a_foundCount;
1615  if (!a_resultCallback(id, a_context))
1616  {
1617  return false; // Don't continue searching
1618  }
1619  }
1620  }
1621  }
1622  }
1623 
1624  return true; // Continue searching
1625  }
1626 
1627 }
1628 
1629 #undef RTREE_TEMPLATE
1630 #undef RTREE_QUAL
1631 
1632 #endif //RTREE_H
void GetFirst(Iterator &a_it)
Get 'first' for iteration.
Definition: RTree.h:254
A link list of nodes for reinsertion after a delete operation.
Definition: RTree.h:334
Variables for finding a split partition.
Definition: RTree.h:341
DATATYPE & operator*()
Access the current data element. Caller must be sure iterator is not NULL first.
Definition: RTree.h:144
bool IsNull()
Is iterator invalid.
Definition: RTree.h:132
Node * m_child
Child node.
Definition: RTree.h:311
Contains all classes and functions for the VoxelFarm engine.
ELEMTYPEREAL m_unitSphereVolume
Unit sphere constant for required number of dimensions.
Definition: RTree.h:393
Max elements in node.
Definition: RTree.h:61
DATATYPE m_data
Data Id or Ptr.
Definition: RTree.h:312
Minimal bounding rectangle (n-dimensional)
Definition: RTree.h:297
Branch m_branch[MAXNODES]
Branch.
Definition: RTree.h:330
Iterator is not remove safe.
Definition: RTree.h:110
bool IsNull(Iterator &a_it)
Is iterator NULL, or at end?
Definition: RTree.h:283
void Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE &a_dataId)
Node for each branch level.
Definition: RTree.h:317
DATATYPE & GetAt(Iterator &a_it)
Get object at iterator position.
Definition: RTree.h:289
int m_level
Leaf is zero, others positive.
Definition: RTree.h:329
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)
int m_count
Count.
Definition: RTree.h:328
Rect m_rect
Bounds.
Definition: RTree.h:308
bool Save(const char *a_fileName)
Save tree contents to file.
ELEMTYPE m_min[NUMDIMS]
Min dimensions of bounding box.
Definition: RTree.h:299
Min elements in node.
Definition: RTree.h:62
ELEMTYPE m_max[NUMDIMS]
Max dimensions of bounding box.
Definition: RTree.h:300
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.
Definition: RTree.h:160
ListNode * m_next
Next in list.
Definition: RTree.h:336
Node * m_node
Node.
Definition: RTree.h:337
void GetBounds(ELEMTYPE a_min[NUMDIMS], ELEMTYPE a_max[NUMDIMS])
Get the bounds for this node.
Definition: RTree.h:166
const DATATYPE & operator*() const
Access the current data element. Caller must be sure iterator is not NULL first.
Definition: RTree.h:152
void GetNext(Iterator &a_it)
Get Next for iteration.
Definition: RTree.h:277
Node * m_root
Root of tree.
Definition: RTree.h:392
bool Load(const char *a_fileName)
Load tree contents from file.
bool IsNotNull()
Is iterator pointing to valid data.
Definition: RTree.h:138
void RemoveAll()
Remove all entries from tree.