Revision: 73961
http://sourceforge.net/p/brlcad/code/73961
Author: starseeker
Date: 2019-09-18 20:41:47 +0000 (Wed, 18 Sep 2019)
Log Message:
-----------
Initial stab at boiling down the idea outlined by the openNURBS code into
RTree.h terms. Untested.
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:59:37 UTC (rev 73960)
+++ brlcad/trunk/src/libbrep/RTree.h 2019-09-18 20:41:47 UTC (rev 73961)
@@ -8,6 +8,7 @@
#include <functional>
#include <type_traits>
#include <cmath>
+#include <set>
#include "opennurbs.h"
#define RTreeAssert assert // RTree uses RTreeAssert( condition )
@@ -102,8 +103,9 @@
/// \return Returns the number of entries found
int Search(const Element& a_min, const Element& a_max,
std::function<bool(const DataType&, void *)> callback, void *a_context) const;
- // Find the overlapping leaves between this rtree and another rtree
- bool Overlaps(RTree &other, double tolerance, std::function<bool(const
DataType&, const DataType&, void *)> callback, void *a_context);
+ // Find the overlapping leaves between this rtree and another rtree,
returning the data from each
+ // leaf in the respective a and b result sets.
+ size_t Overlaps(RTree &other, std::set<DataType> *a_result,
std::set<DataType> *b_result);
/// Remove all entries from tree
void RemoveAll();
@@ -374,6 +376,8 @@
bool LoadRec(Node* a_node, RTFileStream& a_stream);
void CopyRec(Node* current, Node* other);
+ size_t CheckNodes(Node *a_nodeA, Node *a_nodeB, std::set<DataType>
*a_result, std::set<DataType> *b_result);
+
Node* m_root = nullptr; ///< Root
of tree
ElementTypeReal m_unitSphereVolume = kElementTypeRealZero; ///< Unit
sphere constant for required number of dimensions
};
@@ -1645,15 +1649,39 @@
return true; // Continue searching
}
+RTREE_TEMPLATE
+size_t RTREE_QUAL::CheckNodes(Node *a_nodeA, Node *a_nodeB, std::set<DataType>
*a_result, std::set<DataType> *b_result)
+{
+ 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, a_result, b_result);
+ } else {
+ ocnt += CheckNodes(a_nodeA->m_branch[index].m_child,
a_nodeB->m_branch[index2], a_result, b_result);
+ }
+ } else if ( a_nodeB->m_level > 0 ) {
+ ocnt += CheckNodes(a_nodeA->m_branch[index],
a_nodeB->m_branch[index2].m_child, a_result, b_result);
+ } else {
+ a_result->insert(a_nodeA->m_branch[index].m_data);
+ b_result->insert(a_nodeB->m_branch[index2].m_data);
+ ocnt++;
+ }
+ }
+ }
+ }
+ return ocnt;
+}
-
-// Based on the idea from the openNURBS code to search two R-trees for all
pairs elements whose bounding boxes overlap.
+// Loosely based on the idea from the openNURBS code to search two R-trees for
all pairs elements whose bounding boxes overlap.
RTREE_TEMPLATE
-bool RTREE_QUAL::Overlaps(RTree &other, double tolerance,
std::function<bool(const DataType&, const DataType&, void *)> callback, void
*a_context)
+size_t RTREE_QUAL::Overlaps(RTree &other, std::set<DataType> *a_result,
std::set<DataType> *b_result)
{
- if (!m_root || !other.m_root) return false;
- if (tolerance < 0) return false;
- return true;
+ if (!m_root || !other.m_root) return 0;
+ size_t ovlp_cnt = CheckNodes(m_root, other.m_root, a_result, b_result);
+ return ovlp_cnt;
}
#undef RTREE_TEMPLATE
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
