Rhino C++ API  7.21
Public Member Functions | Static Public Member Functions | Static Public Attributes | List of all members
ON_RTree Class Reference

#include <opennurbs_rtree.h>

Inheritance diagram for ON_RTree:
ON_SubDRTree

Public Member Functions

 ON_RTree (size_t leaf_count=0)
 
 ~ON_RTree ()
 
ON_BoundingBox BoundingBox () const
 
bool CreateMeshFaceTree (const class ON_Mesh *mesh)
 
int ElementCount ()
 
bool Insert (const double a_min[3], const double a_max[3], int a_element_id)
 
bool Insert (const double a_min[3], const double a_max[3], void *a_element_id)
 
bool Insert2d (const double a_min[2], const double a_max[2], int a_element_id)
 
bool Insert2d (const double a_min[2], const double a_max[2], void *a_element_id)
 
bool Remove (const double a_min[3], const double a_max[3], int a_elementId)
 
bool Remove (const double a_min[3], const double a_max[3], void *a_elementId)
 
bool Remove2d (const double a_min[2], const double a_max[2], int a_elementId)
 
bool Remove2d (const double a_min[2], const double a_max[2], void *a_elementId)
 
void RemoveAll ()
 
const ON_RTreeNodeRoot () const
 
bool Search (const class ON_PlaneEquation &a_plane_eqn, double a_min, double a_max, bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_id), void *a_context) const
 
bool Search (const double a_min[3], const double a_max[3], bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_id), void *a_context) const
 
bool Search (const double a_min[3], const double a_max[3], ON_RTreeSearchResult &a_result) const
 
bool Search (const double a_min[3], const double a_max[3], ON_SimpleArray< int > &a_result) const
 
bool Search (const double a_min[3], const double a_max[3], ON_SimpleArray< ON_RTreeLeaf > &a_result) const
 
bool Search (const double a_min[3], const double a_max[3], ON_SimpleArray< void * > &a_result) const
 
bool Search (const double a_plane_eqn[4], double a_min, double a_max, bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_id), void *a_context) const
 
bool Search (const ON_Line *a_line, bool infinite, bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_id), void *a_context) const
 
bool Search (const ON_Line *a_line, bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_id), void *a_context) const
 
bool Search (const ON_Polyline *polyline, bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_id), ON_RTreePolylineContext *a_context) const
 
bool Search (double tolerance, bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB), void *a_context) const
 
bool Search (double tolerance, bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB, double *tolerance), void *a_context) const
 
bool Search (double tolerance, ON_SimpleArray< ON_2dex > &a_result) const
 
bool Search (double tolerance, void ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB), void *a_context) const
 
bool Search (ON_RTreeBBox *a_rect, bool ON_CALLBACK_CDECL a_resultCallback(void *a_context, ON__INT_PTR a_id), void *a_context) const
 
bool Search (ON_RTreeCapsule *a_capsule, bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_id), void *a_context) const
 
bool Search (ON_RTreeSphere *a_sphere, bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_id), void *a_context) const
 
bool Search2d (const double a_min[2], const double a_max[2], bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_id), void *a_context) const
 
bool Search2d (const double a_min[2], const double a_max[2], ON_RTreeSearchResult &a_result) const
 
bool Search2d (const double a_min[2], const double a_max[2], ON_SimpleArray< int > &a_result) const
 
bool Search2d (const double a_min[2], const double a_max[2], ON_SimpleArray< ON_RTreeLeaf > &a_result) const
 
bool Search2d (const double a_min[2], const double a_max[2], ON_SimpleArray< void * > &a_result) const
 
size_t SizeOf () const
 

Static Public Member Functions

static bool Search (const ON_RTree &a_rtreeA, const ON_RTree &a_rtreeB, double tolerance, bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB), void *a_context)
 
static bool Search (const ON_RTree &a_rtreeA, const ON_RTree &a_rtreeB, double tolerance, bool ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB, double *tolerance), void *a_context)
 
static bool Search (const ON_RTree &a_rtreeA, const ON_RTree &a_rtreeB, double tolerance, ON_SimpleArray< ON_2dex > &a_result)
 
static bool Search (const ON_RTree &a_rtreeA, const ON_RTree &a_rtreeB, double tolerance, void ON_CALLBACK_CDECL resultCallback(void *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB), void *a_context)
 

Static Public Attributes

static const ON_RTree Empty
 

Constructor & Destructor Documentation

◆ ON_RTree()

ON_RTree::ON_RTree ( size_t  leaf_count = 0)

◆ ~ON_RTree()

ON_RTree::~ON_RTree ( )

Member Function Documentation

◆ BoundingBox()

ON_BoundingBox ON_RTree::BoundingBox ( ) const

