28 #define ASSERT assert // RTree uses ASSERT( condition ) 34 #define RTREE_TEMPLATE template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES> 35 #define RTREE_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES> 37 #define RTREE_DONT_USE_MEMPOOLS // This version does not contain a fixed memory allocator, fill in lines with EXAMPLE to implement one. 38 #define RTREE_USE_SPHERICAL_VOLUME // Better split classification, may be slower on some systems 65 template <
class DATATYPE,
class ELEMTYPE,
int NUMDIMS,
66 class ELEMTYPEREAL = ELEMTYPE,
int TMAXNODES = 8,
int TMINNODES = TMAXNODES / 2 >
93 void Insert(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE &a_dataId );
99 void Remove(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE &a_dataId );
108 int Search(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
bool a_resultCallback( DATATYPE a_data,
void *a_context ),
void *a_context );
117 bool Load(
const char *a_fileName );
119 bool Load( RTFileStream &a_stream );
123 bool Save(
const char *a_fileName );
125 bool Save( RTFileStream &a_stream );
135 enum { MAX_STACK = 32 };
139 Node *m_node =
nullptr;
140 int m_branchIndex = 0;
145 Iterator() { Init(); }
148 bool IsNull()
const {
return ( m_tos <= 0 ); }
151 bool IsNotNull()
const {
return ( m_tos > 0 ); }
156 ASSERT( IsNotNull() );
157 StackElement &curTos = m_stack[m_tos - 1];
158 return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
164 ASSERT( IsNotNull() );
165 StackElement &curTos = m_stack[m_tos - 1];
166 return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
170 bool operator++() {
return FindNextData(); }
175 void Init() { m_tos = 0; }
186 StackElement curTos = Pop();
188 if ( curTos.m_node->IsLeaf() )
191 if ( curTos.m_branchIndex + 1 < curTos.m_node->m_count )
194 Push( curTos.m_node, curTos.m_branchIndex + 1 );
201 if ( curTos.m_branchIndex + 1 < curTos.m_node->m_count )
205 Push( curTos.m_node, curTos.m_branchIndex + 1 );
208 Node *nextLevelnode = curTos.m_node->m_branch[curTos.m_branchIndex].m_child;
209 Push( nextLevelnode, 0 );
212 if ( nextLevelnode->IsLeaf() )
221 void Push( Node *a_node,
int a_branchIndex )
223 m_stack[m_tos].m_node = a_node;
224 m_stack[m_tos].m_branchIndex = a_branchIndex;
226 ASSERT( m_tos <= MAX_STACK );
234 return m_stack[m_tos];
237 StackElement m_stack[MAX_STACK];
244 void GetFirst( Iterator &a_it )
247 if ( m_root && ( m_root->m_count > 0 ) )
249 a_it.Push( m_root, 0 );
255 void GetNext( Iterator &a_it ) { ++a_it; }
258 bool IsNull( Iterator &a_it ) {
return a_it.IsNull(); }
261 DATATYPE &GetAt( Iterator &a_it ) {
return *a_it; }
268 ELEMTYPE m_min[NUMDIMS];
269 ELEMTYPE m_max[NUMDIMS];
288 bool IsInternalNode() {
return ( m_level > 0 ); }
289 bool IsLeaf() {
return ( m_level == 0 ); }
293 Branch m_branch[MAXNODES];
306 int m_partition[MAXNODES + 1];
309 int m_taken[MAXNODES + 1];
312 ELEMTYPEREAL m_area[2];
314 Branch m_branchBuf[MAXNODES + 1];
317 ELEMTYPEREAL m_coverSplitArea;
321 void FreeNode( Node *a_node );
322 void InitNode( Node *a_node );
323 void InitRect( Rect *a_rect );
324 bool InsertRectRec( Rect *a_rect,
const DATATYPE &a_id, Node *a_node, Node **a_newNode,
int a_level );
325 bool InsertRect( Rect *a_rect,
const DATATYPE &a_id, Node **a_root,
int a_level );
326 Rect NodeCover( Node *a_node );
327 bool AddBranch( Branch *a_branch, Node *a_node, Node **a_newNode );
328 void DisconnectBranch( Node *a_node,
int a_index );
329 int PickBranch( Rect *a_rect, Node *a_node );
330 Rect CombineRect( Rect *a_rectA, Rect *a_rectB );
331 void SplitNode( Node *a_node, Branch *a_branch, Node **a_newNode );
332 ELEMTYPEREAL RectSphericalVolume( Rect *a_rect );
333 ELEMTYPEREAL RectVolume( Rect *a_rect );
334 ELEMTYPEREAL CalcRectVolume( Rect *a_rect );
335 void GetBranches( Node *a_node, Branch *a_branch, PartitionVars *a_parVars );
336 void ChoosePartition( PartitionVars *a_parVars,
int a_minFill );
337 void LoadNodes( Node *a_nodeA, Node *a_nodeB, PartitionVars *a_parVars );
338 void InitParVars( PartitionVars *a_parVars,
int a_maxRects,
int a_minFill );
339 void PickSeeds( PartitionVars *a_parVars );
340 void Classify(
int a_index,
int a_group, PartitionVars *a_parVars );
341 bool RemoveRect( Rect *a_rect,
const DATATYPE &a_id, Node **a_root );
342 bool RemoveRectRec( Rect *a_rect,
const DATATYPE &a_id, Node *a_node, ListNode **a_listNode );
343 ListNode *AllocListNode();
344 void FreeListNode( ListNode *a_listNode );
345 bool Overlap( Rect *a_rectA, Rect *a_rectB );
346 void ReInsert( Node *a_node, ListNode **a_listNode );
347 bool Search( Node *a_node, Rect *a_rect,
int &a_foundCount,
bool a_resultCallback( DATATYPE a_data,
void *a_context ),
void *a_context );
348 void RemoveAllRec( Node *a_node );
350 void CountRec( Node *a_node,
int &a_count );
352 bool SaveRec( Node *a_node, RTFileStream &a_stream );
353 bool LoadRec( Node *a_node, RTFileStream &a_stream );
356 ELEMTYPEREAL m_unitSphereVolume;
368 FILE *m_file =
nullptr;
384 RTFileStream(
const RTFileStream &other ) =
delete;
386 RTFileStream &operator=(
const RTFileStream &other ) =
delete;
388 bool OpenRead(
const char *a_fileName )
393 m_file = fopen( a_fileName,
"rb" );
394 return m_file !=
nullptr;
397 bool OpenWrite(
const char *a_fileName )
402 m_file = fopen( a_fileName,
"wb" );
403 return m_file !=
nullptr;
415 template<
typename TYPE >
416 size_t Write(
const TYPE &a_value )
419 return fwrite( static_cast< void * >( &a_value ),
sizeof( a_value ), 1, m_file );
422 template<
typename TYPE >
423 size_t WriteArray(
const TYPE *a_array,
int a_count )
426 return fwrite( static_cast< void * >( a_array ),
sizeof( TYPE ) * a_count, 1, m_file );
429 template<
typename TYPE >
430 size_t Read( TYPE &a_value )
433 return fread( static_cast< void * >( &a_value ),
sizeof( a_value ), 1, m_file );
436 template<
typename TYPE >
437 size_t ReadArray( TYPE *a_array,
int a_count )
440 return fread( static_cast< void * >( a_array ),
sizeof( TYPE ) * a_count, 1, m_file );
449 ASSERT( MAXNODES > MINNODES );
450 ASSERT( MINNODES > 0 );
455 ASSERT(
sizeof( DATATYPE ) ==
sizeof(
void * ) ||
sizeof( DATATYPE ) ==
sizeof(
int ) );
458 const float UNIT_SPHERE_VOLUMES[] =
460 0.000000f, 2.000000f, 3.141593f,
461 4.188790f, 4.934802f, 5.263789f,
462 5.167713f, 4.724766f, 4.058712f,
463 3.298509f, 2.550164f, 1.884104f,
464 1.335263f, 0.910629f, 0.599265f,
465 0.381443f, 0.235331f, 0.140981f,
466 0.082146f, 0.046622f, 0.025807f,
469 m_root = AllocNode();
471 m_unitSphereVolume =
static_cast< ELEMTYPEREAL
>( UNIT_SPHERE_VOLUMES[NUMDIMS] );
483 void RTREE_QUAL::Insert(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE &a_dataId )
486 for (
int index = 0; index < NUMDIMS; ++index )
488 ASSERT( a_min[index] <= a_max[index] );
494 for (
int axis = 0; axis < NUMDIMS; ++axis )
496 rect.m_min[axis] = a_min[axis];
497 rect.m_max[axis] = a_max[axis];
500 InsertRect( &rect, a_dataId, &m_root, 0 );
505 void RTREE_QUAL::Remove(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
const DATATYPE &a_dataId )
508 for (
int index = 0; index < NUMDIMS; ++index )
510 ASSERT( a_min[index] <= a_max[index] );
516 for (
int axis = 0; axis < NUMDIMS; ++axis )
518 rect.m_min[axis] = a_min[axis];
519 rect.m_max[axis] = a_max[axis];
522 RemoveRect( &rect, a_dataId, &m_root );
527 int RTREE_QUAL::Search(
const ELEMTYPE a_min[NUMDIMS],
const ELEMTYPE a_max[NUMDIMS],
bool a_resultCallback( DATATYPE a_data,
void *a_context ),
void *a_context )
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, a_resultCallback, a_context );
554 int RTREE_QUAL::Count()
557 CountRec( m_root, count );
565 void RTREE_QUAL::CountRec( Node *a_node,
int &a_count )
567 if ( a_node->IsInternalNode() )
569 for (
int index = 0; index < a_node->m_count; ++index )
571 CountRec( a_node->m_branch[index].m_child, a_count );
576 a_count += a_node->m_count;
582 bool RTREE_QUAL::Load(
const char *a_fileName )
587 if ( !stream.OpenRead( a_fileName ) )
592 bool result = Load( stream );
602 bool RTREE_QUAL::Load( RTFileStream &a_stream )
605 int _dataFileId = (
'R' << 0 ) | (
'T' << 8 ) | (
'R' << 16 ) | (
'E' << 24 );
606 int _dataSize =
sizeof( DATATYPE );
607 int _dataNumDims = NUMDIMS;
608 int _dataElemSize =
sizeof( ELEMTYPE );
609 int _dataElemRealSize =
sizeof( ELEMTYPEREAL );
610 int _dataMaxNodes = TMAXNODES;
611 int _dataMinNodes = TMINNODES;
616 int dataElemSize = 0;
617 int dataElemRealSize = 0;
618 int dataMaxNodes = 0;
619 int dataMinNodes = 0;
621 a_stream.Read( dataFileId );
622 a_stream.Read( dataSize );
623 a_stream.Read( dataNumDims );
624 a_stream.Read( dataElemSize );
625 a_stream.Read( dataElemRealSize );
626 a_stream.Read( dataMaxNodes );
627 a_stream.Read( dataMinNodes );
632 if ( ( dataFileId == _dataFileId )
633 && ( dataSize == _dataSize )
634 && ( dataNumDims == _dataNumDims )
635 && ( dataElemSize == _dataElemSize )
636 && ( dataElemRealSize == _dataElemRealSize )
637 && ( dataMaxNodes == _dataMaxNodes )
638 && ( dataMinNodes == _dataMinNodes )
642 result = LoadRec( m_root, a_stream );
650 bool RTREE_QUAL::LoadRec( Node *a_node, RTFileStream &a_stream )
652 a_stream.Read( a_node->m_level );
653 a_stream.Read( a_node->m_count );
655 if ( a_node->IsInternalNode() )
657 for (
int index = 0; index < a_node->m_count; ++index )
659 Branch *curBranch = &a_node->m_branch[index];
661 a_stream.ReadArray( curBranch->m_rect.m_min, NUMDIMS );
662 a_stream.ReadArray( curBranch->m_rect.m_max, NUMDIMS );
664 curBranch->m_child = AllocNode();
665 LoadRec( curBranch->m_child, a_stream );
670 for (
int index = 0; index < a_node->m_count; ++index )
672 Branch *curBranch = &a_node->m_branch[index];
674 a_stream.ReadArray( curBranch->m_rect.m_min, NUMDIMS );
675 a_stream.ReadArray( curBranch->m_rect.m_max, NUMDIMS );
677 a_stream.Read( curBranch->m_data );
686 bool RTREE_QUAL::Save(
const char *a_fileName )
689 if ( !stream.OpenWrite( a_fileName ) )
694 bool result = Save( stream );
703 bool RTREE_QUAL::Save( RTFileStream &a_stream )
706 int dataFileId = (
'R' << 0 ) | (
'T' << 8 ) | (
'R' << 16 ) | (
'E' << 24 );
707 int dataSize =
sizeof( DATATYPE );
708 int dataNumDims = NUMDIMS;
709 int dataElemSize =
sizeof( ELEMTYPE );
710 int dataElemRealSize =
sizeof( ELEMTYPEREAL );
711 int dataMaxNodes = TMAXNODES;
712 int dataMinNodes = TMINNODES;
714 a_stream.Write( dataFileId );
715 a_stream.Write( dataSize );
716 a_stream.Write( dataNumDims );
717 a_stream.Write( dataElemSize );
718 a_stream.Write( dataElemRealSize );
719 a_stream.Write( dataMaxNodes );
720 a_stream.Write( dataMinNodes );
723 bool result = SaveRec( m_root, a_stream );
730 bool RTREE_QUAL::SaveRec( Node *a_node, RTFileStream &a_stream )
732 a_stream.Write( a_node->m_level );
733 a_stream.Write( a_node->m_count );
735 if ( a_node->IsInternalNode() )
737 for (
int index = 0; index < a_node->m_count; ++index )
739 Branch *curBranch = &a_node->m_branch[index];
741 a_stream.WriteArray( curBranch->m_rect.m_min, NUMDIMS );
742 a_stream.WriteArray( curBranch->m_rect.m_max, NUMDIMS );
744 SaveRec( curBranch->m_child, a_stream );
749 for (
int index = 0; index < a_node->m_count; ++index )
751 Branch *curBranch = &a_node->m_branch[index];
753 a_stream.WriteArray( curBranch->m_rect.m_min, NUMDIMS );
754 a_stream.WriteArray( curBranch->m_rect.m_max, NUMDIMS );
756 a_stream.Write( curBranch->m_data );
765 void RTREE_QUAL::RemoveAll()
770 m_root = AllocNode();
776 void RTREE_QUAL::Reset()
778 #ifdef RTREE_DONT_USE_MEMPOOLS 780 RemoveAllRec( m_root );
781 #else // RTREE_DONT_USE_MEMPOOLS 784 #endif // RTREE_DONT_USE_MEMPOOLS 789 void RTREE_QUAL::RemoveAllRec( Node *a_node )
792 ASSERT( a_node->m_level >= 0 );
794 if ( a_node->IsInternalNode() )
796 for (
int index = 0; index < a_node->m_count; ++index )
798 RemoveAllRec( a_node->m_branch[index].m_child );
806 typename RTREE_QUAL::Node *RTREE_QUAL::AllocNode()
808 Node *newNode =
nullptr;
809 #ifdef RTREE_DONT_USE_MEMPOOLS 811 #else // RTREE_DONT_USE_MEMPOOLS 813 #endif // RTREE_DONT_USE_MEMPOOLS 820 void RTREE_QUAL::FreeNode( Node *a_node )
824 #ifdef RTREE_DONT_USE_MEMPOOLS 826 #else // RTREE_DONT_USE_MEMPOOLS 828 #endif // RTREE_DONT_USE_MEMPOOLS 835 typename RTREE_QUAL::ListNode *RTREE_QUAL::AllocListNode()
837 #ifdef RTREE_DONT_USE_MEMPOOLS 839 #else // RTREE_DONT_USE_MEMPOOLS 841 #endif // RTREE_DONT_USE_MEMPOOLS 846 void RTREE_QUAL::FreeListNode( ListNode *a_listNode )
848 #ifdef RTREE_DONT_USE_MEMPOOLS 850 #else // RTREE_DONT_USE_MEMPOOLS 852 #endif // RTREE_DONT_USE_MEMPOOLS 857 void RTREE_QUAL::InitNode( Node *a_node )
860 a_node->m_level = -1;
865 void RTREE_QUAL::InitRect( Rect *a_rect )
867 for (
int index = 0; index < NUMDIMS; ++index )
869 a_rect->m_min[index] =
static_cast< ELEMTYPE
>( 0 );
870 a_rect->m_max[index] =
static_cast< ELEMTYPE
>( 0 );
883 bool RTREE_QUAL::InsertRectRec( Rect *a_rect,
const DATATYPE &a_id, Node *a_node, Node **a_newNode,
int a_level )
885 ASSERT( a_rect && a_node && a_newNode );
886 ASSERT( a_level >= 0 && a_level <= a_node->m_level );
890 Node *otherNode =
nullptr;
893 if ( a_node->m_level > a_level )
895 index = PickBranch( a_rect, a_node );
896 if ( !InsertRectRec( a_rect, a_id, a_node->m_branch[index].m_child, &otherNode, a_level ) )
899 a_node->m_branch[index].m_rect = CombineRect( a_rect, & ( a_node->m_branch[index].m_rect ) );
904 a_node->m_branch[index].m_rect = NodeCover( a_node->m_branch[index].m_child );
905 branch.m_child = otherNode;
906 branch.m_rect = NodeCover( otherNode );
907 return AddBranch( &branch, a_node, a_newNode );
910 else if ( a_node->m_level == a_level )
912 branch.m_rect = *a_rect;
913 branch.m_child =
reinterpret_cast< Node *
>( a_id );
915 return AddBranch( &branch, a_node, a_newNode );
934 bool RTREE_QUAL::InsertRect( Rect *a_rect,
const DATATYPE &a_id, Node **a_root,
int a_level )
936 ASSERT( a_rect && a_root );
937 ASSERT( a_level >= 0 && a_level <= ( *a_root )->m_level );
939 for (
int index = 0; index < NUMDIMS; ++index )
941 ASSERT( a_rect->m_min[index] <= a_rect->m_max[index] );
945 Node *newRoot =
nullptr;
946 Node *newNode =
nullptr;
949 if ( InsertRectRec( a_rect, a_id, *a_root, &newNode, a_level ) )
951 newRoot = AllocNode();
952 newRoot->m_level = ( *a_root )->m_level + 1;
953 branch.m_rect = NodeCover( *a_root );
954 branch.m_child = *a_root;
955 AddBranch( &branch, newRoot,
nullptr );
956 branch.m_rect = NodeCover( newNode );
957 branch.m_child = newNode;
958 AddBranch( &branch, newRoot,
nullptr );
969 typename RTREE_QUAL::Rect RTREE_QUAL::NodeCover( Node *a_node )
973 bool firstTime =
true;
977 for (
int index = 0; index < a_node->m_count; ++index )
981 rect = a_node->m_branch[index].m_rect;
986 rect = CombineRect( &rect, & ( a_node->m_branch[index].m_rect ) );
999 bool RTREE_QUAL::AddBranch( Branch *a_branch, Node *a_node, Node **a_newNode )
1004 if ( a_node->m_count < MAXNODES )
1006 a_node->m_branch[a_node->m_count] = *a_branch;
1013 ASSERT( a_newNode );
1015 SplitNode( a_node, a_branch, a_newNode );
1024 void RTREE_QUAL::DisconnectBranch( Node *a_node,
int a_index )
1026 ASSERT( a_node && ( a_index >= 0 ) && ( a_index < MAXNODES ) );
1027 ASSERT( a_node->m_count > 0 );
1030 a_node->m_branch[a_index] = a_node->m_branch[a_node->m_count - 1];
1042 int RTREE_QUAL::PickBranch( Rect *a_rect, Node *a_node )
1044 ASSERT( a_rect && a_node );
1046 bool firstTime =
true;
1047 ELEMTYPEREAL increase;
1048 ELEMTYPEREAL bestIncr =
static_cast< ELEMTYPEREAL
>( -1 );
1050 ELEMTYPEREAL bestArea = 0;
1054 for (
int index = 0; index < a_node->m_count; ++index )
1056 Rect *curRect = &a_node->m_branch[index].m_rect;
1057 area = CalcRectVolume( curRect );
1058 tempRect = CombineRect( a_rect, curRect );
1059 increase = CalcRectVolume( &tempRect ) - area;
1060 if ( ( increase < bestIncr ) || firstTime )
1064 bestIncr = increase;
1067 else if (
qgsDoubleNear( increase, bestIncr ) && ( area < bestArea ) )
1071 bestIncr = increase;
1080 typename RTREE_QUAL::Rect RTREE_QUAL::CombineRect( Rect *a_rectA, Rect *a_rectB )
1082 ASSERT( a_rectA && a_rectB );
1084 Rect newRect = { {0, }, {0, } };
1086 for (
int index = 0; index < NUMDIMS; ++index )
1088 newRect.m_min[index] = std::min( a_rectA->m_min[index], a_rectB->m_min[index] );
1089 newRect.m_max[index] = std::max( a_rectA->m_max[index], a_rectB->m_max[index] );
1102 void RTREE_QUAL::SplitNode( Node *a_node, Branch *a_branch, Node **a_newNode )
1108 PartitionVars localVars;
1109 PartitionVars *parVars = &localVars;
1113 level = a_node->m_level;
1114 GetBranches( a_node, a_branch, parVars );
1117 ChoosePartition( parVars, MINNODES );
1120 *a_newNode = AllocNode();
1121 ( *a_newNode )->m_level = a_node->m_level = level;
1122 LoadNodes( a_node, *a_newNode, parVars );
1124 ASSERT( ( a_node->m_count + ( *a_newNode )->m_count ) == parVars->m_total );
1130 ELEMTYPEREAL RTREE_QUAL::RectVolume( Rect *a_rect )
1134 ELEMTYPEREAL volume =
static_cast< ELEMTYPEREAL
>( 1 );
1136 for (
int index = 0; index < NUMDIMS; ++index )
1138 volume *= a_rect->m_max[index] - a_rect->m_min[index];
1141 ASSERT( volume >= static_cast< ELEMTYPEREAL >( 0 ) );
1149 ELEMTYPEREAL RTREE_QUAL::RectSphericalVolume( Rect *a_rect )
1153 ELEMTYPEREAL sumOfSquares =
static_cast< ELEMTYPEREAL
>( 0 );
1154 ELEMTYPEREAL radius;
1156 for (
int index = 0; index < NUMDIMS; ++index )
1158 ELEMTYPEREAL halfExtent = (
static_cast< ELEMTYPEREAL
>( a_rect->m_max[index] ) - static_cast< ELEMTYPEREAL >( a_rect->m_min[index] ) ) * 0.5
f;
1159 sumOfSquares += halfExtent * halfExtent;
1162 radius =
static_cast< ELEMTYPEREAL
>( std::sqrt( sumOfSquares ) );
1167 return ( radius * radius * radius * m_unitSphereVolume );
1169 else if ( NUMDIMS == 2 )
1171 return ( radius * radius * m_unitSphereVolume );
1175 return static_cast< ELEMTYPEREAL
>( std::pow( radius, NUMDIMS ) * m_unitSphereVolume );
1182 ELEMTYPEREAL RTREE_QUAL::CalcRectVolume( Rect *a_rect )
1184 #ifdef RTREE_USE_SPHERICAL_VOLUME 1185 return RectSphericalVolume( a_rect );
1186 #else // RTREE_USE_SPHERICAL_VOLUME 1187 return RectVolume( a_rect );
1188 #endif // RTREE_USE_SPHERICAL_VOLUME 1194 void RTREE_QUAL::GetBranches( Node *a_node, Branch *a_branch, PartitionVars *a_parVars )
1199 ASSERT( a_node->m_count == MAXNODES );
1203 for ( index = 0; index < MAXNODES; ++index )
1205 a_parVars->m_branchBuf[index] = a_node->m_branch[index];
1207 a_parVars->m_branchBuf[MAXNODES] = *a_branch;
1208 a_parVars->m_branchCount = MAXNODES + 1;
1211 a_parVars->m_coverSplit = a_parVars->m_branchBuf[0].m_rect;
1212 for ( index = 1; index < MAXNODES + 1; ++index )
1214 a_parVars->m_coverSplit = CombineRect( &a_parVars->m_coverSplit, &a_parVars->m_branchBuf[index].m_rect );
1216 a_parVars->m_coverSplitArea = CalcRectVolume( &a_parVars->m_coverSplit );
1234 void RTREE_QUAL::ChoosePartition( PartitionVars *a_parVars,
int a_minFill )
1236 ASSERT( a_parVars );
1238 ELEMTYPEREAL biggestDiff;
1239 int group, chosen = 0, betterGroup = 0;
1241 InitParVars( a_parVars, a_parVars->m_branchCount, a_minFill );
1242 PickSeeds( a_parVars );
1244 while ( ( ( a_parVars->m_count[0] + a_parVars->m_count[1] ) < a_parVars->m_total )
1245 && ( a_parVars->m_count[0] < ( a_parVars->m_total - a_parVars->m_minFill ) )
1246 && ( a_parVars->m_count[1] < ( a_parVars->m_total - a_parVars->m_minFill ) ) )
1248 biggestDiff =
static_cast< ELEMTYPEREAL
>( -1 );
1249 for (
int index = 0; index < a_parVars->m_total; ++index )
1251 if ( !a_parVars->m_taken[index] )
1253 Rect *curRect = &a_parVars->m_branchBuf[index].m_rect;
1254 Rect rect0 = CombineRect( curRect, &a_parVars->m_cover[0] );
1255 Rect rect1 = CombineRect( curRect, &a_parVars->m_cover[1] );
1256 ELEMTYPEREAL growth0 = CalcRectVolume( &rect0 ) - a_parVars->m_area[0];
1257 ELEMTYPEREAL growth1 = CalcRectVolume( &rect1 ) - a_parVars->m_area[1];
1258 ELEMTYPEREAL diff = growth1 - growth0;
1269 if ( diff > biggestDiff )
1273 betterGroup = group;
1275 else if (
qgsDoubleNear( diff, biggestDiff ) && ( a_parVars->m_count[group] < a_parVars->m_count[betterGroup] ) )
1278 betterGroup = group;
1282 Classify( chosen, betterGroup, a_parVars );
1286 if ( ( a_parVars->m_count[0] + a_parVars->m_count[1] ) < a_parVars->m_total )
1288 if ( a_parVars->m_count[0] >= a_parVars->m_total - a_parVars->m_minFill )
1296 for (
int index = 0; index < a_parVars->m_total; ++index )
1298 if ( !a_parVars->m_taken[index] )
1300 Classify( index, group, a_parVars );
1305 ASSERT( ( a_parVars->m_count[0] + a_parVars->m_count[1] ) == a_parVars->m_total );
1306 ASSERT( ( a_parVars->m_count[0] >= a_parVars->m_minFill ) &&
1307 ( a_parVars->m_count[1] >= a_parVars->m_minFill ) );
1313 void RTREE_QUAL::LoadNodes( Node *a_nodeA, Node *a_nodeB, PartitionVars *a_parVars )
1317 ASSERT( a_parVars );
1319 for (
int index = 0; index < a_parVars->m_total; ++index )
1321 ASSERT( a_parVars->m_partition[index] == 0 || a_parVars->m_partition[index] == 1 );
1323 if ( a_parVars->m_partition[index] == 0 )
1325 AddBranch( &a_parVars->m_branchBuf[index], a_nodeA,
nullptr );
1327 else if ( a_parVars->m_partition[index] == 1 )
1329 AddBranch( &a_parVars->m_branchBuf[index], a_nodeB,
nullptr );
1337 void RTREE_QUAL::InitParVars( PartitionVars *a_parVars,
int a_maxRects,
int a_minFill )
1339 ASSERT( a_parVars );
1341 a_parVars->m_count[0] = a_parVars->m_count[1] = 0;
1342 a_parVars->m_area[0] = a_parVars->m_area[1] =
static_cast< ELEMTYPEREAL
>( 0 );
1343 a_parVars->m_total = a_maxRects;
1344 a_parVars->m_minFill = a_minFill;
1345 for (
int index = 0; index < a_maxRects; ++index )
1347 a_parVars->m_taken[index] =
false;
1348 a_parVars->m_partition[index] = -1;
1354 void RTREE_QUAL::PickSeeds( PartitionVars *a_parVars )
1356 int seed0 = 0, seed1 = 0;
1357 ELEMTYPEREAL worst, waste;
1358 ELEMTYPEREAL area[MAXNODES + 1];
1360 for (
int index = 0; index < a_parVars->m_total; ++index )
1362 area[index] = CalcRectVolume( &a_parVars->m_branchBuf[index].m_rect );
1365 worst = -a_parVars->m_coverSplitArea - 1;
1366 for (
int indexA = 0; indexA < a_parVars->m_total - 1; ++indexA )
1368 for (
int indexB = indexA + 1; indexB < a_parVars->m_total; ++indexB )
1370 Rect oneRect = CombineRect( &a_parVars->m_branchBuf[indexA].m_rect, &a_parVars->m_branchBuf[indexB].m_rect );
1371 waste = CalcRectVolume( &oneRect ) - area[indexA] - area[indexB];
1372 if ( waste > worst )
1380 Classify( seed0, 0, a_parVars );
1381 Classify( seed1, 1, a_parVars );
1387 void RTREE_QUAL::Classify(
int a_index,
int a_group, PartitionVars *a_parVars )
1389 ASSERT( a_parVars );
1390 ASSERT( !a_parVars->m_taken[a_index] );
1392 a_parVars->m_partition[a_index] = a_group;
1393 a_parVars->m_taken[a_index] =
true;
1395 if ( a_parVars->m_count[a_group] == 0 )
1397 a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect;
1401 a_parVars->m_cover[a_group] = CombineRect( &a_parVars->m_branchBuf[a_index].m_rect, &a_parVars->m_cover[a_group] );
1403 a_parVars->m_area[a_group] = CalcRectVolume( &a_parVars->m_cover[a_group] );
1404 ++a_parVars->m_count[a_group];
1413 bool RTREE_QUAL::RemoveRect( Rect *a_rect,
const DATATYPE &a_id, Node **a_root )
1415 ASSERT( a_rect && a_root );
1418 Node *tempNode =
nullptr;
1419 ListNode *reInsertList =
nullptr;
1421 if ( !RemoveRectRec( a_rect, a_id, *a_root, &reInsertList ) )
1425 while ( reInsertList )
1427 tempNode = reInsertList->m_node;
1429 for (
int index = 0; index < tempNode->m_count; ++index )
1431 InsertRect( & ( tempNode->m_branch[index].m_rect ),
1432 tempNode->m_branch[index].m_data,
1434 tempNode->m_level );
1437 ListNode *remLNode = reInsertList;
1438 reInsertList = reInsertList->m_next;
1440 FreeNode( remLNode->m_node );
1441 FreeListNode( remLNode );
1445 if ( ( *a_root )->m_count == 1 && ( *a_root )->IsInternalNode() )
1447 tempNode = ( *a_root )->m_branch[0].m_child;
1450 FreeNode( *a_root );
1467 bool RTREE_QUAL::RemoveRectRec( Rect *a_rect,
const DATATYPE &a_id, Node *a_node, ListNode **a_listNode )
1469 ASSERT( a_rect && a_node && a_listNode );
1470 ASSERT( a_node->m_level >= 0 );
1472 if ( a_node->IsInternalNode() )
1474 for (
int index = 0; index < a_node->m_count; ++index )
1476 if ( Overlap( a_rect, & ( a_node->m_branch[index].m_rect ) ) )
1478 if ( !RemoveRectRec( a_rect, a_id, a_node->m_branch[index].m_child, a_listNode ) )
1480 if ( a_node->m_branch[index].m_child->m_count >= MINNODES )
1483 a_node->m_branch[index].m_rect = NodeCover( a_node->m_branch[index].m_child );
1488 ReInsert( a_node->m_branch[index].m_child, a_listNode );
1489 DisconnectBranch( a_node, index );
1499 for (
int index = 0; index < a_node->m_count; ++index )
1501 if ( a_node->m_branch[index].m_child == reinterpret_cast< Node * >( a_id ) )
1503 DisconnectBranch( a_node, index );
1514 bool RTREE_QUAL::Overlap( Rect *a_rectA, Rect *a_rectB )
1516 ASSERT( a_rectA && a_rectB );
1518 for (
int index = 0; index < NUMDIMS; ++index )
1520 if ( a_rectA->m_min[index] > a_rectB->m_max[index] ||
1521 a_rectB->m_min[index] > a_rectA->m_max[index] )
1533 void RTREE_QUAL::ReInsert( Node *a_node, ListNode **a_listNode )
1535 ListNode *newListNode =
nullptr;
1537 newListNode = AllocListNode();
1538 newListNode->m_node = a_node;
1539 newListNode->m_next = *a_listNode;
1540 *a_listNode = newListNode;
1546 bool RTREE_QUAL::Search( Node *a_node, Rect *a_rect,
int &a_foundCount,
bool ( *a_resultCallback )( DATATYPE a_data,
void *a_context ),
void *a_context )
1549 ASSERT( a_node->m_level >= 0 );
1552 if ( a_node->IsInternalNode() )
1554 for (
int index = 0; index < a_node->m_count; ++index )
1556 if ( Overlap( a_rect, &a_node->m_branch[index].m_rect ) )
1558 if ( !Search( a_node->m_branch[index].m_child, a_rect, a_foundCount, a_resultCallback, a_context ) )
1567 for (
int index = 0; index < a_node->m_count; ++index )
1569 if ( Overlap( a_rect, &a_node->m_branch[index].m_rect ) )
1571 DATATYPE &
id = a_node->m_branch[index].m_data;
1574 if ( a_resultCallback )
1577 if ( !a_resultCallback(
id, a_context ) )
1590 #undef RTREE_TEMPLATE bool qgsDoubleNear(double a, double b, double epsilon=4 *DBL_EPSILON)
Compare two doubles (but allow some difference)
QgsMargins operator*(const QgsMargins &margins, double factor)
Returns a QgsMargins object that is formed by multiplying each component of the given margins by fact...