Revision: 74288
http://sourceforge.net/p/brlcad/code/74288
Author: starseeker
Date: 2019-11-04 20:39:02 +0000 (Mon, 04 Nov 2019)
Log Message:
-----------
hit RTree.h with astyle
Modified Paths:
--------------
brlcad/trunk/src/libbrep/RTree.h
Modified: brlcad/trunk/src/libbrep/RTree.h
===================================================================
--- brlcad/trunk/src/libbrep/RTree.h 2019-11-04 15:52:28 UTC (rev 74287)
+++ brlcad/trunk/src/libbrep/RTree.h 2019-11-04 20:39:02 UTC (rev 74288)
@@ -46,19 +46,19 @@
/// This is the version from https://github.com/DevHwan/RTree, with some minor
tweaks for building with BRL-CAD
/// Also, Search was modified to restore the passing of a context pointer that
allows the callback to
/// record information for later use.
-template<class _DataType, class _ElementType, int _NumDimensions,
- class _ElementTypeReal = _ElementType, int _MaxNodeCount = 8, int
_MinNodeCount = _MaxNodeCount / 2>
- class RTree
+template<class _DataType, class _ElementType, int _NumDimensions,
+ class _ElementTypeReal = _ElementType, int _MaxNodeCount = 8, int
_MinNodeCount = _MaxNodeCount / 2>
+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;
@@ -69,13 +69,15 @@
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);
@@ -136,130 +138,135 @@
/// 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
+ 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;
}
- 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);
+ // 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
@@ -267,16 +274,11 @@
{
a_it.Init();
auto first = m_root;
- while (first)
- {
- if (first->IsInternalNode() && first->m_count > 1)
- {
+ 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)
- {
+ } else if (first->IsLeaf()) {
+ if (first->m_count) {
a_it.Push(first, 0);
}
break;
@@ -286,28 +288,35 @@
}
/// Get Next for iteration
- void GetNext(Iterator& a_it) const { ++a_it; }
+ void GetNext(Iterator& a_it) const
+ {
+ ++a_it;
+ }
/// Is iterator NULL, or at end?
- bool IsNull(const Iterator& a_it) const { return a_it.IsNull(); }
+ bool IsNull(const Iterator& a_it) const
+ {
+ return a_it.IsNull();
+ }
/// Get object at iterator position
- DataType& GetAt(Iterator& a_it) { return *a_it; }
+ 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
+ struct Rect {
+ 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
/// The parents level determines this.
/// If the parents level is 0, then this is data
- struct Branch
- {
+ struct Branch {
Rect m_rect; ///< Bounds
Node* m_child = nullptr; ///< Child node
DataType m_data; ///< Data Id
@@ -314,10 +323,15 @@
};
/// 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
+ 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
+ }
int m_count = 0; ///< Count
int m_level = 0; ///< Leaf is zero, others
positive
@@ -325,15 +339,13 @@
};
/// A link list of nodes for reinsertion after a delete operation
- struct ListNode
- {
+ struct ListNode {
ListNode* m_next = nullptr; ///< Next in list
Node* m_node = nullptr; ///< Node
};
/// Variables for finding a split partition
- struct PartitionVars
- {
+ struct PartitionVars {
constexpr static const int kNotTaken = -1; // indicates that position
int m_partition[_MaxNodeCount + 1] = { 0, };
@@ -399,7 +411,7 @@
{
FILE* m_file = nullptr;
- public:
+public:
RTFileStream() = default;
@@ -412,8 +424,7 @@
bool OpenRead(const char* a_fileName)
{
m_file = fopen(a_fileName, "rb");
- if (!m_file)
- {
+ if (!m_file) {
return false;
}
return true;
@@ -422,8 +433,7 @@
bool OpenWrite(const char* a_fileName)
{
m_file = fopen(a_fileName, "wb");
- if (!m_file)
- {
+ if (!m_file) {
return false;
}
return true;
@@ -431,8 +441,7 @@
void Close()
{
- if (m_file)
- {
+ if (m_file) {
fclose(m_file);
m_file = nullptr;
}
@@ -439,32 +448,32 @@
}
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);
+ }
};
@@ -479,7 +488,7 @@
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.082146), CastElementTypeReal(0.046622),
CastElementTypeReal(0.025807), // Dimension 18,19,20
};
m_root = AllocNode();
@@ -506,8 +515,7 @@
void RTREE_QUAL::Insert(const Element& a_min, const Element& a_max, const
DataType& a_dataId)
{
#ifdef _DEBUG
- for (int index = 0; index < kNumDimensions; ++index)
- {
+ for (int index = 0; index < kNumDimensions; ++index) {
RTreeAssert(a_min[index] <= a_max[index]);
}
#endif //_DEBUG
@@ -516,8 +524,7 @@
branch.m_data = a_dataId;
branch.m_child = nullptr;
- for (int axis = 0; axis < kNumDimensions; ++axis)
- {
+ 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];
}
@@ -530,8 +537,7 @@
void RTREE_QUAL::Remove(const Element& a_min, const Element& a_max, const
DataType& a_dataId)
{
#ifdef _DEBUG
- for (int index = 0; index < kNumDimensions; ++index)
- {
+ for (int index = 0; index < kNumDimensions; ++index) {
RTreeAssert(a_min[index] <= a_max[index]);
}
#endif //_DEBUG
@@ -538,8 +544,7 @@
Rect rect;
- for (int axis = 0; axis < kNumDimensions; ++axis)
- {
+ for (int axis = 0; axis < kNumDimensions; ++axis) {
rect.m_min[axis] = a_min[axis];
rect.m_max[axis] = a_max[axis];
}
@@ -552,8 +557,7 @@
int RTREE_QUAL::Search(const Element& a_min, const Element& a_max,
std::function<bool(const DataType&, void *)> callback, void *a_context) const
{
#ifdef _DEBUG
- for (int index = 0; index < kNumDimensions; ++index)
- {
+ for (int index = 0; index < kNumDimensions; ++index) {
RTreeAssert(a_min[index] <= a_max[index]);
}
#endif //_DEBUG
@@ -560,8 +564,7 @@
Rect rect;
- for (int axis = 0; axis < kNumDimensions; ++axis)
- {
+ for (int axis = 0; axis < kNumDimensions; ++axis) {
rect.m_min[axis] = a_min[axis];
rect.m_max[axis] = a_max[axis];
}
@@ -589,15 +592,11 @@
RTREE_TEMPLATE
void RTREE_QUAL::CountRec(Node* a_node, int& a_count) const
{
- if (a_node->IsInternalNode()) // not a leaf node
- {
- for (int index = 0; index < a_node->m_count; ++index)
- {
+ 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);
}
- }
- else // A leaf node
- {
+ } else { // A leaf node
a_count += a_node->m_count;
}
}
@@ -609,8 +608,7 @@
RemoveAll(); // Clear existing tree
RTFileStream stream;
- if (!stream.OpenRead(a_fileName))
- {
+ if (!stream.OpenRead(a_fileName)) {
return false;
}
@@ -655,14 +653,13 @@
// 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);
}
@@ -677,10 +674,8 @@
a_stream.Read(a_node->m_level);
a_stream.Read(a_node->m_count);
- if (a_node->IsInternalNode()) // not a leaf node
- {
- for (int index = 0; index < a_node->m_count; ++index)
- {
+ 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];
a_stream.ReadArray(curBranch->m_rect.m_min, kNumDimensions);
@@ -689,11 +684,8 @@
curBranch->m_child = AllocNode();
LoadRec(curBranch->m_child, a_stream);
}
- }
- else // A leaf node
- {
- for (int index = 0; index < a_node->m_count; ++index)
- {
+ } else { // A leaf node
+ 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);
@@ -713,39 +705,34 @@
current->m_level = other->m_level;
current->m_count = other->m_count;
- if (current->IsInternalNode()) // not a leaf node
- {
- for (int index = 0; index < current->m_count; ++index)
- {
+ 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];
std::copy(otherBranch.m_rect.m_min,
- otherBranch.m_rect.m_min + kNumDimensions,
- currentBranch.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);
+ otherBranch.m_rect.m_max + kNumDimensions,
+ currentBranch.m_rect.m_max);
currentBranch.m_child = AllocNode();
CopyRec(currentBranch.m_child, otherBranch.m_child);
}
- }
- else // A leaf node
- {
- for (int index = 0; index < current->m_count; ++index)
- {
+ } 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];
std::copy(otherBranch.m_rect.m_min,
- otherBranch.m_rect.m_min + kNumDimensions,
- currentBranch.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);
+ otherBranch.m_rect.m_max + kNumDimensions,
+ currentBranch.m_rect.m_max);
currentBranch.m_data = otherBranch.m_data;
}
@@ -757,8 +744,7 @@
bool RTREE_QUAL::Save(const char* a_fileName)
{
RTFileStream stream;
- if (!stream.OpenWrite(a_fileName))
- {
+ if (!stream.OpenWrite(a_fileName)) {
return false;
}
@@ -803,10 +789,8 @@
a_stream.Write(a_node->m_level);
a_stream.Write(a_node->m_count);
- if (a_node->IsInternalNode()) // not a leaf node
- {
- for (int index = 0; index < a_node->m_count; ++index)
- {
+ 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];
a_stream.WriteArray(curBranch->m_rect.m_min, kNumDimensions);
@@ -814,11 +798,8 @@
SaveRec(curBranch->m_child, a_stream);
}
- }
- else // A leaf node
- {
- for (int index = 0; index < a_node->m_count; ++index)
- {
+ } else { // A leaf node
+ 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);
@@ -862,10 +843,8 @@
RTreeAssert(a_node);
RTreeAssert(a_node->m_level >= 0);
- if (a_node->IsInternalNode()) // This is an internal node in the tree
- {
- for (int index = 0; index < a_node->m_count; ++index)
- {
+ 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);
}
}
@@ -935,8 +914,7 @@
RTREE_TEMPLATE
void RTREE_QUAL::InitRect(Rect* a_rect)
{
- for (int index = 0; index < kNumDimensions; ++index)
- {
+ for (int index = 0; index < kNumDimensions; ++index) {
a_rect->m_min[index] = CastElementType(0);
a_rect->m_max[index] = CastElementType(0);
}
@@ -958,8 +936,7 @@
// recurse until we reach the correct level for the new record. data
records
// will always be called with a_level == 0 (leaf)
- if (a_node->m_level > a_level)
- {
+ if (a_node->m_level > a_level) {
// Still above level for insertion, go down tree recursively
Node* otherNode;
@@ -969,15 +946,12 @@
// 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)
- {
+ 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
- {
+ } 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);
@@ -989,14 +963,10 @@
// 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)
- {
+ } 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);
- }
- else
- {
+ } else {
// Should never occur
RTreeAssert(0);
return false;
@@ -1017,8 +987,7 @@
RTreeAssert(a_root);
RTreeAssert(a_level >= 0 && a_level <= (*a_root)->m_level);
#ifdef _DEBUG
- for (int index = 0; index < kNumDimensions; ++index)
- {
+ for (int index = 0; index < kNumDimensions; ++index) {
RTreeAssert(a_branch.m_rect.m_min[index] <=
a_branch.m_rect.m_max[index]);
}
#endif //_DEBUG
@@ -1025,8 +994,7 @@
Node* newNode;
- if (InsertRectRec(a_branch, *a_root, &newNode, a_level)) // Root split
- {
+ 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;
@@ -1060,8 +1028,7 @@
RTreeAssert(a_node);
Rect rect = a_node->m_branch[0].m_rect;
- for (int index = 1; index < a_node->m_count; ++index)
- {
+ for (int index = 1; index < a_node->m_count; ++index) {
rect = CombineRect(&rect, &(a_node->m_branch[index].m_rect));
}
@@ -1079,15 +1046,12 @@
RTreeAssert(a_branch);
RTreeAssert(a_node);
- if (a_node->m_count < _MaxNodeCount) // Split won't be necessary
- {
+ 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;
return false;
- }
- else
- {
+ } else {
RTreeAssert(a_newNode);
SplitNode(a_node, a_branch, a_newNode);
@@ -1129,21 +1093,17 @@
int best = 0;
Rect tempRect;
- for (int index = 0; index < a_node->m_count; ++index)
- {
+ 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)
- {
+ if ((increase < bestIncr) || firstTime) {
best = index;
bestArea = area;
bestIncr = increase;
firstTime = false;
- }
- else if (NEAR_EQUAL(increase, bestIncr, ON_ZERO_TOLERANCE) && (area <
bestArea))
- {
+ } else if (NEAR_EQUAL(increase, bestIncr, ON_ZERO_TOLERANCE) && (area <
bestArea)) {
best = index;
bestArea = area;
bestIncr = increase;
@@ -1161,8 +1121,7 @@
Rect newRect;
- for (int index = 0; index < kNumDimensions; ++index)
- {
+ 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]);
}
@@ -1212,8 +1171,7 @@
auto volume = kElementTypeRealOne;
- for (int index = 0; index < kNumDimensions; ++index)
- {
+ for (int index = 0; index < kNumDimensions; ++index) {
volume *= a_rect->m_max[index] - a_rect->m_min[index];
}
@@ -1231,8 +1189,7 @@
ElementTypeReal sumOfSquares = kElementTypeRealZero;
- for (int index = 0; index < kNumDimensions; ++index)
- {
+ 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;
}
@@ -1240,16 +1197,11 @@
const auto radius = CastElementTypeReal(sqrt(sumOfSquares));
// Pow maybe slow, so test for common dims like 2,3 and just use x*x,
x*x*x.
- if (kNumDimensions == 3)
- {
+ if (kNumDimensions == 3) {
return (radius * radius * radius * m_unitSphereVolume);
- }
- else if (kNumDimensions == 2)
- {
+ } else if (kNumDimensions == 2) {
return (radius * radius * m_unitSphereVolume);
- }
- else
- {
+ } else {
return CastElementTypeReal(pow(radius, kNumDimensions) *
m_unitSphereVolume);
}
}
@@ -1277,8 +1229,7 @@
RTreeAssert(a_node->m_count == _MaxNodeCount);
// Load the branch buffer
- for (int index = 0; index < _MaxNodeCount; ++index)
- {
+ for (int index = 0; index < _MaxNodeCount; ++index) {
a_parVars->m_branchBuf[index] = a_node->m_branch[index];
}
a_parVars->m_branchBuf[_MaxNodeCount] = *a_branch;
@@ -1286,8 +1237,7 @@
// Calculate rect containing all in the set
a_parVars->m_coverSplit = a_parVars->m_branchBuf[0].m_rect;
- for (int index = 1; index < _MaxNodeCount + 1; ++index)
- {
+ 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_coverSplitArea = CalcRectVolume(&a_parVars->m_coverSplit);
@@ -1317,14 +1267,11 @@
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])
- {
+ 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]);
@@ -1331,24 +1278,18 @@
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)
- {
+ if (diff >= 0) {
group = 0;
- }
- else
- {
+ } else {
group = 1;
diff = -diff;
}
- if (diff > biggestDiff)
- {
+ 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]))
- {
+ } else if (NEAR_EQUAL(diff, biggestDiff, ON_ZERO_TOLERANCE) &&
(a_parVars->m_count[group] < a_parVars->m_count[betterGroup])) {
chosen = index;
betterGroup = group;
}
@@ -1358,20 +1299,14 @@
}
// 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)
- {
+ 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
- {
+ } else {
group = 0;
}
- for (int index = 0; index < a_parVars->m_total; ++index)
- {
- if (PartitionVars::kNotTaken == a_parVars->m_partition[index])
- {
+ for (int index = 0; index < a_parVars->m_total; ++index) {
+ if (PartitionVars::kNotTaken == a_parVars->m_partition[index]) {
Classify(index, group, a_parVars);
}
}
@@ -1379,7 +1314,7 @@
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));
}
@@ -1391,14 +1326,13 @@
RTreeAssert(a_nodeB);
RTreeAssert(a_parVars);
- for (int index = 0; index < a_parVars->m_total; ++index)
- {
+ for (int index = 0; index < a_parVars->m_total; ++index) {
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 };
- // It is assured that AddBranch here will not cause a node split.
+ // It is assured that AddBranch here will not cause a node split.
AddBranch(&a_parVars->m_branchBuf[index], targetNodes[targetNodeIndex],
nullptr);
}
}
@@ -1414,8 +1348,7 @@
a_parVars->m_area[0] = a_parVars->m_area[1] = kElementTypeRealZero;
a_parVars->m_total = a_maxRects;
a_parVars->m_minFill = a_minFill;
- for (int index = 0; index < a_maxRects; ++index)
- {
+ for (int index = 0; index < a_maxRects; ++index) {
a_parVars->m_partition[index] = PartitionVars::kNotTaken;
}
}
@@ -1428,20 +1361,16 @@
_ElementTypeReal worst{ 0.0 }, waste{ 0.0 };
_ElementTypeReal area[_MaxNodeCount + 1] = { 0.0, };
- for (int index = 0; index < a_parVars->m_total; ++index)
- {
+ for (int index = 0; index < a_parVars->m_total; ++index) {
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)
- {
+ 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)
- {
+ if (waste > worst) {
worst = waste;
seed0 = indexA;
seed1 = indexB;
@@ -1464,12 +1393,9 @@
a_parVars->m_partition[a_index] = a_group;
// Calculate combined rect
- if (a_parVars->m_count[a_group] == 0)
- {
+ if (a_parVars->m_count[a_group] == 0) {
a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect;
- }
- else
- {
+ } else {
a_parVars->m_cover[a_group] =
CombineRect(&a_parVars->m_branchBuf[a_index].m_rect,
&a_parVars->m_cover[a_group]);
}
@@ -1492,19 +1418,16 @@
ListNode* reInsertList{ nullptr };
- if (!RemoveRectRec(a_rect, a_id, *a_root, &reInsertList))
- {
+ if (!RemoveRectRec(a_rect, a_id, *a_root, &reInsertList)) {
// Found and deleted a data item
// Reinsert any branches from eliminated nodes
- while (reInsertList)
- {
+ while (reInsertList) {
Node* tempNode = reInsertList->m_node;
- for (int index = 0; index < tempNode->m_count; ++index)
- {
+ for (int index = 0; index < tempNode->m_count; ++index) {
InsertRect(tempNode->m_branch[index],
- a_root,
- tempNode->m_level);
+ a_root,
+ tempNode->m_level);
}
ListNode* remLNode = reInsertList;
@@ -1516,8 +1439,7 @@
// 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())
- {
+ if ((*a_root)->m_count == 1 && (*a_root)->IsInternalNode()) {
auto tempNode = (*a_root)->m_branch[0].m_child;
RTreeAssert(tempNode);
@@ -1525,9 +1447,7 @@
*a_root = tempNode;
}
return false;
- }
- else
- {
+ } else {
return true;
}
}
@@ -1543,21 +1463,14 @@
RTreeAssert(a_rect && a_node && a_listNode);
RTreeAssert(a_node->m_level >= 0);
- 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)
- {
+ 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
- {
+ } 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
@@ -1567,13 +1480,9 @@
}
}
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)
- {
+ } 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;
}
@@ -1589,11 +1498,9 @@
{
RTreeAssert(a_rectA && a_rectB);
- for (int index = 0; index < kNumDimensions; ++index)
- {
+ 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])
- {
+ a_rectB->m_min[index] > a_rectA->m_max[index]) {
return false;
}
}
@@ -1623,33 +1530,24 @@
RTreeAssert(a_node->m_level >= 0);
RTreeAssert(a_rect);
- if (a_node->IsInternalNode())
- {
+ 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))
- {
+ 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
- {
+ } 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))
- {
+ 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))
- {
+ if (callback && !callback(id, a_context)) {
return false; // Don't continue searching
}
}
@@ -1667,12 +1565,12 @@
for (int index2 = 0; index2 < a_nodeB->m_count; ++index2) {
if (Overlap(&(a_nodeA->m_branch[index].m_rect),
&(a_nodeB->m_branch[index2].m_rect))) {
if (a_nodeA->m_level > 0) {
- if ( a_nodeB->m_level > 0 ) {
+ if (a_nodeB->m_level > 0) {
ocnt += CheckNodes(a_nodeA->m_branch[index].m_child,
a_nodeB->m_branch[index2].m_child, a_result, b_result);
} else {
ocnt += CheckNodes(a_nodeA->m_branch[index].m_child,
a_nodeB, a_result, b_result);
}
- } else if ( a_nodeB->m_level > 0 ) {
+ } else if (a_nodeB->m_level > 0) {
ocnt += CheckNodes(a_nodeA,
a_nodeB->m_branch[index2].m_child, a_result, b_result);
} else {
a_result->insert(a_nodeA->m_branch[index].m_data);
@@ -1699,22 +1597,22 @@
{
size_t ocnt = 0;
for (int index = 0; index < a_nodeA->m_count; ++index) {
- for (int index2 = 0; index2 < a_nodeB->m_count; ++index2) {
- if (Overlap(&(a_nodeA->m_branch[index].m_rect),
&(a_nodeB->m_branch[index2].m_rect))) {
- if (a_nodeA->m_level > 0) {
- if ( a_nodeB->m_level > 0 ) {
- ocnt += CheckNodes(a_nodeA->m_branch[index].m_child,
a_nodeB->m_branch[index2].m_child, result);
- } else {
- ocnt += CheckNodes(a_nodeA->m_branch[index].m_child,
a_nodeB, result);
- }
- } else if ( a_nodeB->m_level > 0 ) {
- ocnt += CheckNodes(a_nodeA,
a_nodeB->m_branch[index2].m_child, result);
- } else {
- result->insert(std::pair<DataType,
DataType>(a_nodeA->m_branch[index].m_data, a_nodeB->m_branch[index2].m_data));
- ocnt++;
- }
- }
- }
+ for (int index2 = 0; index2 < a_nodeB->m_count; ++index2) {
+ if (Overlap(&(a_nodeA->m_branch[index].m_rect),
&(a_nodeB->m_branch[index2].m_rect))) {
+ if (a_nodeA->m_level > 0) {
+ if (a_nodeB->m_level > 0) {
+ ocnt += CheckNodes(a_nodeA->m_branch[index].m_child,
a_nodeB->m_branch[index2].m_child, result);
+ } else {
+ ocnt += CheckNodes(a_nodeA->m_branch[index].m_child,
a_nodeB, result);
+ }
+ } else if (a_nodeB->m_level > 0) {
+ ocnt += CheckNodes(a_nodeA,
a_nodeB->m_branch[index2].m_child, result);
+ } else {
+ result->insert(std::pair<DataType,
DataType>(a_nodeA->m_branch[index].m_data, a_nodeB->m_branch[index2].m_data));
+ ocnt++;
+ }
+ }
+ }
}
return ocnt;
}
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