Returns: Bounding box of the entire R-tree;

◆ CreateMeshFaceTree()

bool ON_RTree::CreateMeshFaceTree ( const class ON_Mesh mesh)

Description: Create an R-tree with an element for each face in the mesh. The element id is set to the index of the face. Parameters: mesh - [in] Returns: True if successful.

◆ ElementCount()

int ON_RTree::ElementCount ( )

Returns: Number of elements (leaves). Remark: No internal count is maintained, so this function traverses the tree to count the leaves. If efficiency is important, save the result.

◆ Insert() [1/2]

bool ON_RTree::Insert ( const double  a_min[3],
const double  a_max[3],
int  a_element_id 
)

◆ Insert() [2/2]

bool ON_RTree::Insert ( const double  a_min[3],
const double  a_max[3],
void *  a_element_id 
)

Description: Insert an element into the RTree. Parameters: a_min - [in] a_max - [in] 3d bounding box of the element. The values in a_min[3] and a_max[3] must satisfy a_min[0] <= a_max[0], a_min[1] <= a_max[1], and a_min[1] <= a_max[1]. a_dataId - [in] id of the element. This can be either a pointer or an integer id. Returns: True if element was successfully inserted. Remarks: Calling Insert() or Remove() invalidates any ON_RTreeIterator used to iterate this rtree.

◆ Insert2d() [1/2]

bool ON_RTree::Insert2d ( const double  a_min[2],
const double  a_max[2],
int  a_element_id 
)

◆ Insert2d() [2/2]

bool ON_RTree::Insert2d ( const double  a_min[2],
const double  a_max[2],
void *  a_element_id 
)

◆ Remove() [1/2]

bool ON_RTree::Remove ( const double  a_min[3],
const double  a_max[3],
int  a_elementId 
)

◆ Remove() [2/2]

bool ON_RTree::Remove ( const double  a_min[3],
const double  a_max[3],
void *  a_elementId 
)

Description: Remove an element from the RTree. Parameters: a_min - [in] a_max - [in] 3d bounding box of the element. The values in a_min[3] and a_max[3] must satisfy a_min[0] <= a_max[0], a_min[1] <= a_max[1], and a_min[2] <= a_max[2]. a_dataId - [in] id of the element. This can be either a pointer or an integer id. Returns: True if element was successfully removed. Remarks: Calling Insert() or Remove() invalidates any ON_RTreeIterator used to iterate this rtree.

◆ Remove2d() [1/2]

bool ON_RTree::Remove2d ( const double  a_min[2],
const double  a_max[2],
int  a_elementId 
)

◆ Remove2d() [2/2]

bool ON_RTree::Remove2d ( const double  a_min[2],
const double  a_max[2],
void *  a_elementId 
)

◆ RemoveAll()

void ON_RTree::RemoveAll ( )

Description: Remove all elements from the R-tree.

◆ Root()

const ON_RTreeNode* ON_RTree::Root ( ) const

Returns: Pointer to the root node.

◆ Search() [1/21]

bool ON_RTree::Search ( const class ON_PlaneEquation a_plane_eqn,
double  a_min,
double  a_max,
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_id,
void *  a_context 
) const

◆ Search() [2/21]

bool ON_RTree::Search ( const double  a_min[3],
const double  a_max[3],
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_id,
void *  a_context 
) const

◆ Search() [3/21]

bool ON_RTree::Search ( const double  a_min[3],
const double  a_max[3],
ON_RTreeSearchResult a_result 
) const

◆ Search() [4/21]

bool ON_RTree::Search ( const double  a_min[3],
const double  a_max[3],
ON_SimpleArray< int > &  a_result 
) const

◆ Search() [5/21]

bool ON_RTree::Search ( const double  a_min[3],
const double  a_max[3],
ON_SimpleArray< ON_RTreeLeaf > &  a_result 
) const

◆ Search() [6/21]

bool ON_RTree::Search ( const double  a_min[3],
const double  a_max[3],
ON_SimpleArray< void * > &  a_result 
) const

◆ Search() [7/21]

bool ON_RTree::Search ( const double  a_plane_eqn[4],
double  a_min,
double  a_max,
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_id,
void *  a_context 
) const

Description: Search the R-tree for all elements whose bounding boxes overlap the set of points between to parallel planes. Parameters: a_plane_eqn - [in] a_min - [in] a_max - [in] The region between the parallel planes is the set point points where the value of the plane equation is >= a_min and <= a_max. resultCallback - [in] A function to call when leaf nodes overlap the region between the parallel planes. a_context - [in] pointer passed to the resultCallback() function. Returns: True if entire tree was searched. It is possible no results were found. Remarks: If you are using a Search() that uses a resultCallback() function, then return true to keep searching and false to terminate the search.

