#include <opennurbs_rtree.h>

Public Member Functions
	ON_RTree (size_t leaf_count=0)

	~ON_RTree ()

ON_BoundingBox	BoundingBox () const

bool	CreateMeshFaceTree (const class ON_Mesh *mesh)
	Create an R-tree with an element for each face in the mesh. The element id is set to the index of the face. More...

int	ElementCount ()

bool	Insert (const double a_min[3], const double a_max[3], void *a_element_id)
	Insert an element into the RTree. More...

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

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

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

bool	Remove (const double a_min[3], const double a_max[3], void *a_elementId)
	Remove an element from the RTree. More...

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

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

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

void	RemoveAll ()
	Remove all elements from the R-tree. More...

const ON_RTreeNode *	Root () const

bool	Search (ON_RTreeSphere a_sphere, bool ON_CALLBACK_CDECL resultCallback(void a_context, ON__INT_PTR a_id), void *a_context) const
	Search the R-tree for all elements whose bounding boxes overlap a_rect. More...

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_RTreeBBox a_rect, bool ON_CALLBACK_CDECL resultCallback(void a_context, ON__INT_PTR a_id), void *a_context) 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
	Search the R-tree for all elements whose bounding boxes overlap the set of points between to parallel planes. More...

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< 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_min[3], const double a_max[3], ON_SimpleArray< int > &a_result) const

bool	Search (double tolerance, ON_SimpleArray< ON_2dex > &a_result) const
	Search a single R-tree for all pairs of distinct elements whose bounding boxes overlap. More...

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
	Search a single R-tree for all pairs of distinct elements whose bounding boxes overlap. More...

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
	Search a single R-tree for all pairs of distinct elements whose bounding boxes overlap. More...

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
	Search a single R-tree for all pairs of distinct elements whose bounding boxes overlap. More...

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< ON_RTreeLeaf > &a_result) const

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

bool	Search2d (const double a_min[2], const double a_max[2], ON_SimpleArray< int > &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, ON_SimpleArray< ON_2dex > &a_result)
	Search two R-trees for all pairs elements whose bounding boxes overlap. More...

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)
	Search two R-trees for all pairs elements whose bounding boxes overlap. More...

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)
	Search two R-trees for all pairs elements whose bounding boxes overlap. More...

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)
	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. More...

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 )

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],
		void *	a_element_id
	)

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.

Calling Insert() or Remove() invalidates any ON_RTreeIterator used to iterate this rtree.

◆ Insert() [2/2]

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

◆ Insert2d() [1/2]

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

◆ Insert2d() [2/2]

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

◆ Remove() [1/2]

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

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.

Calling Insert() or Remove() invalidates any ON_RTreeIterator used to iterate this rtree.

◆ Remove() [2/2]

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

◆ Remove2d() [1/2]

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

◆ Remove2d() [2/2]

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

◆ RemoveAll()

void ON_RTree::RemoveAll ( )

Remove all elements from the R-tree.

◆ Root()

const ON_RTreeNode* ON_RTree::Root ( ) const

Returns: Pointer to the root node.

◆ Search() [1/18]

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

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.

If you are using a Search() that uses a resultCallback() function, then return true to keep searching and false to terminate the search.

◆ Search() [2/18]

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() [3/18]

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

◆ Search() [4/18]

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

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.

If you are using a Search() that uses a resultCallback() function, then return true to keep searching and false to terminate the search.

◆ Search() [5/18]

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() [6/18]

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() [7/18]

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

◆ Search() [8/18]

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

◆ Search() [9/18]

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

◆ Search() [10/18]

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

◆ Search() [11/18]

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

static

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.

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/18]

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

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.

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/18]

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

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.

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/18]

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

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.

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/18]

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

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() [16/18]

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

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() [17/18]

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

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() [18/18]

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

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.

◆ 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< ON_RTreeLeaf > &	a_result
	)		const

◆ Search2d() [4/5]

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

◆ Search2d() [5/5]

bool ON_RTree::Search2d	(	const double	a_min[2],
		const double	a_max[2],
		ON_SimpleArray< int > &	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

Public Member Functions

Static Public Member Functions

Static Public Attributes

Constructor & Destructor Documentation

◆ ON_RTree()

◆ ~ON_RTree()

Member Function Documentation

◆ BoundingBox()

◆ CreateMeshFaceTree()

◆ ElementCount()

◆ Insert() [1/2]

◆ Insert() [2/2]

◆ Insert2d() [1/2]

◆ Insert2d() [2/2]

◆ Remove() [1/2]

◆ Remove() [2/2]

◆ Remove2d() [1/2]

◆ Remove2d() [2/2]

◆ RemoveAll()

◆ Root()

◆ Search() [1/18]

◆ Search() [2/18]

◆ Search() [3/18]

◆ Search() [4/18]

◆ Search() [5/18]

◆ Search() [6/18]

◆ Search() [7/18]

◆ Search() [8/18]

◆ Search() [9/18]

◆ Search() [10/18]

◆ Search() [11/18]

◆ Search() [12/18]

◆ Search() [13/18]

◆ Search() [14/18]

◆ Search() [15/18]

◆ Search() [16/18]

◆ Search() [17/18]

◆ Search() [18/18]

◆ Search2d() [1/5]

◆ Search2d() [2/5]

◆ Search2d() [3/5]

◆ Search2d() [4/5]

◆ Search2d() [5/5]

◆ SizeOf()

Member Data Documentation

◆ Empty