Revision: 73960
http://sourceforge.net/p/brlcad/code/73960
Author: starseeker
Date: 2019-09-18 19:59:37 +0000 (Wed, 18 Sep 2019)
Log Message:
-----------
footer, ws
Modified Paths:
--------------
brlcad/trunk/src/libbrep/RTree.h
Modified: brlcad/trunk/src/libbrep/RTree.h
===================================================================
--- brlcad/trunk/src/libbrep/RTree.h 2019-09-18 19:56:26 UTC (rev 73959)
+++ brlcad/trunk/src/libbrep/RTree.h 2019-09-18 19:59:37 UTC (rev 73960)
@@ -47,17 +47,17 @@
/// record information for later use.
template<class _DataType, class _ElementType, int _NumDimensions,
class _ElementTypeReal = _ElementType, int _MaxNodeCount = 8, int
_MinNodeCount = _MaxNodeCount / 2>
-class RTree
+ class RTree
{
static_assert(1 < _NumDimensions, "_NumDimensions must be larger than 1");
static_assert(0 < _MinNodeCount, "_MinNodeCount must be larger than 0");
static_assert(_MinNodeCount < _MaxNodeCount, "_MaxNodeCount must be larger
than _MinNodeCount");
static_assert(std::is_floating_point<_ElementTypeReal>::value,
"_ElementTypeReal must be floating point type");
-protected:
+ protected:
struct Node; // Fwd decl. Used by other internal structs and iterator
-public:
+ public:
using DataType = _DataType;
using ElementType = _ElementType;
using ElementTypeReal = _ElementTypeReal;
@@ -68,13 +68,13 @@
constexpr static const int kMinNodeCount = _MinNodeCount;
template<typename ValueType>
- constexpr static ElementType CastElementType(const ValueType val) noexcept
{
- return static_cast<ElementType>(val);
- }
+ constexpr static ElementType CastElementType(const ValueType val)
noexcept {
+ return static_cast<ElementType>(val);
+ }
template<typename ValueType>
- constexpr static ElementTypeReal CastElementTypeReal(const ValueType val)
noexcept {
- return static_cast<ElementTypeReal>(val);
- }
+ constexpr static ElementTypeReal CastElementTypeReal(const ValueType
val) noexcept {
+ return static_cast<ElementTypeReal>(val);
+ }
constexpr static const ElementTypeReal kElementTypeRealOne =
CastElementTypeReal(1.0);
constexpr static const ElementTypeReal kElementTypeRealZero =
CastElementTypeReal(0.0);
@@ -125,153 +125,153 @@
/// Iterator is not remove safe.
class Iterator
{
- private:
+ private:
- constexpr static const int kMaxStackSize = 32; // Max stack size.
Allows almost n^32 where n is number of branches in node
+ constexpr static const int kMaxStackSize = 32; // Max stack size.
Allows almost n^32 where n is number of branches in node
- struct StackElement
- {
- Node* m_node = nullptr;
- int m_branchIndex = 0;
- };
+ struct StackElement
+ {
+ Node* m_node = nullptr;
+ int m_branchIndex = 0;
+ };
- public:
+ public:
- Iterator() { Init(); }
+ Iterator() { Init(); }
- ~Iterator() = default;
+ ~Iterator() = default;
- /// Is iterator invalid
- bool IsNull() const noexcept { return (m_tos <= 0); }
+ /// Is iterator invalid
+ bool IsNull() const noexcept { return (m_tos <= 0); }
- /// Is iterator pointing to valid data
- bool IsNotNull() const noexcept { return (m_tos > 0); }
+ /// Is iterator pointing to valid data
+ bool IsNotNull() const noexcept { return (m_tos > 0); }
- /// Access the current data element. Caller must be sure iterator is
not NULL first.
- DataType& operator*()
- {
- RTreeAssert(IsNotNull());
- auto& curTos = m_stack[m_tos - 1];
- return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
- }
+ /// Access the current data element. Caller must be sure iterator
is not NULL first.
+ DataType& operator*()
+ {
+ RTreeAssert(IsNotNull());
+ auto& curTos = m_stack[m_tos - 1];
+ return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
+ }
- /// Access the current data element. Caller must be sure iterator is
not NULL first.
- const DataType& operator*() const
- {
- RTreeAssert(IsNotNull());
- auto& curTos = m_stack[m_tos - 1];
- return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
- }
+ /// Access the current data element. Caller must be sure iterator
is not NULL first.
+ const DataType& operator*() const
+ {
+ RTreeAssert(IsNotNull());
+ auto& curTos = m_stack[m_tos - 1];
+ return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;
+ }
- /// Find the next data element
- bool operator++() { return FindNextData(); }
+ /// Find the next data element
+ bool operator++() { return FindNextData(); }
- /// Get the bounds for this node
- void GetBounds(Element& a_min, Element& a_max)
- {
- RTreeAssert(IsNotNull());
- auto& curTos = m_stack[m_tos - 1];
- auto& curBranch = curTos.m_node->m_branch[curTos.m_branchIndex];
+ /// Get the bounds for this node
+ void GetBounds(Element& a_min, Element& a_max)
+ {
+ RTreeAssert(IsNotNull());
+ auto& curTos = m_stack[m_tos - 1];
+ auto& curBranch = curTos.m_node->m_branch[curTos.m_branchIndex];
- for (int index = 0; index < kNumDimensions; ++index)
- {
- a_min[index] = curBranch.m_rect.m_min[index];
- a_max[index] = curBranch.m_rect.m_max[index];
- }
- }
+ for (int index = 0; index < kNumDimensions; ++index)
+ {
+ a_min[index] = curBranch.m_rect.m_min[index];
+ a_max[index] = curBranch.m_rect.m_max[index];
+ }
+ }
- private:
+ private:
- /// Reset iterator
- void Init() { m_tos = 0; }
+ /// Reset iterator
+ void Init() { m_tos = 0; }
- /// Find the next data element in the tree (For internal use only)
- bool FindNextData()
- {
- for (;;)
- {
- if (m_tos <= 0)
- {
- return false;
- }
- auto curTos = Pop(); // Copy stack top cause it may change as
we use it
+ /// Find the next data element in the tree (For internal use only)
+ bool FindNextData()
+ {
+ for (;;)
+ {
+ if (m_tos <= 0)
+ {
+ return false;
+ }
+ auto curTos = Pop(); // Copy stack top cause it may change
as we use it
- if (curTos.m_node->IsLeaf())
- {
- // Keep walking through data while we can
- if (curTos.m_branchIndex + 1 < curTos.m_node->m_count)
- {
- // There is more data, just point to the next one
- Push(curTos.m_node, curTos.m_branchIndex + 1);
- return true;
- }
- // No more data, so it will fall back to previous level
- }
- else
- {
- if (curTos.m_branchIndex + 1 < curTos.m_node->m_count)
- {
- // Push sibling on for future tree walk
- // This is the 'fall back' node when we finish with
the current level
- Push(curTos.m_node, curTos.m_branchIndex + 1);
- }
- // Since cur node is not a leaf, push first of next level
to get deeper into the tree
- auto nextLevelnode =
curTos.m_node->m_branch[curTos.m_branchIndex].m_child;
- Push(nextLevelnode, 0);
+ if (curTos.m_node->IsLeaf())
+ {
+ // Keep walking through data while we can
+ if (curTos.m_branchIndex + 1 < curTos.m_node->m_count)
+ {
+ // There is more data, just point to the next one
+ Push(curTos.m_node, curTos.m_branchIndex + 1);
+ return true;
+ }
+ // No more data, so it will fall back to previous level
+ }
+ else
+ {
+ if (curTos.m_branchIndex + 1 < curTos.m_node->m_count)
+ {
+ // Push sibling on for future tree walk
+ // This is the 'fall back' node when we finish with
the current level
+ Push(curTos.m_node, curTos.m_branchIndex + 1);
+ }
+ // Since cur node is not a leaf, push first of next
level to get deeper into the tree
+ auto nextLevelnode =
curTos.m_node->m_branch[curTos.m_branchIndex].m_child;
+ Push(nextLevelnode, 0);
- // If we pushed on a new leaf, exit as the data is ready
at TOS
- if (nextLevelnode->IsLeaf())
- {
- return true;
- }
- }
- }
- }
+ // If we pushed on a new leaf, exit as the data is
ready at TOS
+ if (nextLevelnode->IsLeaf())
+ {
+ return true;
+ }
+ }
+ }
+ }
- /// Push node and branch onto iteration stack (For internal use only)
- void Push(Node* a_node, int a_branchIndex)
- {
- m_stack[m_tos].m_node = a_node;
- m_stack[m_tos].m_branchIndex = a_branchIndex;
- ++m_tos;
- RTreeAssert(m_tos <= kMaxStackSize);
- }
+ /// Push node and branch onto iteration stack (For internal use
only)
+ void Push(Node* a_node, int a_branchIndex)
+ {
+ m_stack[m_tos].m_node = a_node;
+ m_stack[m_tos].m_branchIndex = a_branchIndex;
+ ++m_tos;
+ RTreeAssert(m_tos <= kMaxStackSize);
+ }
- /// Pop element off iteration stack (For internal use only)
- StackElement& Pop()
- {
- RTreeAssert(m_tos > 0);
- --m_tos;
- return m_stack[m_tos];
- }
+ /// Pop element off iteration stack (For internal use only)
+ StackElement& Pop()
+ {
+ RTreeAssert(m_tos > 0);
+ --m_tos;
+ return m_stack[m_tos];
+ }
- StackElement m_stack[kMaxStackSize]; ///< Stack as we are
doing iteration instead of recursion
- int m_tos = 0; ///< Top Of Stack index
+ StackElement m_stack[kMaxStackSize]; ///< Stack as we are
doing iteration instead of recursion
+ int m_tos = 0; ///< Top Of Stack
index
- friend class RTree; // Allow hiding of non-public functions while
allowing manipulation by logical owner
+ friend class RTree; // Allow hiding of non-public functions while
allowing manipulation by logical owner
};
/// Get 'first' for iteration
void GetFirst(Iterator& a_it) const
{
- a_it.Init();
- auto first = m_root;
- while (first)
- {
- if (first->IsInternalNode() && first->m_count > 1)
- {
- a_it.Push(first, 1); // Descend sibling branch later
- }
- else if (first->IsLeaf())
- {
- if (first->m_count)
- {
- a_it.Push(first, 0);
- }
- break;
- }
- first = first->m_branch[0].m_child;
- }
+ a_it.Init();
+ auto first = m_root;
+ while (first)
+ {
+ if (first->IsInternalNode() && first->m_count > 1)
+ {
+ a_it.Push(first, 1); // Descend sibling branch later
+ }
+ else if (first->IsLeaf())
+ {
+ if (first->m_count)
+ {
+ a_it.Push(first, 0);
+ }
+ break;
+ }
+ first = first->m_branch[0].m_child;
+ }
}
/// Get Next for iteration
@@ -283,13 +283,13 @@
/// Get object at iterator position
DataType& GetAt(Iterator& a_it) { return *a_it; }
-protected:
+ protected:
/// Minimal bounding rectangle (n-dimensional)
struct Rect
{
- ElementType m_min[kNumDimensions] = { 0, }; ///<
Min dimensions of bounding box
- ElementType m_max[kNumDimensions] = { 0, }; ///<
Max dimensions of bounding box
+ ElementType m_min[kNumDimensions] = { 0, }; ///<
Min dimensions of bounding box
+ ElementType m_max[kNumDimensions] = { 0, }; ///<
Max dimensions of bounding box
};
/// May be data or may be another subtree
@@ -297,45 +297,45 @@
/// If the parents level is 0, then this is data
struct Branch
{
- Rect m_rect; ///< Bounds
- Node* m_child = nullptr; ///< Child node
- DataType m_data; ///< Data Id
+ Rect m_rect; ///< Bounds
+ Node* m_child = nullptr; ///< Child node
+ DataType m_data; ///< Data Id
};
/// Node for each branch level
struct Node
{
- bool IsInternalNode() const noexcept { return (m_level > 0); } // Not
a leaf, but a internal node
- bool IsLeaf() const noexcept { return (m_level == 0); } // A
leaf, contains data
+ bool IsInternalNode() const noexcept { return (m_level > 0); } // Not a
leaf, but a internal node
+ bool IsLeaf() const noexcept { return (m_level == 0); } // A
leaf, contains data
- int m_count = 0; ///< Count
- int m_level = 0; ///< Leaf is zero,
others positive
- Branch m_branch[_MaxNodeCount]; ///< Branch
+ int m_count = 0; ///< Count
+ int m_level = 0; ///< Leaf is zero, others
positive
+ Branch m_branch[_MaxNodeCount]; ///< Branch
};
/// A link list of nodes for reinsertion after a delete operation
struct ListNode
{
- ListNode* m_next = nullptr; ///< Next in list
- Node* m_node = nullptr; ///< Node
+ ListNode* m_next = nullptr; ///< Next in list
+ Node* m_node = nullptr; ///< Node
};
/// Variables for finding a split partition
struct PartitionVars
{
- constexpr static const int kNotTaken = -1; // indicates that position
+ constexpr static const int kNotTaken = -1; // indicates that position
- int m_partition[_MaxNodeCount + 1] = { 0, };
- int m_total = 0;
- int m_minFill = 0;
- int m_count[2] = { 0, };
- Rect m_cover[2];
- ElementTypeReal m_area[2] = { kElementTypeRealZero, };
+ int m_partition[_MaxNodeCount + 1] = { 0, };
+ int m_total = 0;
+ int m_minFill = 0;
+ int m_count[2] = { 0, };
+ Rect m_cover[2];
+ ElementTypeReal m_area[2] = { kElementTypeRealZero, };
- Branch m_branchBuf[_MaxNodeCount + 1];
- int m_branchCount = 0;
- Rect m_coverSplit;
- ElementTypeReal m_coverSplitArea = kElementTypeRealZero;
+ Branch m_branchBuf[_MaxNodeCount + 1];
+ int m_branchCount = 0;
+ Rect m_coverSplit;
+ ElementTypeReal m_coverSplitArea = kElementTypeRealZero;
};
Node* AllocNode();
@@ -385,7 +385,7 @@
{
FILE* m_file = nullptr;
-public:
+ public:
RTFileStream() = default;
@@ -392,65 +392,65 @@
~RTFileStream()
{
- Close();
+ Close();
}
bool OpenRead(const char* a_fileName)
{
- m_file = fopen(a_fileName, "rb");
- if (!m_file)
- {
- return false;
- }
- return true;
+ m_file = fopen(a_fileName, "rb");
+ if (!m_file)
+ {
+ return false;
+ }
+ return true;
}
bool OpenWrite(const char* a_fileName)
{
- m_file = fopen(a_fileName, "wb");
- if (!m_file)
- {
- return false;
- }
- return true;
+ m_file = fopen(a_fileName, "wb");
+ if (!m_file)
+ {
+ return false;
+ }
+ return true;
}
void Close()
{
- if (m_file)
- {
- fclose(m_file);
- m_file = nullptr;
- }
+ if (m_file)
+ {
+ fclose(m_file);
+ m_file = nullptr;
+ }
}
template< typename TYPE >
- size_t Write(const TYPE& a_value)
- {
- RTreeAssert(m_file);
- return fwrite((void*)&a_value, sizeof(a_value), 1, m_file);
- }
+ size_t Write(const TYPE& a_value)
+ {
+ RTreeAssert(m_file);
+ return fwrite((void*)&a_value, sizeof(a_value), 1, m_file);
+ }
template< typename TYPE >
- size_t WriteArray(const TYPE* a_array, int a_count)
- {
- RTreeAssert(m_file);
- return fwrite((void*)a_array, sizeof(TYPE) * a_count, 1, m_file);
- }
+ size_t WriteArray(const TYPE* a_array, int a_count)
+ {
+ RTreeAssert(m_file);
+ return fwrite((void*)a_array, sizeof(TYPE) * a_count, 1, m_file);
+ }
template< typename TYPE >
- size_t Read(TYPE& a_value)
- {
- RTreeAssert(m_file);
- return fread((void*)&a_value, sizeof(a_value), 1, m_file);
- }
+ size_t Read(TYPE& a_value)
+ {
+ RTreeAssert(m_file);
+ return fread((void*)&a_value, sizeof(a_value), 1, m_file);
+ }
template< typename TYPE >
- size_t ReadArray(TYPE* a_array, int a_count)
- {
- RTreeAssert(m_file);
- return fread((void*)a_array, sizeof(TYPE) * a_count, 1, m_file);
- }
+ size_t ReadArray(TYPE* a_array, int a_count)
+ {
+ RTreeAssert(m_file);
+ return fread((void*)a_array, sizeof(TYPE) * a_count, 1, m_file);
+ }
};
@@ -459,13 +459,13 @@
{
// Precomputed volumes of the unit spheres for the first few dimensions
constexpr const ElementTypeReal kUnitSphereVolumes[] = {
- CastElementTypeReal(0.000000), CastElementTypeReal(2.000000),
CastElementTypeReal(3.141593), // Dimension 0,1,2
- CastElementTypeReal(4.188790), CastElementTypeReal(4.934802),
CastElementTypeReal(5.263789), // Dimension 3,4,5
- CastElementTypeReal(5.167713), CastElementTypeReal(4.724766),
CastElementTypeReal(4.058712), // Dimension 6,7,8
- CastElementTypeReal(3.298509), CastElementTypeReal(2.550164),
CastElementTypeReal(1.884104), // Dimension 9,10,11
- CastElementTypeReal(1.335263), CastElementTypeReal(0.910629),
CastElementTypeReal(0.599265), // Dimension 12,13,14
- CastElementTypeReal(0.381443), CastElementTypeReal(0.235331),
CastElementTypeReal(0.140981), // Dimension 15,16,17
- CastElementTypeReal(0.082146), CastElementTypeReal(0.046622),
CastElementTypeReal(0.025807), // Dimension 18,19,20
+ CastElementTypeReal(0.000000), CastElementTypeReal(2.000000),
CastElementTypeReal(3.141593), // Dimension 0,1,2
+ CastElementTypeReal(4.188790), CastElementTypeReal(4.934802),
CastElementTypeReal(5.263789), // Dimension 3,4,5
+ CastElementTypeReal(5.167713), CastElementTypeReal(4.724766),
CastElementTypeReal(4.058712), // Dimension 6,7,8
+ CastElementTypeReal(3.298509), CastElementTypeReal(2.550164),
CastElementTypeReal(1.884104), // Dimension 9,10,11
+ CastElementTypeReal(1.335263), CastElementTypeReal(0.910629),
CastElementTypeReal(0.599265), // Dimension 12,13,14
+ CastElementTypeReal(0.381443), CastElementTypeReal(0.235331),
CastElementTypeReal(0.140981), // Dimension 15,16,17
+ CastElementTypeReal(0.082146), CastElementTypeReal(0.046622),
CastElementTypeReal(0.025807), // Dimension 18,19,20
};
m_root = AllocNode();
@@ -494,7 +494,7 @@
#ifdef _DEBUG
for (int index = 0; index < kNumDimensions; ++index)
{
- RTreeAssert(a_min[index] <= a_max[index]);
+ RTreeAssert(a_min[index] <= a_max[index]);
}
#endif //_DEBUG
@@ -504,8 +504,8 @@
for (int axis = 0; axis < kNumDimensions; ++axis)
{
- branch.m_rect.m_min[axis] = a_min[axis];
- branch.m_rect.m_max[axis] = a_max[axis];
+ branch.m_rect.m_min[axis] = a_min[axis];
+ branch.m_rect.m_max[axis] = a_max[axis];
}
InsertRect(branch, &m_root, 0);
@@ -518,7 +518,7 @@
#ifdef _DEBUG
for (int index = 0; index < kNumDimensions; ++index)
{
- RTreeAssert(a_min[index] <= a_max[index]);
+ RTreeAssert(a_min[index] <= a_max[index]);
}
#endif //_DEBUG
@@ -526,8 +526,8 @@
for (int axis = 0; axis < kNumDimensions; ++axis)
{
- rect.m_min[axis] = a_min[axis];
- rect.m_max[axis] = a_max[axis];
+ rect.m_min[axis] = a_min[axis];
+ rect.m_max[axis] = a_max[axis];
}
RemoveRect(&rect, a_dataId, &m_root);
@@ -540,7 +540,7 @@
#ifdef _DEBUG
for (int index = 0; index < kNumDimensions; ++index)
{
- RTreeAssert(a_min[index] <= a_max[index]);
+ RTreeAssert(a_min[index] <= a_max[index]);
}
#endif //_DEBUG
@@ -548,8 +548,8 @@
for (int axis = 0; axis < kNumDimensions; ++axis)
{
- rect.m_min[axis] = a_min[axis];
- rect.m_max[axis] = a_max[axis];
+ rect.m_min[axis] = a_min[axis];
+ rect.m_max[axis] = a_max[axis];
}
// NOTE: May want to return search result another way, perhaps returning
the number of found elements here.
@@ -577,14 +577,14 @@
{
if (a_node->IsInternalNode()) // not a leaf node
{
- for (int index = 0; index < a_node->m_count; ++index)
- {
- CountRec(a_node->m_branch[index].m_child, a_count);
- }
+ for (int index = 0; index < a_node->m_count; ++index)
+ {
+ CountRec(a_node->m_branch[index].m_child, a_count);
+ }
}
else // A leaf node
{
- a_count += a_node->m_count;
+ a_count += a_node->m_count;
}
}
@@ -597,7 +597,7 @@
RTFileStream stream;
if (!stream.OpenRead(a_fileName))
{
- return false;
+ return false;
}
bool result = Load(stream);
@@ -641,16 +641,16 @@
// Test if header was valid and compatible
if ((dataFileId == _dataFileId)
- && (dataSize == _dataSize)
- && (dataNumDims == _dataNumDims)
- && (dataElemSize == _dataElemSize)
- && (dataElemRealSize == _dataElemRealSize)
- && (dataMaxNodes == _dataMaxNodes)
- && (dataMinNodes == _dataMinNodes)
- )
+ && (dataSize == _dataSize)
+ && (dataNumDims == _dataNumDims)
+ && (dataElemSize == _dataElemSize)
+ && (dataElemRealSize == _dataElemRealSize)
+ && (dataMaxNodes == _dataMaxNodes)
+ && (dataMinNodes == _dataMinNodes)
+ )
{
- // Recursively load tree
- result = LoadRec(m_root, a_stream);
+ // Recursively load tree
+ result = LoadRec(m_root, a_stream);
}
return result;
@@ -665,28 +665,28 @@
if (a_node->IsInternalNode()) // not a leaf node
{
- for (int index = 0; index < a_node->m_count; ++index)
- {
- Branch* curBranch = &a_node->m_branch[index];
+ for (int index = 0; index < a_node->m_count; ++index)
+ {
+ Branch* curBranch = &a_node->m_branch[index];
- a_stream.ReadArray(curBranch->m_rect.m_min, kNumDimensions);
- a_stream.ReadArray(curBranch->m_rect.m_max, kNumDimensions);
+ a_stream.ReadArray(curBranch->m_rect.m_min, kNumDimensions);
+ a_stream.ReadArray(curBranch->m_rect.m_max, kNumDimensions);
- curBranch->m_child = AllocNode();
- LoadRec(curBranch->m_child, a_stream);
- }
+ curBranch->m_child = AllocNode();
+ LoadRec(curBranch->m_child, a_stream);
+ }
}
else // A leaf node
{
- for (int index = 0; index < a_node->m_count; ++index)
- {
- Branch* curBranch = &a_node->m_branch[index];
+ for (int index = 0; index < a_node->m_count; ++index)
+ {
+ Branch* curBranch = &a_node->m_branch[index];
- a_stream.ReadArray(curBranch->m_rect.m_min, kNumDimensions);
- a_stream.ReadArray(curBranch->m_rect.m_max, kNumDimensions);
+ a_stream.ReadArray(curBranch->m_rect.m_min, kNumDimensions);
+ a_stream.ReadArray(curBranch->m_rect.m_max, kNumDimensions);
- a_stream.Read(curBranch->m_data);
- }
+ a_stream.Read(curBranch->m_data);
+ }
}
return true; // Should do more error checking on I/O operations
@@ -701,40 +701,40 @@
if (current->IsInternalNode()) // not a leaf node
{
- for (int index = 0; index < current->m_count; ++index)
- {
- auto& currentBranch = current->m_branch[index];
- const auto& otherBranch = other->m_branch[index];
+ for (int index = 0; index < current->m_count; ++index)
+ {
+ auto& currentBranch = current->m_branch[index];
+ const auto& otherBranch = other->m_branch[index];
- std::copy(otherBranch.m_rect.m_min,
- otherBranch.m_rect.m_min + kNumDimensions,
- currentBranch.m_rect.m_min);
+ std::copy(otherBranch.m_rect.m_min,
+ otherBranch.m_rect.m_min + kNumDimensions,
+ currentBranch.m_rect.m_min);
- std::copy(otherBranch.m_rect.m_max,
- otherBranch.m_rect.m_max + kNumDimensions,
- currentBranch.m_rect.m_max);
+ std::copy(otherBranch.m_rect.m_max,
+ otherBranch.m_rect.m_max + kNumDimensions,
+ currentBranch.m_rect.m_max);
- currentBranch.m_child = AllocNode();
- CopyRec(currentBranch.m_child, otherBranch.m_child);
- }
+ currentBranch.m_child = AllocNode();
+ CopyRec(currentBranch.m_child, otherBranch.m_child);
+ }
}
else // A leaf node
{
- for (int index = 0; index < current->m_count; ++index)
- {
- auto& currentBranch = current->m_branch[index];
- const auto& otherBranch = other->m_branch[index];
+ for (int index = 0; index < current->m_count; ++index)
+ {
+ auto& currentBranch = current->m_branch[index];
+ const auto& otherBranch = other->m_branch[index];
- std::copy(otherBranch.m_rect.m_min,
- otherBranch.m_rect.m_min + kNumDimensions,
- currentBranch.m_rect.m_min);
+ std::copy(otherBranch.m_rect.m_min,
+ otherBranch.m_rect.m_min + kNumDimensions,
+ currentBranch.m_rect.m_min);
- std::copy(otherBranch.m_rect.m_max,
- otherBranch.m_rect.m_max + kNumDimensions,
- currentBranch.m_rect.m_max);
+ std::copy(otherBranch.m_rect.m_max,
+ otherBranch.m_rect.m_max + kNumDimensions,
+ currentBranch.m_rect.m_max);
- currentBranch.m_data = otherBranch.m_data;
- }
+ currentBranch.m_data = otherBranch.m_data;
+ }
}
}
@@ -745,7 +745,7 @@
RTFileStream stream;
if (!stream.OpenWrite(a_fileName))
{
- return false;
+ return false;
}
bool result = Save(stream);
@@ -791,27 +791,27 @@
if (a_node->IsInternalNode()) // not a leaf node
{
- for (int index = 0; index < a_node->m_count; ++index)
- {
- const auto& curBranch = &a_node->m_branch[index];
+ for (int index = 0; index < a_node->m_count; ++index)
+ {
+ const auto& curBranch = &a_node->m_branch[index];
- a_stream.WriteArray(curBranch->m_rect.m_min, kNumDimensions);
- a_stream.WriteArray(curBranch->m_rect.m_max, kNumDimensions);
+ a_stream.WriteArray(curBranch->m_rect.m_min, kNumDimensions);
+ a_stream.WriteArray(curBranch->m_rect.m_max, kNumDimensions);
- SaveRec(curBranch->m_child, a_stream);
- }
+ SaveRec(curBranch->m_child, a_stream);
+ }
}
else // A leaf node
{
- for (int index = 0; index < a_node->m_count; ++index)
- {
- const auto& curBranch = &a_node->m_branch[index];
+ for (int index = 0; index < a_node->m_count; ++index)
+ {
+ const auto& curBranch = &a_node->m_branch[index];
- a_stream.WriteArray(curBranch->m_rect.m_min, kNumDimensions);
- a_stream.WriteArray(curBranch->m_rect.m_max, kNumDimensions);
+ a_stream.WriteArray(curBranch->m_rect.m_min, kNumDimensions);
+ a_stream.WriteArray(curBranch->m_rect.m_max, kNumDimensions);
- a_stream.Write(curBranch->m_data);
- }
+ a_stream.Write(curBranch->m_data);
+ }
}
return true; // Should do more error checking on I/O operations
@@ -850,10 +850,10 @@
if (a_node->IsInternalNode()) // This is an internal node in the tree
{
- for (int index = 0; index < a_node->m_count; ++index)
- {
- RemoveAllRec(a_node->m_branch[index].m_child);
- }
+ for (int index = 0; index < a_node->m_count; ++index)
+ {
+ RemoveAllRec(a_node->m_branch[index].m_child);
+ }
}
FreeNode(a_node);
}
@@ -923,8 +923,8 @@
{
for (int index = 0; index < kNumDimensions; ++index)
{
- a_rect->m_min[index] = CastElementType(0);
- a_rect->m_max[index] = CastElementType(0);
+ a_rect->m_min[index] = CastElementType(0);
+ a_rect->m_max[index] = CastElementType(0);
}
}
@@ -946,46 +946,46 @@
// will always be called with a_level == 0 (leaf)
if (a_node->m_level > a_level)
{
- // Still above level for insertion, go down tree recursively
- Node* otherNode;
+ // Still above level for insertion, go down tree recursively
+ Node* otherNode;
- // find the optimal branch for this record
- int index = PickBranch(&a_branch.m_rect, a_node);
+ // find the optimal branch for this record
+ int index = PickBranch(&a_branch.m_rect, a_node);
- // recursively insert this record into the picked branch
- bool childWasSplit = InsertRectRec(a_branch,
a_node->m_branch[index].m_child, &otherNode, a_level);
+ // recursively insert this record into the picked branch
+ bool childWasSplit = InsertRectRec(a_branch,
a_node->m_branch[index].m_child, &otherNode, a_level);
- if (!childWasSplit)
- {
- // Child was not split. Merge the bounding box of the new record
with the
- // existing bounding box
- a_node->m_branch[index].m_rect = CombineRect(&a_branch.m_rect,
&(a_node->m_branch[index].m_rect));
- return false;
- }
- else
- {
- // Child was split. The old branches are now re-partitioned to two
nodes
- // so we have to re-calculate the bounding boxes of each node
- a_node->m_branch[index].m_rect =
NodeCover(a_node->m_branch[index].m_child);
- Branch branch;
- branch.m_child = otherNode;
- branch.m_rect = NodeCover(otherNode);
+ if (!childWasSplit)
+ {
+ // Child was not split. Merge the bounding box of the new record
with the
+ // existing bounding box
+ a_node->m_branch[index].m_rect = CombineRect(&a_branch.m_rect,
&(a_node->m_branch[index].m_rect));
+ return false;
+ }
+ else
+ {
+ // Child was split. The old branches are now re-partitioned to two
nodes
+ // so we have to re-calculate the bounding boxes of each node
+ a_node->m_branch[index].m_rect =
NodeCover(a_node->m_branch[index].m_child);
+ Branch branch;
+ branch.m_child = otherNode;
+ branch.m_rect = NodeCover(otherNode);
- // The old node is already a child of a_node. Now add the
newly-created
- // node to a_node as well. a_node might be split because of that.
- return AddBranch(&branch, a_node, a_newNode);
- }
+ // The old node is already a child of a_node. Now add the
newly-created
+ // node to a_node as well. a_node might be split because of that.
+ return AddBranch(&branch, a_node, a_newNode);
+ }
}
else if (a_node->m_level == a_level)
{
- // We have reached level for insertion. Add rect, split if necessary
- return AddBranch(&a_branch, a_node, a_newNode);
+ // We have reached level for insertion. Add rect, split if necessary
+ return AddBranch(&a_branch, a_node, a_newNode);
}
else
{
- // Should never occur
- RTreeAssert(0);
- return false;
+ // Should never occur
+ RTreeAssert(0);
+ return false;
}
}
@@ -1005,7 +1005,7 @@
#ifdef _DEBUG
for (int index = 0; index < kNumDimensions; ++index)
{
- RTreeAssert(a_branch.m_rect.m_min[index] <=
a_branch.m_rect.m_max[index]);
+ RTreeAssert(a_branch.m_rect.m_min[index] <=
a_branch.m_rect.m_max[index]);
}
#endif //_DEBUG
@@ -1013,26 +1013,26 @@
if (InsertRectRec(a_branch, *a_root, &newNode, a_level)) // Root split
{
- // Grow tree taller and new root
- Node* newRoot = AllocNode();
- newRoot->m_level = (*a_root)->m_level + 1;
+ // Grow tree taller and new root
+ Node* newRoot = AllocNode();
+ newRoot->m_level = (*a_root)->m_level + 1;
- Branch branch;
+ Branch branch;
- // add old root node as a child of the new root
- branch.m_rect = NodeCover(*a_root);
- branch.m_child = *a_root;
- AddBranch(&branch, newRoot, nullptr);
+ // add old root node as a child of the new root
+ branch.m_rect = NodeCover(*a_root);
+ branch.m_child = *a_root;
+ AddBranch(&branch, newRoot, nullptr);
- // add the split node as a child of the new root
- branch.m_rect = NodeCover(newNode);
- branch.m_child = newNode;
- AddBranch(&branch, newRoot, nullptr);
+ // add the split node as a child of the new root
+ branch.m_rect = NodeCover(newNode);
+ branch.m_child = newNode;
+ AddBranch(&branch, newRoot, nullptr);
- // set the new root as the root node
- *a_root = newRoot;
+ // set the new root as the root node
+ *a_root = newRoot;
- return true;
+ return true;
}
return false;
@@ -1048,7 +1048,7 @@
Rect rect = a_node->m_branch[0].m_rect;
for (int index = 1; index < a_node->m_count; ++index)
{
- rect = CombineRect(&rect, &(a_node->m_branch[index].m_rect));
+ rect = CombineRect(&rect, &(a_node->m_branch[index].m_rect));
}
return rect;
@@ -1067,17 +1067,17 @@
if (a_node->m_count < _MaxNodeCount) // Split won't be necessary
{
- a_node->m_branch[a_node->m_count] = *a_branch;
- ++a_node->m_count;
+ a_node->m_branch[a_node->m_count] = *a_branch;
+ ++a_node->m_count;
- return false;
+ return false;
}
else
{
- RTreeAssert(a_newNode);
+ RTreeAssert(a_newNode);
- SplitNode(a_node, a_branch, a_newNode);
- return true;
+ SplitNode(a_node, a_branch, a_newNode);
+ return true;
}
}
@@ -1117,23 +1117,23 @@
for (int index = 0; index < a_node->m_count; ++index)
{
- Rect* curRect = &a_node->m_branch[index].m_rect;
- area = CalcRectVolume(curRect);
- tempRect = CombineRect(a_rect, curRect);
- increase = CalcRectVolume(&tempRect) - area;
- if ((increase < bestIncr) || firstTime)
- {
- best = index;
- bestArea = area;
- bestIncr = increase;
- firstTime = false;
- }
- else if (NEAR_EQUAL(increase, bestIncr, ON_ZERO_TOLERANCE) && (area <
bestArea))
- {
- best = index;
- bestArea = area;
- bestIncr = increase;
- }
+ Rect* curRect = &a_node->m_branch[index].m_rect;
+ area = CalcRectVolume(curRect);
+ tempRect = CombineRect(a_rect, curRect);
+ increase = CalcRectVolume(&tempRect) - area;
+ if ((increase < bestIncr) || firstTime)
+ {
+ best = index;
+ bestArea = area;
+ bestIncr = increase;
+ firstTime = false;
+ }
+ else if (NEAR_EQUAL(increase, bestIncr, ON_ZERO_TOLERANCE) && (area <
bestArea))
+ {
+ best = index;
+ bestArea = area;
+ bestIncr = increase;
+ }
}
return best;
}
@@ -1149,8 +1149,8 @@
for (int index = 0; index < kNumDimensions; ++index)
{
- newRect.m_min[index] = (std::min)(a_rectA->m_min[index],
a_rectB->m_min[index]);
- newRect.m_max[index] = (std::max)(a_rectA->m_max[index],
a_rectB->m_max[index]);
+ newRect.m_min[index] = (std::min)(a_rectA->m_min[index],
a_rectB->m_min[index]);
+ newRect.m_max[index] = (std::max)(a_rectA->m_max[index],
a_rectB->m_max[index]);
}
return newRect;
@@ -1200,7 +1200,7 @@
for (int index = 0; index < kNumDimensions; ++index)
{
- volume *= a_rect->m_max[index] - a_rect->m_min[index];
+ volume *= a_rect->m_max[index] - a_rect->m_min[index];
}
RTreeAssert(volume >= kElementTypeRealZero);
@@ -1219,8 +1219,8 @@
for (int index = 0; index < kNumDimensions; ++index)
{
- const auto halfExtent = ((ElementTypeReal)a_rect->m_max[index] -
(ElementTypeReal)a_rect->m_min[index]) * 0.5f;
- sumOfSquares += halfExtent * halfExtent;
+ const auto halfExtent = ((ElementTypeReal)a_rect->m_max[index] -
(ElementTypeReal)a_rect->m_min[index]) * 0.5f;
+ sumOfSquares += halfExtent * halfExtent;
}
const auto radius = CastElementTypeReal(sqrt(sumOfSquares));
@@ -1228,15 +1228,15 @@
// Pow maybe slow, so test for common dims like 2,3 and just use x*x,
x*x*x.
if (kNumDimensions == 3)
{
- return (radius * radius * radius * m_unitSphereVolume);
+ return (radius * radius * radius * m_unitSphereVolume);
}
else if (kNumDimensions == 2)
{
- return (radius * radius * m_unitSphereVolume);
+ return (radius * radius * m_unitSphereVolume);
}
else
{
- return CastElementTypeReal(pow(radius, kNumDimensions) *
m_unitSphereVolume);
+ return CastElementTypeReal(pow(radius, kNumDimensions) *
m_unitSphereVolume);
}
}
@@ -1265,7 +1265,7 @@
// Load the branch buffer
for (int index = 0; index < _MaxNodeCount; ++index)
{
- a_parVars->m_branchBuf[index] = a_node->m_branch[index];
+ a_parVars->m_branchBuf[index] = a_node->m_branch[index];
}
a_parVars->m_branchBuf[_MaxNodeCount] = *a_branch;
a_parVars->m_branchCount = _MaxNodeCount + 1;
@@ -1274,7 +1274,7 @@
a_parVars->m_coverSplit = a_parVars->m_branchBuf[0].m_rect;
for (int index = 1; index < _MaxNodeCount + 1; ++index)
{
- a_parVars->m_coverSplit = CombineRect(&a_parVars->m_coverSplit,
&a_parVars->m_branchBuf[index].m_rect);
+ a_parVars->m_coverSplit = CombineRect(&a_parVars->m_coverSplit,
&a_parVars->m_branchBuf[index].m_rect);
}
a_parVars->m_coverSplitArea = CalcRectVolume(&a_parVars->m_coverSplit);
}
@@ -1303,69 +1303,69 @@
PickSeeds(a_parVars);
while (((a_parVars->m_count[0] + a_parVars->m_count[1]) <
a_parVars->m_total)
- && (a_parVars->m_count[0] < (a_parVars->m_total -
a_parVars->m_minFill))
- && (a_parVars->m_count[1] < (a_parVars->m_total -
a_parVars->m_minFill)))
+ && (a_parVars->m_count[0] < (a_parVars->m_total -
a_parVars->m_minFill))
+ && (a_parVars->m_count[1] < (a_parVars->m_total -
a_parVars->m_minFill)))
{
- biggestDiff = CastElementTypeReal(-1);
- for (int index = 0; index < a_parVars->m_total; ++index)
- {
- if (PartitionVars::kNotTaken == a_parVars->m_partition[index])
- {
- Rect* curRect = &a_parVars->m_branchBuf[index].m_rect;
- Rect rect0 = CombineRect(curRect, &a_parVars->m_cover[0]);
- Rect rect1 = CombineRect(curRect, &a_parVars->m_cover[1]);
- ElementTypeReal growth0 = CalcRectVolume(&rect0) -
a_parVars->m_area[0];
- ElementTypeReal growth1 = CalcRectVolume(&rect1) -
a_parVars->m_area[1];
- ElementTypeReal diff = growth1 - growth0;
- if (diff >= 0)
- {
- group = 0;
- }
- else
- {
- group = 1;
- diff = -diff;
- }
+ biggestDiff = CastElementTypeReal(-1);
+ for (int index = 0; index < a_parVars->m_total; ++index)
+ {
+ if (PartitionVars::kNotTaken == a_parVars->m_partition[index])
+ {
+ Rect* curRect = &a_parVars->m_branchBuf[index].m_rect;
+ Rect rect0 = CombineRect(curRect, &a_parVars->m_cover[0]);
+ Rect rect1 = CombineRect(curRect, &a_parVars->m_cover[1]);
+ ElementTypeReal growth0 = CalcRectVolume(&rect0) -
a_parVars->m_area[0];
+ ElementTypeReal growth1 = CalcRectVolume(&rect1) -
a_parVars->m_area[1];
+ ElementTypeReal diff = growth1 - growth0;
+ if (diff >= 0)
+ {
+ group = 0;
+ }
+ else
+ {
+ group = 1;
+ diff = -diff;
+ }
- if (diff > biggestDiff)
- {
- biggestDiff = diff;
- chosen = index;
- betterGroup = group;
- }
- else if (NEAR_EQUAL(diff, biggestDiff, ON_ZERO_TOLERANCE) &&
(a_parVars->m_count[group] < a_parVars->m_count[betterGroup]))
- {
- chosen = index;
- betterGroup = group;
- }
- }
- }
- Classify(chosen, betterGroup, a_parVars);
+ if (diff > biggestDiff)
+ {
+ biggestDiff = diff;
+ chosen = index;
+ betterGroup = group;
+ }
+ else if (NEAR_EQUAL(diff, biggestDiff, ON_ZERO_TOLERANCE) &&
(a_parVars->m_count[group] < a_parVars->m_count[betterGroup]))
+ {
+ chosen = index;
+ betterGroup = group;
+ }
+ }
+ }
+ Classify(chosen, betterGroup, a_parVars);
}
// If one group too full, put remaining rects in the other
if ((a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total)
{
- if (a_parVars->m_count[0] >= a_parVars->m_total - a_parVars->m_minFill)
- {
- group = 1;
- }
- else
- {
- group = 0;
- }
- for (int index = 0; index < a_parVars->m_total; ++index)
- {
- if (PartitionVars::kNotTaken == a_parVars->m_partition[index])
- {
- Classify(index, group, a_parVars);
- }
- }
+ if (a_parVars->m_count[0] >= a_parVars->m_total - a_parVars->m_minFill)
+ {
+ group = 1;
+ }
+ else
+ {
+ group = 0;
+ }
+ for (int index = 0; index < a_parVars->m_total; ++index)
+ {
+ if (PartitionVars::kNotTaken == a_parVars->m_partition[index])
+ {
+ Classify(index, group, a_parVars);
+ }
+ }
}
RTreeAssert((a_parVars->m_count[0] + a_parVars->m_count[1]) ==
a_parVars->m_total);
RTreeAssert((a_parVars->m_count[0] >= a_parVars->m_minFill) &&
- (a_parVars->m_count[1] >= a_parVars->m_minFill));
+ (a_parVars->m_count[1] >= a_parVars->m_minFill));
}
@@ -1379,13 +1379,13 @@
for (int index = 0; index < a_parVars->m_total; ++index)
{
- RTreeAssert(a_parVars->m_partition[index] == 0 ||
a_parVars->m_partition[index] == 1);
+ RTreeAssert(a_parVars->m_partition[index] == 0 ||
a_parVars->m_partition[index] == 1);
- int targetNodeIndex = a_parVars->m_partition[index];
- Node* targetNodes[] = { a_nodeA, a_nodeB };
+ int targetNodeIndex = a_parVars->m_partition[index];
+ Node* targetNodes[] = { a_nodeA, a_nodeB };
- // It is assured that AddBranch here will not cause a node split.
- AddBranch(&a_parVars->m_branchBuf[index],
targetNodes[targetNodeIndex], nullptr);
+ // It is assured that AddBranch here will not cause a node split.
+ AddBranch(&a_parVars->m_branchBuf[index], targetNodes[targetNodeIndex],
nullptr);
}
}
@@ -1402,7 +1402,7 @@
a_parVars->m_minFill = a_minFill;
for (int index = 0; index < a_maxRects; ++index)
{
- a_parVars->m_partition[index] = PartitionVars::kNotTaken;
+ a_parVars->m_partition[index] = PartitionVars::kNotTaken;
}
}
@@ -1416,23 +1416,23 @@
for (int index = 0; index < a_parVars->m_total; ++index)
{
- area[index] = CalcRectVolume(&a_parVars->m_branchBuf[index].m_rect);
+ area[index] = CalcRectVolume(&a_parVars->m_branchBuf[index].m_rect);
}
worst = -a_parVars->m_coverSplitArea - 1;
for (int indexA = 0; indexA < a_parVars->m_total - 1; ++indexA)
{
- for (int indexB = indexA + 1; indexB < a_parVars->m_total; ++indexB)
- {
- auto oneRect = CombineRect(&a_parVars->m_branchBuf[indexA].m_rect,
&a_parVars->m_branchBuf[indexB].m_rect);
- waste = CalcRectVolume(&oneRect) - area[indexA] - area[indexB];
- if (waste > worst)
- {
- worst = waste;
- seed0 = indexA;
- seed1 = indexB;
- }
- }
+ for (int indexB = indexA + 1; indexB < a_parVars->m_total; ++indexB)
+ {
+ auto oneRect = CombineRect(&a_parVars->m_branchBuf[indexA].m_rect,
&a_parVars->m_branchBuf[indexB].m_rect);
+ waste = CalcRectVolume(&oneRect) - area[indexA] - area[indexB];
+ if (waste > worst)
+ {
+ worst = waste;
+ seed0 = indexA;
+ seed1 = indexB;
+ }
+ }
}
Classify(seed0, 0, a_parVars);
@@ -1452,11 +1452,11 @@
// Calculate combined rect
if (a_parVars->m_count[a_group] == 0)
{
- a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect;
+ a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect;
}
else
{
- a_parVars->m_cover[a_group] =
CombineRect(&a_parVars->m_branchBuf[a_index].m_rect,
&a_parVars->m_cover[a_group]);
+ a_parVars->m_cover[a_group] =
CombineRect(&a_parVars->m_branchBuf[a_index].m_rect,
&a_parVars->m_cover[a_group]);
}
// Calculate volume of combined rect
@@ -1480,41 +1480,41 @@
if (!RemoveRectRec(a_rect, a_id, *a_root, &reInsertList))
{
- // Found and deleted a data item
- // Reinsert any branches from eliminated nodes
- while (reInsertList)
- {
- Node* tempNode = reInsertList->m_node;
+ // Found and deleted a data item
+ // Reinsert any branches from eliminated nodes
+ while (reInsertList)
+ {
+ Node* tempNode = reInsertList->m_node;
- for (int index = 0; index < tempNode->m_count; ++index)
- {
- InsertRect(tempNode->m_branch[index],
- a_root,
- tempNode->m_level);
- }
+ for (int index = 0; index < tempNode->m_count; ++index)
+ {
+ InsertRect(tempNode->m_branch[index],
+ a_root,
+ tempNode->m_level);
+ }
- ListNode* remLNode = reInsertList;
- reInsertList = reInsertList->m_next;
+ ListNode* remLNode = reInsertList;
+ reInsertList = reInsertList->m_next;
- FreeNode(remLNode->m_node);
- FreeListNode(remLNode);
- }
+ FreeNode(remLNode->m_node);
+ FreeListNode(remLNode);
+ }
- // Check for redundant root (not leaf, 1 child) and eliminate TODO
replace
- // if with while? In case there is a whole branch of redundant roots...
- if ((*a_root)->m_count == 1 && (*a_root)->IsInternalNode())
- {
- auto tempNode = (*a_root)->m_branch[0].m_child;
+ // Check for redundant root (not leaf, 1 child) and eliminate TODO
replace
+ // if with while? In case there is a whole branch of redundant roots...
+ if ((*a_root)->m_count == 1 && (*a_root)->IsInternalNode())
+ {
+ auto tempNode = (*a_root)->m_branch[0].m_child;
- RTreeAssert(tempNode);
- FreeNode(*a_root);
- *a_root = tempNode;
- }
- return false;
+ RTreeAssert(tempNode);
+ FreeNode(*a_root);
+ *a_root = tempNode;
+ }
+ return false;
}
else
{
- return true;
+ return true;
}
}
@@ -1531,40 +1531,40 @@
if (a_node->IsInternalNode()) // not a leaf node
{
- for (int index = 0; index < a_node->m_count; ++index)
- {
- if (Overlap(a_rect, &(a_node->m_branch[index].m_rect)))
- {
- if (!RemoveRectRec(a_rect, a_id,
a_node->m_branch[index].m_child, a_listNode))
- {
- if (a_node->m_branch[index].m_child->m_count >=
_MinNodeCount)
- {
- // child removed, just resize parent rect
- a_node->m_branch[index].m_rect =
NodeCover(a_node->m_branch[index].m_child);
- }
- else
- {
- // child removed, not enough entries in node,
eliminate node
- ReInsert(a_node->m_branch[index].m_child, a_listNode);
- DisconnectBranch(a_node, index); // Must return after
this call as count has changed
- }
- return false;
- }
- }
- }
- return true;
+ for (int index = 0; index < a_node->m_count; ++index)
+ {
+ if (Overlap(a_rect, &(a_node->m_branch[index].m_rect)))
+ {
+ if (!RemoveRectRec(a_rect, a_id,
a_node->m_branch[index].m_child, a_listNode))
+ {
+ if (a_node->m_branch[index].m_child->m_count >=
_MinNodeCount)
+ {
+ // child removed, just resize parent rect
+ a_node->m_branch[index].m_rect =
NodeCover(a_node->m_branch[index].m_child);
+ }
+ else
+ {
+ // child removed, not enough entries in node, eliminate
node
+ ReInsert(a_node->m_branch[index].m_child, a_listNode);
+ DisconnectBranch(a_node, index); // Must return after
this call as count has changed
+ }
+ return false;
+ }
+ }
+ }
+ return true;
}
else // A leaf node
{
- for (int index = 0; index < a_node->m_count; ++index)
- {
- if (a_node->m_branch[index].m_data == a_id)
- {
- DisconnectBranch(a_node, index); // Must return after this
call as count has changed
- return false;
- }
- }
- return true;
+ for (int index = 0; index < a_node->m_count; ++index)
+ {
+ if (a_node->m_branch[index].m_data == a_id)
+ {
+ DisconnectBranch(a_node, index); // Must return after this call
as count has changed
+ return false;
+ }
+ }
+ return true;
}
}
@@ -1577,11 +1577,11 @@
for (int index = 0; index < kNumDimensions; ++index)
{
- if (a_rectA->m_min[index] > a_rectB->m_max[index] ||
- a_rectB->m_min[index] > a_rectA->m_max[index])
- {
- return false;
- }
+ if (a_rectA->m_min[index] > a_rectB->m_max[index] ||
+ a_rectB->m_min[index] > a_rectA->m_max[index])
+ {
+ return false;
+ }
}
return true;
}
@@ -1611,35 +1611,35 @@
if (a_node->IsInternalNode())
{
- // This is an internal node in the tree
- for (int index = 0; index < a_node->m_count; ++index)
- {
- if (Overlap(a_rect, &a_node->m_branch[index].m_rect))
- {
- if (!Search(a_node->m_branch[index].m_child, a_rect,
a_foundCount, callback, a_context))
- {
- // The callback indicated to stop searching
- return false;
- }
- }
- }
+ // This is an internal node in the tree
+ for (int index = 0; index < a_node->m_count; ++index)
+ {
+ if (Overlap(a_rect, &a_node->m_branch[index].m_rect))
+ {
+ if (!Search(a_node->m_branch[index].m_child, a_rect,
a_foundCount, callback, a_context))
+ {
+ // The callback indicated to stop searching
+ return false;
+ }
+ }
+ }
}
else
{
- // This is a leaf node
- for (int index = 0; index < a_node->m_count; ++index)
- {
- if (Overlap(a_rect, &a_node->m_branch[index].m_rect))
- {
- const auto& id = a_node->m_branch[index].m_data;
- ++a_foundCount;
+ // This is a leaf node
+ for (int index = 0; index < a_node->m_count; ++index)
+ {
+ if (Overlap(a_rect, &a_node->m_branch[index].m_rect))
+ {
+ const auto& id = a_node->m_branch[index].m_data;
+ ++a_foundCount;
- if (callback && !callback(id, a_context))
- {
- return false; // Don't continue searching
- }
- }
- }
+ if (callback && !callback(id, a_context))
+ {
+ return false; // Don't continue searching
+ }
+ }
+ }
}
return true; // Continue searching
@@ -1661,3 +1661,12 @@
#endif //RTREE_H
+
+// Local Variables:
+// tab-width: 8
+// mode: C++
+// c-basic-offset: 4
+// indent-tabs-mode: t
+// c-file-style: "stroustrup"
+// End:
+// ex: shiftwidth=4 tabstop=8
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
_______________________________________________
BRL-CAD Source Commits mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-commits