◆ Search() [8/21]

bool ON_RTree::Search ( const ON_Line a_line,
bool  infinite,
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_id,
void *  a_context 
) const

◆ Search() [9/21]

bool ON_RTree::Search ( const ON_Line a_line,
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_id,
void *  a_context 
) const

◆ Search() [10/21]

bool ON_RTree::Search ( const ON_Polyline polyline,
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_id,
ON_RTreePolylineContext a_context 
) const

◆ Search() [11/21]

static bool ON_RTree::Search ( const ON_RTree a_rtreeA,
const ON_RTree a_rtreeB,
double  tolerance,
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB,
void *  a_context 
)
static

Description: Search two R-trees for all pairs elements whose bounding boxes overlap. Parameters: a_rtreeA - [in] a_rtreeB - [in] tolerance - [in] If the distance between a pair of bounding boxes is <= tolerance, then resultCallback() is called. resultCallback - [out] callback function Return true for the search to continue and false to terminate the search. a_context - [in] argument passed through to resultCallback(). Returns: True if entire tree was searched. It is possible no results were found. Remarks: If you have a single R-tree and you want to find paris of distinct nodes whose bounding boxes overlap, then use the non-static ON_RTree::Search(double tolerance, ... results ) member functions.

◆ Search() [12/21]

static bool ON_RTree::Search ( const ON_RTree a_rtreeA,
const ON_RTree a_rtreeB,
double  tolerance,
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB, double *tolerance,
void *  a_context 
)
static

Description: Search two R-trees for all pairs elements whose bounding boxes overlap. The tolerance can be reduced by the callback function during the search. This version of search is well suited to finding closest points between two objects. Parameters: a_rtreeA - [in] a_rtreeB - [in] tolerance - [in] If the distance between a pair of bounding boxes is <= tolerance, then resultCallback() is called. resultCallback - [out] callback function Return true for the search to continue and false to terminate the search. The callback may reduce the value of the tolerance parameter during the search. Increasing the value of the tolerance or setting it to an invalid value is not supported and will lead to unpredictable results. a_context - [in] argument passed through to resultCallback(). Returns: True if entire tree was searched. It is possible no results were found. Remarks: If you have a single R-tree and you want to find paris of distinct nodes whose bounding boxes overlap, then use the non-static ON_RTree::Search(double tolerance, ... results ) member functions.

◆ Search() [13/21]

static bool ON_RTree::Search ( const ON_RTree a_rtreeA,
const ON_RTree a_rtreeB,
double  tolerance,
ON_SimpleArray< ON_2dex > &  a_result 
)
static

Description: Search two R-trees for all pairs elements whose bounding boxes overlap. Parameters: a_rtreeA - [in] a_rtreeB - [in] tolerance - [in] If the distance between a pair of bounding boxes is <= tolerance, then the pair is added to a_result[]. a_result - [out] Pairs of ids of elements who bounding boxes overlap. Returns: True if entire tree was searched. It is possible no results were found. Remarks: If you have a single R-tree and you want to find paris of distinct nodes whose bounding boxes overlap, then use the non-static ON_RTree::Search(double tolerance, ... results ) member functions.

◆ Search() [14/21]

static bool ON_RTree::Search ( const ON_RTree a_rtreeA,
const ON_RTree a_rtreeB,
double  tolerance,
void ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB,
void *  a_context 
)
static

Description: Search two R-trees for all pairs elements whose bounding boxes overlap. Parameters: a_rtreeA - [in] a_rtreeB - [in] tolerance - [in] If the distance between a pair of bounding boxes is <= tolerance, then resultCallback() is called. resultCallback - [out] callback function a_context - [in] argument passed through to resultCallback(). Returns: True if entire tree was searched. It is possible no results were found. Remarks: If you have a single R-tree and you want to find paris of distinct nodes whose bounding boxes overlap, then use the non-static ON_RTree::Search(double tolerance, ... results ) member functions.

◆ Search() [15/21]

bool ON_RTree::Search ( double  tolerance,
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB,
void *  a_context 
) const

Description: Search a single R-tree for all pairs of distinct elements whose bounding boxes overlap. Parameters: tolerance - [in] If the distance between a pair of bounding boxes is <= tolerance, then resultCallback() is called. resultCallback - [out] callback function a_context - [in] argument passed through to resultCallback(). Returns: True if entire tree was searched. It is possible no results were found.

◆ Search() [16/21]

bool ON_RTree::Search ( double  tolerance,
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB, double *tolerance,
void *  a_context 
) const

Description: Search a single R-tree for all pairs of distinct elements whose bounding boxes overlap. Parameters: tolerance - [in] If the distance between a pair of bounding boxes is <= tolerance, then resultCallback() is called. resultCallback - [out] callback function Return true for the search to continue and false to terminate the search. The callback may reduce the value of the tolerance parameter during the search. Increasing the value of the tolerance or setting it to an invalid value is not supported and will lead to unpredictable results. a_context - [in] argument passed through to resultCallback(). Returns: True if entire tree was searched. It is possible no results were found.

◆ Search() [17/21]

bool ON_RTree::Search ( double  tolerance,
ON_SimpleArray< ON_2dex > &  a_result 
) const

Description: Search a single R-tree for all pairs of distinct elements whose bounding boxes overlap. Parameters: tolerance - [in] If the distance between a pair of bounding boxes is <= tolerance, then the pair is added to a_result[]. a_result - [out] Pairs of ids of elements who bounding boxes overlap. Returns: True if entire tree was searched. It is possible no results were found.

◆ Search() [18/21]

bool ON_RTree::Search ( double  tolerance,
void ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_idA, ON__INT_PTR a_idB,
void *  a_context 
) const

Description: Search a single R-tree for all pairs of distinct elements whose bounding boxes overlap. Parameters: tolerance - [in] If the distance between a pair of bounding boxes is <= tolerance, then resultCallback() is called. resultCallback - [out] callback function a_context - [in] argument passed through to resultCallback(). Returns: True if entire tree was searched. It is possible no results were found.

◆ Search() [19/21]

bool ON_RTree::Search ( ON_RTreeBBox a_rect,
bool ON_CALLBACK_CDECL   a_resultCallbackvoid *a_context, ON__INT_PTR a_id,
void *  a_context 
) const

◆ Search() [20/21]

bool ON_RTree::Search ( ON_RTreeCapsule a_capsule,
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_id,
void *  a_context 
) const

◆ Search() [21/21]

bool ON_RTree::Search ( ON_RTreeSphere a_sphere,
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_id,
void *  a_context 
) const

Description: Search the R-tree for all elements whose bounding boxes overlap a_rect. Parameters: a_rect - [in/out] The version of search that has ON_RTreeBBox* a_rect as the first argument, allows you to shrink the a_rect as the search progresses. This is useful for doing things like searching for closest points. If you want to shrink a_rect, you must use a_context to pass it to the resultCallback function and shrink it in the resultCallback function. In the callback, the modified rect must be contained in the previous rect. a_sphere - [in/out] The version of search that has ON_RTreeSphere* a_sphere as the first argument, allows you to shrink the a_sphere as the search progresses. This is useful for doing things like searching for closest points. If you want to shrink a_sphere, you must use a_context to pass it to the resultCallback function and shrink it in the resultCallback function. In the callback, the modified sphere must be contained in the previous sphere. a_capsule - [in/out] The version of search that has ON_RTreeSphere* a_capsule as the first argument, allows you to shrink the a_capsule as the search progresses. This is useful for doing things like searching for closest points. If you want to shrink a_capsule, you must use a_context to pass it to the resultCallback function and shrink it in the resultCallback function. In the callback, the modified capsule must be contained in the previous capsule. a_min - [in] a_max - [in] (a_min,a_max) is the bounding box of the search region. a_results - [out] The ids of elements that overlaps the search region. resultCallback - [in] A function to call when leaf nodes overlap. a_context - [in] pointer passed to the resultCallback() function. Returns: True if entire tree was searched. It is possible no results were found. Remarks: If you are using a Search() that uses a resultCallback() function, then return true to keep searching and false to terminate the search.

◆ Search2d() [1/5]

bool ON_RTree::Search2d ( const double  a_min[2],
const double  a_max[2],
bool ON_CALLBACK_CDECL   resultCallbackvoid *a_context, ON__INT_PTR a_id,
void *  a_context 
) const

◆ Search2d() [2/5]

bool ON_RTree::Search2d ( const double  a_min[2],
const double  a_max[2],
ON_RTreeSearchResult a_result 
) const

◆ Search2d() [3/5]

bool ON_RTree::Search2d ( const double  a_min[2],
const double  a_max[2],
ON_SimpleArray< int > &  a_result 
) const

◆ Search2d() [4/5]

bool ON_RTree::Search2d ( const double  a_min[2],
const double  a_max[2],
ON_SimpleArray< ON_RTreeLeaf > &  a_result 
) const

◆ Search2d() [5/5]

bool ON_RTree::Search2d ( const double  a_min[2],
const double  a_max[2],
ON_SimpleArray< void * > &  a_result 
) const

◆ SizeOf()

size_t ON_RTree::SizeOf ( ) const

Returns: Number of bytes of heap memory used by this R-tree.

Member Data Documentation

◆ Empty

const ON_RTree ON_RTree::Empty
static